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

What is the branching factor $b$ in this state space?

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

What is the maximum number of nodes expanded by breadthfirst tree search?

What is the maximum number of nodes expanded by breadthfirst graph search?

Is $h = ux + vy$ an admissible heuristic for a state at $(u,v)$? Explain.

How many nodes are expanded by A graph search using $h$?

Does $h$ remain admissible if some links are removed?

Does $h$ remain admissible if some links are added between nonadjacent states?
Answer
Improve This Solution
View Answer