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

Question

计算一个方块的步数是否会导致其他方块到达它们的目标状态？因此，计算每个方块可能会给出比到达目标状态所需的最小步数更多的步数？

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

换句话说：我们可以将曼哈顿距离用作N-Puzzle的可行启发式吗？要实现A*搜索，我们需要一种可行的启发式方法。曼哈顿启发式方法是一个候选吗？如果是，那么您如何反驳上述论点（问题中的前三句话）？

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

- Akhil

---

能否提供更多关于问题的背景信息？根据具体问题，曼哈顿距离可能是完全可接受的，也可能完全不可接受。 - templatetypedef

曼哈顿距离是一种用于衡量距离或工作的度量标准，而不是问题的类别。请描述该问题。 - San Jacinto

@San 这个问题是关于 http://en.wikipedia.org/wiki/Fifteen_puzzle 的。 - Dr. belisarius

@belisarius: 在A*搜索中，“可接受的启发式”是指一种估计你距离目标有多近的方法，它永远不会高估距离。这保证了找到最短（或最少成本）路径。虽然需要一些特定术语的知识，但这是一个真正的问题，并应该重新开放。 - David Thornley

@David：现在已经重新开放，并且重新标记，以便具有必要知识的人可以找到它。对于具有必要知识的人来说，这个问题一开始就大部分是清晰的，尽管最好一开始提供一个指向维基百科15拼图的链接（或者对其进行描述）。 - Ken Bloom

Answer 1

可接受的启发式方法不能高估解决此问题所需的移动次数。由于您每次只能将块移动1次，并且只有4个方向可用，每个块的最佳情况是它具有通往其目标状态的明确无误的路径。这是MD值为1。

对于一对块的其余状态都是次优的，意味着获得正确位置需要比MD值更多的移动次数。因此，该启发式方法永远不会高估，是可接受的。

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

- San Jacinto

---

我明白了！对于我的表达不够清楚，我很抱歉。这可能是因为我没有充分考虑到我所面临的疑问。 - Akhil

Answer 2

正式证明: 根据h的定义，如果s∗是目标状态，则h(s∗) = 0。假设有某个初始状态s0，使得C∗ < h(s0)，以反证法进行证明。注意，由于每个动作只能移动一个方块，执行动作最多只能将h减少一次。由于可以在C∗个动作中到达目标状态，我们有h(s∗) ≥ h(s0) − C∗ > 0，这带来了矛盾，因为h(s∗)应该为零。因此，对于所有s0，我们必须有h(s0) ≤ C∗，并且h是可接受的。 （来源：加州大学欧文分校）

- Menezes Sousa

---

感谢加州大学欧文分校。 - Abdullah

抱歉，我想重新激活这个旧帖子。我只是想问一下你是如何得出这个结论的：h(s∗) ≥ h(s0) − C∗ - Donald

@Donald 假设您从s0沿着一条路径移动并进行C步。您的启发式值只能减少C，因此该路径的任何终点sf的启发式值永远不会低于h(s0) - C，即h(sf) ≥ h(s0) - C。然而，可能的终点之一是s，因此h(s) ≥ h(s0) - C，根据假设大于0。因此，我们有h(s) > 0，这是一个矛盾，证明完成。 - Peiffap