There are six questions. Please submit your solutions through blackboard.
For questions 1, 2, 3, 4, and 5, please use the following figure. We are currently at S and we want to reach G. The edge costs are given on the edges. The heuristic function is given on the side. Notice that the edges are bi-directional.
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
