Homework #3, 22.3.

• 1.) Invent a heuristic function for the 8-puzzle that sometimes overestimates, and show how it can lead to a suboptimal solution on a particular problem.

 
• 2.) Recall, that if the SMA* algorithm needs to generate a successor but has no memory left, it will need to make space on the queue. To do this, it drops a vertex from the queue. It prefers to drop nodes that are unpromising - that is nodes with high f-cost. To avoid reexploring subtrees that it has dropped from memory, it retains in the ancestor nodes information about the quality of the best path in the forgotten subtree. In this way, it only regenerates the subtree when all other paths have been shown to look worse than the path it has forgotten.

a) Carefully redo the example we did in class.
b) SMA* abandons paths that fill up memory by themselves but do not contain a solution. Show that without this check, SMA* will get stuck in an infinite loop whenever it does not have enough memory for the shortest solution path.