Consider the 3 blocks world in which only one block can be on another block and in which the operators include: picking up a block from the table, putting a block down on the table, stacking a block on another block, and unstacking a block from another block. The complete state space for this problem is illustrated below:

Notes:

• In the figure, states in this space are given arbitrary numbers as names in order to easily refer to them.
• When drawing search trees, number the nodes in the order they are expanded, circle these numbers to distinguish them from the numbers naming the nodes.
• Assume that all children of a state are shown in a search tree but that states resulting in a cycle in the resulting path from the root are eliminated as dead-end states as soon as they are generated (draw an X through them).
• If heuristic search is being used, next to each node generated, show the value of the evaluation function (e.g. "h=2" if just using h, or "1+2=3" for g+h=f when using A*).
• When there is an undetermined decision (tie) regarding which node to expand next, assume nodes with lowered numbered state names are preferred (i.e. expand node 1 before node 2, etc.).
• Assume a goal is detected immediately when it is generated (rather than waiting until it is expanded), except for A*, where waiting to check for goal-hood until expansion is critical to guaranteeing an optimal solution (with an admissable heuristic).

Consider the problem of starting in state 5 with the goal of getting to state 17:

1. Draw the search tree resulting from depth-first search. How many nodes are expanded? (That's "expanded" not "generated"; remember "expansion" is when a node's successors are generated.)
2. Draw the search tree resulting from breadth-first search. How many nodes are expanded? Is depth-first or breadth-first better for this specific problem? Why?
3. Draw the search tree resulting from best-first search using as an evaluation function the number of blocks not in the correct place as an estimate of the remaining distance to the goal. For example, the heuristic value for state 5 is 2 since blocks A and C are not in the correct place (but block B is) relative to the goal state, 17. How many nodes are expanded? Could another search strategy perform any less search in solving this specific problem? Why or why not?
4. Assume that ties are broken randomly rather than always choosing the node with the lowest number. Repeat problem 3, showing search trees for each of the possible random outcomes (each with its corresponding probability) and compute the expected number of nodes expanded.
5. Repeat problems 3 and 4 for hill-climbing instead of best-first search. Which expands fewer nodes? Why?
6. Draw the search tree resulting from using A* with g being the number of operators executed and h being the same heuristic as above and assuming tie-breaking based on node numbers. Is this heuristic admissable? Why or why not? How many nodes are expanded? Is this better or worse than best-first and hill-climbing for this case? Why?