8-puzzle: hamming and manahttan heuristic consider "blank space"?
hamming-distance, heuristics
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.
Problem
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