algorithm - 明星搜索：曼哈顿距离是否超过了 8 拼图的缺失瓷砖数量？

Question

考虑 8-puzzle 的三种启发式方法：

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

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

我想知道总曼哈顿距离的启发式函数是否总是超过错位瓷砖的数量？

标签： algorithma-starheuristicssearch-tree

Answer 1

是的，因为只有当所有错放的瓷砖都在正确的位置旁边时（即曼哈顿距离 = 1），您才会得到相同的值。在所有其他情况下，错位瓷砖的曼哈顿距离 > 1。