CS 4804 Homework #1

1. (10 points) Give an example of a state space tree (i.e., a diagram with nodes, links, and costs) where depth first search is preferable to depth-first iterative deepening. Explain what you mean by "preferable".
   
   
2. (20 points) In the 4-queens puzzle, we try to place four queens on a 4 by 4 chess board so that none capture any other. Suppose we try to solve this puzzle using the following problem formulation: The start node is the empty board; each successive step creates new 4 by 4 boards containing one additional legal placement of a queen anywhere on the array; the goal predicate is true if and only if there are four queens in the array (legally positioned).
   
   Invent an admissible heuristic function for this problem based on the number of queen placements remaining to achieve the goal. (Note that all goal nodes are precisely four steps from the start node!)
   
   
3. (10 points) Use your heuristic function in an A* search to a goal node. Work out the steps from the start node and show the calculations (including g() and h()).
   
   
4. (10 points) Consider the Tower-of-Hanoi puzzle. Propose an admissible heuristic h(n) for this problem. A heuristic such as h(n)=0 will fetch you h(n) points. You must begin by formulating the puzzle as a search problem and then use the relaxation idea covered in class to determine a heuristic. For full credit, explain your start state, operators, the goal test, and the heuristic.
   
   
5. (10 points) Give an example of a search tree where the evaluation function f(n) = h*(n) leads to the optimal answer.
   
   
6. (10 points) Give an example of a search tree where the evaluation function f(n) = h*(n) does not lead to the optimal answer.
   
   
7. (30 points) For this question, you are going to perform a series of experiments to determine the quality of different heuristics. We will use the 8-puzzle problem as a case study. To complete this problem it will be worth your while to generate a small collection (about 1000) of 8-puzzle problems. Each problem will have a starting state, an ending state, and the shortest path to the goal. It is easy to create this database by actually doing the tile moves (so that you can guarantee that all problems indeed have a solution!).
   
   Use your collection to evaluate the goodness of the following heuristics:
   • h1(n) = # misplaced tiles (covered in class)
   • h2(n) = Manhattan distance (covered in class)
   • h4(n) = # tiles misplaced in terms of row + # tiles misplaced in terms of column
   • h5(n) = {Go around the edge of the board, i.e., omit the center square, count the number of pairs of tiles that are "inverted" compared to the goal position, and return this number}
   
   For full credit, explain which of these heuristics are admissible, and rank them in order of how close they are to h*(n), from worst to best. Keep in mind that for some combinations of heuristics, there may not be any clear winner.