algorithm - 曼哈顿距离如何成为一种可接受的启发式算法？

Question

当计算 1 个方 block 的移动数时，是否可以导致其他方 block 达到其目标状态，这不是真的吗？因此，对每个图 block 进行计数可以为我们提供比达到目标状态所需的最少步数更多的计数？

这个问题是在 15-Puzzle 的曼哈顿距离的背景下进行的。

这是换句话说的问题:

我们能否使用曼哈顿距离作为 N-Puzzle 的可接受启发式算法。为实现 A* 搜索，我们需要一个可接受的启发式算法。曼哈顿启发式是候选人吗？如果是，你如何反驳上述论点(问题的前 3 句话)？

定义:A*是一种搜索算法。它使用启发式函数来确定到目标​​的估计距离。只要这个启发式函数永远不会高估到目标的距离，该算法就会找到最短路径，可能比广度优先搜索更快。满足该条件的启发式方法是可接受的。

Answer 1

可接受的启发式算法不得高估解决此问题的步数。由于您一次只能移动 1 个 block ，并且只能在 4 个方向中的一个方向移动，因此每个 block 的最佳场景是它有一条通向目标状态的清晰、畅通无阻的路径。这是 1 的医学博士。

一对 block 的其余状态是次优的，这意味着它将比 M.D. 采取更多的移动来将 block 放在正确的位置。因此，启发式永远不会高估并且是可以接受的。

当有人发布正确的正式版本时，我会删除。