There are 6 questions. Please submit your solutions through blackboard.
1. Solve the 5-queens problem (place 5 queens on a 5x5 board so that none is attacked) using DFS-tree search. The initial state is an empty board. Available actions at each state is to put a queen at the left-most empty column (use only legal actions). (This is a similar setup to the 4-queens problem we solved in class). Show the search tree.
For questions 2, 3, 4, 5, and 6, please use the following figure. We want to travel from S to G, where some of the roads allow only one-way traffic. The distances between two locations are given on the figure. The estimates, h, from a location to G are given on the side.
2. Hand-trace breadth-first tree search. What is the solution path found and what is its cost? Show your work.
3. Hand trace uniform-cost graph search. What is the solution path found and what is its cost? Show your work.
4. Hand trace greedy best-first tree search, where best is defined as the node that has the smallest h(n). What is the solution path found and what is its cost? Show your work.
5. Hand trace A* tree search. What is the solution path found and what is its cost? Show your work.
6. Come up with an admissible heuristic function h* that dominates every possible admissible
heuristic for this map; specify h*(n) for all n. Remember the definition of dominates: h1 dominates h2 if h1(n) h2(n) for all n.
