CS 4804 Homework #1

1. (20 points) Problem 3.8 from your textbook (all five parts).
   
   
2. (10 points) Consider a search space where the nodes form a rectangular grid. Every node is connected to its four neighboring nodes (except, of course, for the ones on the borders). Explain why breadth-first search is a better algorithm for such a space than depth-first iterative deepening (DFID).
   
   
3. (20 points) In the sliding tile puzzle, we are given a rectangular strip on which is placed three black tiles, followed by a blank space, followed by three white tiles. Like so:

   
   (B B B O W W W)
   

   (O is the space)
   
   The puzzle has two legal moves with associated costs. A tile may move into an adjacent empty location. This move has a cost of 1. A tile may also hop over one or two other tiles into the empty position. This move has a cost that is equal to the number of tiles jumped over. The goal is to have all the white tiles to the left of all the black tiles with minimum cost.
   
   Formulate a state-space description of this puzzle; give the initial state, the operators (their costs, and how they alter the state), and the goal test.
   
   Invent an admissible heuristic function for this problem. An answer such as h(n)=0 will fetch you h(n) points.
   
   
4. (10 points) Use your heuristic function in an A* search to a goal node. Work out the steps from the start node and show clearly all the calculations (including g() and h()).
   
   
5. (10 points) Problem 4.2 of your textbook. For full credit, explain for each of the three settings, if the algorithm is complete and if it will lead to the optimal solution.
   
   
6. (30 points; programming) For this question, you are going to write a program for playing a certain card game. The game is a single-player game and involves an ordered list of cards that are presented face up to the player. Each card is labeled with a positive integer. For instance, one starting configuration is:

   
   (7, 5, 1, 2, 8)
   

   The player removes a card from either end of the row until all cards are removed (thus only two types of moves are available). The final score is the sum of the labels of the cards removed in odd moves of the game. The goal is to find a strategy that maximizes the final score.
   
   The game can start with any list of cards, as long as there are an odd number of cards. The numbers presented on the cards must all be positive integers and could be repeated.
   
   Formulate the game as search in state-space; give the starting state, the operators, and the goal test. Develop a non-trivial heuristic function (i.e., something other than h(n)=0) for this problem and perform A* search using it.
   
   Create a collection of test problems to pit against your program, of various sizes. Compare your implementation of A* search (with the heuristic) with breadth first search (BFS). Present results of the following form (graphs):
   
   
   • Number of nodes expanded by A* versus BFS, for various problem sizes
   • Effective branching factor (see textbook; Section 4.2) for A* versus BFS, for various problem sizes
     
     
   To have confidence in your results, it is recommended that you average each measurement over multiple problems (of a given size).
   
   For full credit, explain how you arrived at your heuristic, why it is admissible, and a report of observations based on comparing A* to breadth-first search. Supply a URL where your source code can be inspected (but please do not attach printouts of it with your solution).