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)$.
1. What is the branching factor $b$ in this state space?
2. How many distinct states are there at depth $k$ (for $k>0$)?
3. What is the maximum number of nodes expanded by breadth-first tree search?
4. What is the maximum number of nodes expanded by breadth-first graph search?
5. Is $h = |u-x| + |v-y|$ an admissible heuristic for a state at $(u,v)$? Explain.
6. How many nodes are expanded by A graph search using $h$?
7. Does $h$ remain admissible if some links are removed?
8. Does $h$ remain admissible if some links are added between nonadjacent states?
1. What is the branching factor $b$ in this state space?
2. How many distinct states are there at depth $k$ (for $k>0$)?
3. What is the maximum number of nodes expanded by breadth-first tree search?
4. What is the maximum number of nodes expanded by breadth-first graph search?
5. Is $h = |u-x| + |v-y|$ an admissible heuristic for a state at $(u,v)$? Explain.
6. How many nodes are expanded by A graph search using $h$?
7. Does $h$ remain admissible if some links are removed?
8. Does $h$ remain admissible if some links are added between nonadjacent states?
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)$.
1. What is the branching factor $b$ in this state space?
2. How many distinct states are there at depth $k$ (for $k>0$)?
3. What is the maximum number of nodes expanded by breadth-first tree
search?
4. What is the maximum number of nodes expanded by breadth-first graph
search?
5. Is $h = |u-x| + |v-y|$ an admissible heuristic for a state at
$(u,v)$? Explain.
6. How many nodes are expanded by A graph search using $h$?
7. Does $h$ remain admissible if some links are removed?
8. Does $h$ remain admissible if some links are added between
nonadjacent states?