[Solved] CS480-Homework1-Problem set

There are 6 questions. Please submit your solutions through blackboard.

1. Solve the 5-queens problem (place 5 queens on a 55 board so that none is attacked) using DFStree 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 What is the solution path found and what is its cost? Show your work.
3. Hand trace uniform-cost graph 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 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 Remember the definition of dominates: h₁ dominates h₂ if h₁(n) h₂(n) for all n.