CS 480 – WRITTEN ASSIGNMENT 1
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
