8-拼图: Hamming和Manhattan启发式算法是否考虑“空格”？

Question

我有一个非常简单的问题。

我正在处理8数码问题（8个数字（从1到8）+空白（= 0））

在计算汉明距离（数字在错误位置）和曼哈顿距离（起始位置和最终位置之间的水平+垂直距离）时，我是否应该考虑“空白”空间来计算结果？

例如...

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

目标状态

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

什么是正确的？

- 汉明距离 = 8（每个数字都不在正确位置）或 9（0=空白也被考虑在内） - 曼哈顿距离（distance(7),distance(2),distance(4),...）= 3 (=1+2) + 1 (=1+0) + 2 (1+1) + 2 (2+0) + 0 (空白) + 3 (1+2) + 2 (2+0) + 3 (1+2) + 3 (2+1) --> 不考虑空白的话，结果为18， 考虑空白的话 (+2)，结果为20。哪一个是正确的呢？

谢谢。

- dragonmnl

Answer 1

如果您希望该启发式搜索是可行的，那么就不应该计算空白方块。

例如：

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

真正的答案是1，但曼哈顿距离是2（如果算上空白块）。这不可能是一个可行的启发式函数。

- hsiu