# Question: Consider a state space where the start state is number

Consider a state space where the start state is number 1 and the successor function for state n returns two states, numbers 2n and 2n + 1.

a. Draw the portion of the state space for states 1 to 15.

b. Suppose the goal state is 11. List the order in which nodes will be visited for breadth- first search, depth-limited search with limit 3, and iterative deepening search.

c. Would bidirectional search be appropriate for this problem? If so, describe in detail how it would work.

d. What is the branching factor in each direction of the bidirectional search?

e. Does the answer to (c) suggest a reformulation of the problem that would allow you to solve the problem of getting from state I to a given goal state with almost no search?

a. Draw the portion of the state space for states 1 to 15.

b. Suppose the goal state is 11. List the order in which nodes will be visited for breadth- first search, depth-limited search with limit 3, and iterative deepening search.

c. Would bidirectional search be appropriate for this problem? If so, describe in detail how it would work.

d. What is the branching factor in each direction of the bidirectional search?

e. Does the answer to (c) suggest a reformulation of the problem that would allow you to solve the problem of getting from state I to a given goal state with almost no search?

## Answer to relevant Questions

We mentioned iterative lengthening search, an iterative analog of uniform cost search. The idea is in use increasing limits on path cost. If a node is generated whose path cost exceeds the current limit, it is immediately ...Consider the sensor less, two-location vacuum world under Murphy’s Law. Draw the belief state space reachable from the initial belief state {1, 2, 3, 4, 5, 6, 7, 8), and explain why the problem is unsolvable. Show also ...Prove that if a heuristic is consistent, it must be admissible. Construct an admissible heuristic that is not consistent.In this exercise, we will examine hill climbing in the context of robot navigation, using the environment in Figure as an example.a. Repeat Exercise 3.16 using hill climbing. Does your agent ever get stuck in a local ...What is the worst-case complexity of running AC-3 on a tree-structured CSP?Post your question