明星搜索:曼哈顿距离是否主宰了8字谜的失踪瓷砖数量？

Question

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

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

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

我想知道曼哈顿总距离的启发式函数是否总是控制错放的瓷砖数量？

Answer 1

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