8-puzzle: hamming and manahttan heuristic consider “blank space”?
-
29-05-2021 - |
Question
I've a very simple question.
I'm working on 8-puzzle (8 numbers(from 1 to 8) + blank(=0) )
When calculating hamming distance (numbers in wrong position) and manhattan distance (distance horizontal+vertical between start and final position) should I consider "blank" space to calculate the result ?
For example..
|7 2 4|
|5 _ 6|
|8 3 1|
with goal state
|_ 1 2|
|3 4 5|
|6 7 8|
What's correct?
- Hamming distance = 8 (every number not in place) or 9 (also 0 = blank is considered)
- Manhattan distance (distance(7),distance(2),distance(4),...) = 3 (=1+2) + 1 (=1+0) + 2 (1+1) + 2 (2+0) + 0 (blank) + 3 (1+2) + 2 (2+0) + 3 (1+2) + 3 (2+1) --> without considering blank is 18 , with blank (+2) is 20. What's correct?
Thank you
Solution
If you want the heuristic to be admissible, then you shouldn't count blank tile in.
for example
|1 _ 2|
|3 4 5|
|6 7 8|
the real answer is 1, but manhattan distance is 2, if you count the blank tile. That can't be the admissible heuristic.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow