使用曼哈顿距离或欧几里得距离的A*算法用于迷宫求解？

Question

我已经通过图像处理获取了迷宫的所有可能路径。现在，我想使用A*算法来找到迷宫的最短路径。然而，我不确定欧几里得距离还是曼哈顿距离会更好作为启发式函数。这取决于迷宫类型还是启发式函数的选择与迷宫类型无关？对于以下可能的路径，哪种距离（曼哈顿或欧几里得）会是一个好选择？为什么？请建议。

附注：如果您有参考资料，请添加。这将是有帮助的。

- Ruby Shrestha

---

我使用欧几里得和曼哈顿距离作为A*算法中的启发式算法，实现了最短路径查找。但是，两者都没有给出好的结果。我想自动生成启发式算法，有什么可能的选择吗？感谢您的帮助。请给出建议。 - Curious

Answer 1

启发式算法的目标是为寻路器提供上下文信息。这些信息越准确，寻路器就能越高效。

要得到一个好的启发式算法，你需要满足两个相互矛盾的要求，但这很好，因为这意味着存在一个最佳平衡点。这两个要求如下：

• 一个启发式算法必须是可接受的，也就是说，它不应该高估距离。否则，算法会失效并返回不是最优的路径。
• 一个启发式算法应该返回尽可能大的距离。如果一个启发式算法低估了从一个单元格到目标的剩余距离，那么它会更倾向于选择这个单元格，而不是其他更好的单元格。

当然，最优的启发式算法将返回精确的、正确的长度（通常是不可达到的或者与其目的相悖）, 因为它不能返回更长的路径而不再是可接受的。

---

在您的情况下，看起来您正在处理4连通网格。在这种情况下，曼哈顿距离将是比欧几里得距离更好的度量标准，因为欧几里得距离会低估所有位移的成本与曼哈顿相比（由于毕达哥拉斯定理）。

如果没有比“图形是4连通网格”更多的知识，那么曼哈顿距离就没有更好的度量标准了。但是，如果您能够获得更多的数据（障碍密度，“高速公路”等），那么您可能能够设计出更好的启发式方法-尽管保持它可接受性将是一个非常困难的问题。

---

编辑 细看一下，似乎你在左下角有倾斜的顶点。如果是这样的话，你不在一个4连通图中，那么你必须使用欧几里得距离，因为曼哈顿距离不可行。

- MrBrushy

Answer 2

你的英雄有哪些可用移动方式不清楚。你的图表是否类似于象棋棋盘上的矩形网格，并且可以像国王一样在一个步骤中对角线移动？如果是的话，切比雪夫距离是最佳选择https://en.wikipedia.org/wiki/Chebyshev_distance。否则使用欧几里得距离。如果您想要最优路径，则不能在此处使用曼哈顿算法，因为曼哈顿启发式搜索在对角线路线上不可采用（它高估了它们），因此可能导致次优路径。

- Timur Nurmagambetov