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
- 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 sk ends at ek,
both of which are integers. No two classes shares the same classroom. Classrooms
are only available from 1:00 to 4:00.
- 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 aij where i is the row number and j is the column
- Define the states, goal test, and operators for this problem in terms
of aij. 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.