曼哈顿距离如何成为可接受的启发式？
计算 1 个图块的移动次数是否会导致其他图块达到其目标状态，这不是真的吗？因此，对每个图块进行计数可以让我们得到的计数超过达到目标状态所需的最小移动次数？
这个问题是在 15-Puzzle 的曼哈顿距离的背景下进行的。
这是不同语言的问题：
我们可以使用曼哈顿距离作为 N-Puzzle 的可接受的启发式吗？为了实现 A* 搜索，我们需要一个可接受的启发式方法。曼哈顿启发式是候选者吗？如果是，您如何反驳上述论点（问题中的前 3 句话）？
定义： A* 是一种搜索算法。它使用启发式函数来确定距目标的估计距离。只要这个启发式函数永远不会高估到目标的距离，算法就会找到最短路径，可能比广度优先搜索更快。满足该条件的启发式是可接受的。
Ain't it true that while counting the moves for 1 tile can lead to other tiles getting to their goal state? And hence counting for each tile can give us a count more than the minimum moves required to reach the goal state?
This question is in context of Manhattan distance for 15-Puzzle.
Here is the Question in different words:
Can we use Manhattan distance as an admissible heuristic for N-Puzzle. To implement A* search we need an admissible heuristic. Is Manhattan heuristic a candidate? If yes, how do you counter the above argument (the first 3 sentences in the question)?
Definitions: A* is a kind of search algorithm. It uses a heuristic function to determine the estimated distance to the goal. As long as this heuristic function never overestimates the distance to the goal, the algorithm will find the shortest path, probably faster than breadth-first search would. A heuristic that satisfies that condition is admissible.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
可接受的启发法不得高估解决该问题的步数。由于您一次只能移动 1 个块，并且只能向 4 个方向之一移动，因此每个块的最佳场景是它有一条清晰、畅通无阻的路径到达其目标状态。这是 MD 为 1。
一对块的其余状态不是最优的，这意味着它将比 MD 需要更多的移动才能使块到达正确的位置。因此，启发式永远不会高估并且是可接受的。
当有人发布正确、正式的版本时，我会删除。
Admissable heuristics must not overestimate the number of moves to solve this problem. Since you can only move the blocks 1 at a time and in only one of 4 directions, the optimal scenario for each block is that it has a clear, unobstructed path to its goal state. This is a M.D. of 1.
The rest of the states for a pair of blocks is sub-optimal, meaning it will take more moves than the M.D. to get the block in the right place. Thus, the heuristic never over-estimate and is admissible.
I will delete when someone posts a correct, formal version of this.
形式证明：
根据 h 的定义，如果 s* 是目标状态，则 h(s*) = 0。假设通过反证法证明
则 C* < h(s0) 对于某些初始状态 s0。请注意，由于每个动作都可以移动
只有一个图块，执行一个动作最多可以将 h 减一。既然目标可以
在 C* 动作中达到，我们有 h(s*) ≥ h(s0) − C* > 0，这给我们带来了
矛盾，因为 h(s*) 应该为零。因此，对于所有的情况，我们必须有 h(s0) ≤ C*
s0，h 是允许的。
（来源：加州大学欧文分校）
Formal Proof:
By definition of h, h(s∗) = 0, if s∗ is the goal state. Assume for proof by contradiction
that C∗ < h(s0) for some initial state s0. Note that, since each action can move
only one tile, performing an action can at most reduce h by one. Since the goal can
be reached in C∗ actions, we have h(s∗) ≥ h(s0) − C∗ > 0, which brings us to a
contradiction since h(s∗) should be zero. Therefore, we must have h(s0) ≤ C∗ forall
s0, and h is admissible.
(Source: University of California, Irvine)