Problem 3: Consider a state space where the start state is number 1 and each state k has two successors: numbers 2k and 2k+1. As you answer the questions that follow, assume that this state space is infinite in size. a. Draw the portion of the state space for states 1 to 15. Put the 2k successor as the left child of state k and the 2k+1 child as the right child of state k. b. Suppose the goal state is 11. List the order in which nodes will be visited by breadth-first search, assuming that the successors are given in increasing order (i.e., you visit the left 2k successor before the 2k+1 successor). c. Suppose the goal state is 11. List the order in which nodes will be visited by depth- limited search with limit 3, assuming that the successors are given in increasing order (i.e., you visit the left 2k successor before the 2k+1 successor). d. Suppose the goal state is 11. List the order in which nodes will be visited by iterative deepening search, assuming that the successors are given in increasing order (i.e., you visit the left 2k successor before the 2k+1 successor). e. Again, suppose that the goal state is 11. Will depth-first search terminate, assuming that the 2k successor is always visited before the 2k+1 successor? f. Again, suppose that the goal state is 11. Will depth-first search terminate, assuming that the 2k+1 successor is always visited before the 2k successor? g. What is the branching factor for this search space? h. We were given the successors function. It is actually straightforward to specify a predecessors function as well. What are the predecessor(s) of state k? i. Now that we have a predecessors function, what is the branching factor in the backwards direction for this search space (i.e., if we were backward chaining from the goal)? j. Describe the search algorithm that will solve this problem with the least amount of search of all possible search algorithms. Explain your answer. If your answer is an algorithm we've seen, you can just name it, and provide an explanation for why no other search algorithm can solve this problem with less search. If it is a variation of a search algorithm we've seen, you can just indicate its features, and provide an explanation for why no other search algorithm can solve this problem with less search. Hint: Think carefully about your answers to previous parts of this problem. Problem 3: Consider a state space where the start state is number 1 and each state k has two successors: numbers 2k and 2k+1. As you answer the questions that follow, assume that this state space is infinite in size. a. Draw the portion of the state space for states 1 to 15. Put the 2k successor as the left child of state k and the 2k+1 child as the right child of state k. b. Suppose the goal state is 11. List the order in which nodes will be visited by breadth-first search, assuming that the successors are given in increasing order (i.e., you visit the left 2k successor before the 2k+1 successor). c. Suppose the goal state is 11. List the order in which nodes will be visited by depth- limited search with limit 3, assuming that the successors are given in increasing order (i.e., you visit the left 2k successor before the 2k+1 successor). d. Suppose the goal state is 11. List the order in which nodes will be visited by iterative deepening search, assuming that the successors are given in increasing order (i.e., you visit the left 2k successor before the 2k+1 successor). e. Again, suppose that the goal state is 11. Will depth-first search terminate, assuming that the 2k successor is always visited before the 2k+1 successor? f. Again, suppose that the goal state is 11. Will depth-first search terminate, assuming that the 2k+1 successor is always visited before the 2k successor? g. What is the branching factor for this search space? h. We were given the successors function. It is actually straightforward to specify a predecessors function as well. What are the predecessor(s) of state k? i. Now that we have a predecessors function, what is the branching factor in the backwards direction for this search space (i.e., if we were backward chaining from the goal)? j. Describe the search algorithm that will solve this problem with the least amount of search of all possible search algorithms. Explain your answer. If your answer is an algorithm we've seen, you can just name it, and provide an explanation for why no other search algorithm can solve this problem with less search. If it is a variation of a search algorithm we've seen, you can just indicate its features, and provide an explanation for why no other search algorithm can solve this problem with less search. Hint: Think carefully about your answers to previous parts of this