2. Create a Manhattan distance heuristic policy class to estimate the dis-
tance between a node and the target in a navigation graph. Try the
heuristic out with different graphs. Is it better or worse than the
Euclidean heuristic for grid-based graphs?
3. The Euclidean heuristic calculates the straight-line distance between
nodes. This calculation requires the use of a square root. Create a heu-
ristic that works in distance-squared space and note the shape of the
paths it creates.
4. Create a program to find the best solution to the n-disk Towers of
Hanoi puzzle where n can be any positive integer. To do this you must
rewrite the BFS algorithm so that nodes and edges are added to the
state graph as the search proceeds. This is an excellent way to test
your understanding of the material presented in this chapter.
5. Now modify the algorithm you created in 4 to search for the best solu
tion using iterative deepening DFS. How does it compare?
6. Use the A* algorithm to solve a shuffled Rubik’s Cube. Give much
consideration to the design of the heuristic function. This is a difficult
problem, searching a potentially enormous search space, so first try
your algorithm on a cube that is only one rotation away from a solu
tion, then two, and so on. (Tip: If you are having difficulty designing a
heuristic, do a search on the Internet… there are several interesting
papers and articles on the subject.)
248 | Chapter 5