Description
1. Solve this problem using greedy-best-first tree search. Show the search tree where the h values
are clearly shown for each node.
2. Solve this problem using uniform-cost tree search. Show the search tree where the g values are
clearly shown for each node.
3. Solve this problem using uniform-cost graph search. Show the search tree where the g values
are clearly shown for each node.
4. Solve this problem using A* tree search. Show the search tree where the f, g, and h values are
clearly shown for each node.
5. Come up with an admissible heuristic function h* that dominates every possible admissible
heuristic for this map; specify h*(n) for all n.
6. Solve the following 3-puzzle problem using A* tree search. For h, use the number of misplaced
tiles (not counting the blank tile) heuristic. The actions are move the blank tile Left (L), Right (R),
Up (U), Down (D), and in that order. At each state, there are exactly two actions available (e.g.,
you cannot move a blank tile to left if it is already on the left edge). If two nodes have equal f
value, break the ties using LIFO order. That is, if two nodes have equal f value, choose the one
that has been generated more recently. Show the search tree where the f, g, and h values are
clearly shown for each node.
2
3 1
