Clever Geek Handbook

8-puzzle: hamming and manahttan heuristics count "white space"?

I have a very simple question.

I am working on an 8 puzzle (8 numbers (1 to 8) + blank (= 0))

When calculating the distance from clutter (numbers in the wrong position) and the distance in Manhattan (horizontal + vertical distance between start and end positions) should blank space be considered to calculate the result?

For example..

 |7 2 4|
 |5 _ 6|
 |8 3 1|

with target state

 |_ 1 2|
 |3 4 5|
 |6 7 8|

What is right?

  • Hamming distance = 8 (each number is out of place) or 9 (also considered 0 = empty)
  • Manhattan distance (distance (7), distance (2), distance (4), ...) = 3 (= 1 + 2) + 1 (= 1 + 0) + 2 (1 + 1) + 2 (2 + 0) + 0 (space) + 3 (1 + 2) + 2 (2 + 0) + 3 (1 + 2) + 3 (2 + 1) -> no space - 18, with space (+2) - 20 . What is right?

thank

+3


source to share


1 answer


If you want the heuristic to be valid, you shouldn't count an empty slab.

eg



|1 _ 2|  
|3 4 5|  
|6 7 8|

the real answer is 1, but the manhattan distance is 2 if you count blank tiles. This cannot be a valid heuristic.

+4


source






More articles:


All Articles