[Thinking cap topic for 9/12]: Pattern databases etc.

["Subbarao Kambhampati" <rao@asu.edu>]

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.. 
         
http://rakaposhi.eas.asu.edu/f06-cse471-mailarchive/msg00023.html

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? 

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? 

--------------