明星搜索：曼哈顿距离是否比 8 拼图的缺失拼图数量更重要？

Question

考虑 8 拼图的三个启发式算法：

 h1(n) = number of misplaced tiles
 h2(n) = total Manhattan distance
 h3(n) = max(h1, h2)

在一个 8 拼图中，我正在执行不同的拼图并注意到 h3 启发式函数 (max) 似乎提供与总曼哈顿距离启发式相同的解决方案。这是使用A星搜索算法。

我想知道曼哈顿总距离的启发式函数是否总是支配错位图块的数量？

Answer 1

是的，因为只有当所有错放的图块都紧挨着它们正确的位置（即曼哈顿距离 = 1）时，您才会得到相同的值。在所有其他情况下，错误放置的图块的曼哈顿距离 > 1。