Consider the unbounded version of the regular 2D grid shown in Figure 3.9. The start state is at the origin, (0,0), and the goal state is at (x, y).

a. What is the branching factor b in this state space?

b. How many distinct states are there at depth k (for k > 0)?

c. What is the maximum number of nodes expanded by breadth-first tree search?

d. What is the maximum number of nodes expanded by breadth-first graph search?

e. Is h = |u ˆ’ x| + |v ˆ’ y| an admissible heuristic for a state at (u, v)? Explain.

f. How many nodes are expanded by Aˆ— graph search using h?

g. Does h remain admissible if some links are removed?

h. Does h remain admissible if some links are added between nonadjacent states?

Figure 3.9

(a) (b)