Description
There are 6 questions. Please submit your solutions through blackboard.
-
Solve the 5-queens problem (place 5 queens on a 5×5 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.
-
Hand-trace breadth-first tree search. What is the solution path found and what is its cost? Show your work.
-
Hand trace uniform-cost graph search. What is the solution path found and what is its cost? Show your work.
-
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.
-
Hand trace A* tree search. What is the solution path found and what is its cost? Show your work.
-
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.
