Hold forth on these... I am especially interested in seeing blog comments from 471 students..
First a diversion: Check out the following mail from earlier years on the history of n-puzzle problems and how these grabbed popular imagination at one time..
Now the thinking-cap questions
0. Should h*(n) be zero for *all* goal nodes or only optimal goal nodes?
1. We argued that computing the optimal cost for getting each tile into its position and summing the distances will not give an admissible heuristic. However, Manhattan distance is doing the same thing--except in an abstract space. How come it is admissible?
1.1*****ADDED NEW (By EDITING BLOG POST)**********
[INTERACTIONS and Heuristics]
The reason we said we can't just add up true costs of putting individual tiles in the right position
is that the tiles have interactions. There are really *two* kinds of interactions
Positive interactions--getting one tile to its position makes it easier to get another tile to its position
Negative interactions--getting one tile to its position makes it *harder* to get another tile to its position.
How do positive and negative interactions affect the informedness and admissibility of the heuristics that *ignore* them?
2. The pattern we considered in the class was left and bottom edges. If instead we considerd the two diagonals of the goal position, will the resulting pattern database heuristic make sense?
3. Suppose there is a new 24-puzzle competition. You are all supposed to use the same hardware (computer memory etc) to solve
test instances optimally. Whoever solves the problem in the shortest time gets a prize (a "platinum-coated 24-puzzle, suitable for framing").
Before the competition starts however, everyone is given about 3 hours of time on the computer for any pre-computation. You want to use the pattern database heuristics, but you know that you don't quite have all the time needed to compute the pattern heuristic for all the possible states in the three hours. Is there any way you can use the precomputation time gainfully?
4. In the problem above, suppose for each team, they allowed two computers during pre-computation time. This obviously suggests the idea that you can compute two different pattern databases (say the left and bottom edges in one, and the right and top edges in the other). Can you imagine a way of using both the databases to improve search further?