在计算 1 个图块的移动时，是否会导致其他图块达到其目标状态，这不是真的吗？因此，计算每个图块可以让我们获得比达到目标状态所需的最小移动次数更多的计数？
这个问题是在 15-Puzzle 的曼哈顿距离的背景下。
这是不同的问题：
我们可以使用曼哈顿距离作为 N-Puzzle 的可接受启发式算法吗？为了实现 A* 搜索，我们需要一个可接受的启发式算法。曼哈顿启发式是候选人吗？如果是，您如何反驳上述论点（问题的前 3 句话）？
定义： A*是一种搜索算法。它使用启发式函数来确定到目标的估计距离。只要这个启发式函数从不高估到目标的距离，算法就会找到最短路径，可能比广度优先搜索更快。满足该条件的启发式是可接受的。
可接受的启发式方法不能高估解决这个问题的移动次数。由于您一次只能在 4 个方向中的一个方向上移动块 1，因此每个块的最佳方案是它具有通向其目标状态的清晰、通畅的路径。这是 1 的 MD。
一对块的其余状态是次优的，这意味着它需要比 MD 更多的动作才能将块放在正确的位置。因此，启发式永远不会高估并且是可以接受的。
当有人发布正确的正式版本时，我将删除。
形式证明：根据 h 的定义，如果 s* 是目标状态，则 h(s*) = 0。假设对于某个初始状态 s0，C∗ < h(s0) 的矛盾证明。请注意，由于每个动作只能移动一个图块，因此执行一个动作最多可以将 h 减一。由于可以在 C∗ 动作中达到目标，因此我们有 h(s∗) ≥ h(s0) − C∗ > 0，这给我们带来了矛盾，因为 h(s∗) 应该为零。因此，对于所有 s0，我们必须有 h(s0) ≤ C∗，并且 h 是可接受的。（来源：加州大学欧文分校）