曼哈顿距离在这个修改后的n中仍然是可接受的启发式

2018-06-23 09:14:44

我成功实现了一个使用A *算法的8难题求解器，现在我正在给它添加一个转折点：难题中可能有多个空白空间，并且拼图上的数字不再是唯一的（可能有数字是相同的）。

虽然该算法在修改后为所有空白空间生成后继状态后仍然有效，但它并未以最小的移动次数解决游戏（因为我试图通过更小的移动次数来解决这个问题）手，惊喜！）

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

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

最简单的方法就是将曼哈顿距离移动到每个瓦片最近的可能目标位置。

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

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

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

这可以概括为任意数量的切片，但请记住，对于n相同的切片，有n! 这样的可能性，所以计算得相当快就相当昂贵。

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

链接地址: http://www.djcxy.com/p/65567.html