CSE 473 Sp 00** Homework
1** Due 4/17/00

Name: _______________________________________ Email: _____________________________________

- In the following search space, the number beside edges denotes the path cost between nodes, and h is the estimated path cost from the node to the goal state G.
- Give the order by which the nodes are visited in an A* search of the space.
Write down the
*f*(*n*) for each node*n*. - Would greedy search do better? How many more or less nodes does it take greedy search to reach G?
- Both breadth-first search and A* search takes exponential memory. How would you modify A* to use less space? What is the space complexity of your new algorithm?
- If H is also a goal, which algorithms among breadth-first, depth-first and iterative-deepening would find the optimal solution?
- (Bonus) The heuristic function h has a problem, it overestimates the cost from C to G. What property of A* search would be lost if h has this problem?
- Consider the 8-puzzle problem, explain why the
*number of misplaced tiles*and the*Mahattan distance*heuristics do not always make the best move. For each heuristic, give an example to support your explanation by drawing the original state of the 8-puzzle, and describe what move the heuristic chooses and what the optimal move is. - How would you implement best-first search if you can only tell if one node is better than the other, but not the exact cost (h(n))? Explain the differences, if any, of this algorithm.
- In the classroom scheduling problem, we have
*c*classrooms and*k*classes, each class starts at*s*ends at_{k}*e*, both of which are integers. No two classes shares the same classroom. Classrooms are only available from 1:00 to 4:00._{k} - Formulate this problem into a CSP.
- Suggest a heuristic for solving this CSP and explain why you think your heuristic would work.
- Suppose you want to implement a program to play tic-tac-toe. The human player
always use O and computer always use X. Each square on the board is labeled
as a
_{ij }where*i*is the row number and*j*is the column - Define the states, goal test, and operators for this problem in terms
of a
_{ij.}How many possible states are there? - What search algorithm would you use to implement the search? Why?
- Briefly describe a function that evaluates the performance of the computer player given one of the states you defined in part A.