heuristics - 8 谜题：汉明和马纳坦启发式考虑“空白空间”？

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。什么是正确的？

谢谢

Answer 1

如果您希望启发式算法被接受，那么您不应该将空白瓷砖计入其中。

例如

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

真正的答案是 1，但曼哈顿距离是 2，如果你算上空白瓷砖的话。这不能是可接受的启发式方法。