4
$\begingroup$

I am trying to understand Pattern Databases for designing heuristics. I am reading Richard E. Korf's book Heuristic Search. One of its paragraphs says

The obvious heuristic for Rubik's Cube is a three dimensional version of the Manhattan distance. For each cubie, compute the minimum number of moves required to correctly position and orient it, and sum these values over all cubies.Unfortunately, to be admissible, this value has to be divided by 8, since every twist moves 8 cubies. A better heuristic is to take the maximum of the sum of Manhattan distances of the corner cubies, divided by four, and the maximum of the sum of edge cubies divided by 4. The expected value of the Manhattan distance of the edge cubies is 22/4=5.5, while the corresponding values for the corner cubies is 12.333/4 that's approximately equal to 3.08 partly because there are 12 edge cubies, but only eight corner cubes.

My question is why taking the maximum of the sum of Manhattan distances for corner cubies divided by four and the maximum of the sum of Manhattan distances for edge cubies divided by four is better heuristic than taking the sum of Manhattan distances divided by eight?

Besides, how do they get the expected values of 5.5 and 3.08?

$\endgroup$
  • $\begingroup$ An admissible heuristic is like a "Price is Right" estimate: try to get as close as you can, without going over. If you have two admissible heuristics for the same thing, then whichever one has an larger expected cost will be a better (more useful) heuristic, as on average it'll be getting closer to the true value -- you want your estimate to be as large as possible, without going over the true value. $\endgroup$ – D.W. Apr 8 '16 at 5:34
  • $\begingroup$ Also posted on SO. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Apr 10 '16 at 0:41
  • $\begingroup$ I'm voting to close this question because it was cross-posted on Stack Overflow, and cross-posting isn't permitted. $\endgroup$ – D.W. Apr 10 '16 at 0:43