algorithm - 在这个修改过的 n-puzzle 中，曼哈顿距离仍然是一个可接受的启发式方法吗？

Question

我使用 A* 算法成功地实现了一个 8 谜题求解器，现在我对其进行了改动：谜题中可能有多个空白区域，并且瓷砖上的数字不再是唯一的（可能有是相同的）。

虽然算法在我修改它以生成所有空白空间的后继状态后有效，但它并没有以尽可能少的移动数解决游戏（因为当我试图解决它时，我实际上想出了更少的移动数手，惊喜！）

问题：在这个谜题中，曼哈顿距离仍然是一个可行的启发式方法吗？如果不是，启发式可能是什么？

Answer 1

是的，这个问题的可接受启发式可能涉及曼哈顿距离。

最简单的方法就是将曼哈顿距离与每个图块的可能最近的目标位置相距。

这显然是可以接受的，因为与忽略所有障碍物直接移动到最近的位置相比，不可能采取更少的移动来更快地到达任何位置。

但是我们可以做得更好——对于目标位置为 1 和 2 的两个相同的图块 A 和 B，我们可以计算所有可能的图块分配到位置的距离，而不是计算到每个最近的块的距离，所以：

min(dist(A,1) + dist(B,2), dist(A,2) + dist(B,1))

这可以推广到任意数量的图块，但请记住，对于n相同的图块，存在n!这样的可能性，因此快速计算会变得非常昂贵。

了解为什么这是可接受的仍然相当容易 - 因为我们正在计算所有瓷砖到位置的分配的最短距离，所以实际最短距离不可能更小。