algorithm - A-star是否保证给出二维网格中的最短路径

Question

我正在使用 A-star 算法，其中我有一个二维网格和一些障碍物。现在，我只有垂直和水平障碍物，但它们可以密集变化。

现在，A-star 效果很好(即大多数情况下找到的最短路径)，但如果我尝试从左上角到达右下角，那么我有时会看到，路径不是最短的，即有是路径上有些笨拙。

路径似乎偏离了最短路径应该是什么。

下面是我正在用我的算法做的事情。我从源头开始，一边向外移动，一边计算邻居的值，对于源头距离+目标距离，我一直选择最小的单元格，一直重复，直到遇到的单元格是目的地，此时我停止。

我的问题是，为什么A-star不保证给我最短路径。或者是吗？我做错了什么？

谢谢。

Answer 1

A-star 保证根据您的度量函数提供最短路径(不一定像鸟儿一样飞)，前提是您的启发式算法是“可接受的”，这意味着它永远不会高估剩余距离。

检查此链接:http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

为了帮助确定您的实现错误，我们需要有关您的指标和启发式方法的详细信息。

更新:
OP 的度量函数对于正交移动是 10，对于对角线移动是 14。

OP 的启发式只考虑正交移动，因此是“ Not Acceptable ”；它通过忽略更便宜的对角线移动而高估了。

过于保守的启发式算法的唯一代价是在找到最小路径之前访问了额外的节点；过于激进的启发式算法的代价是可能返回非最佳路径。 OP 应该使用以下启发式:

        7 * (deltaX + deltaY)

这略微低估了直接对角线路径的可能性，因此也应该是高性能的。

更新 #2:
要真正发挥性能，这已接近最佳状态，同时仍然非常快:

7 * min(deltaX,deltaY) + 10 * ( max(deltaX,deltaY) - min(deltaX,deltaY) )

更新 #3:
上面的 7 来自 14/2，其中 14 是指标中的对角线成本。

只有您的启发式更改；该指标是“业务规则”并驱动所有其余部分。如果您对六边形网格的 A-star 感兴趣，请在此处查看我的项目:http://hexgridutilities.codeplex.com/

更新 #4(关于性能):
我对 A-star 的印象是它在 O(N^2) 性能区域和几乎 O(N) 性能区域之间摇摆不定。但这非常依赖于网格或图形、障碍物放置以及起点和终点，因此很难一概而论。对于已知特定形状或风格的网格和图形，有多种更有效的算法，但它们通常也变得更加复杂； TANSTAAFL。