A-star算法在2D网格中是否保证给出最短路径？

Question

我正在使用A星算法，其中有一个2D网格和一些障碍物。现在，我只有垂直和水平的障碍物，但它们可能会变得很密集。

现在，A星算法效果不错（即对大多数情况找到了最短路径），但如果我尝试从左上角到达右下角，则有时会发现路径不是最短的，即路径存在某些不必要的绕路。

路径似乎偏离了最短路径。

现在这里是我用算法正在做的事情。我从源点开始，向外移动并计算邻居的值，计算距离源点+距离目标点的距离，选择最小的单元格，重复执行直到遇到的单元格是目标点，在此处停止。

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

谢谢。

- Kraken

Answer 1

A星算法可以保证根据您的度量函数（不一定是“鸟瞰图”），给出最短路径，前提是您选择的启发式函数是“可接受”的，也就是说不能高估剩余距离。请参考此链接：http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html。为了帮助确定实现错误，我们需要了解您的度量和启发式函数的详细信息。

更新：OP的度量函数为10（对于正交移动）和14（对于对角线移动）。OP的启发式函数仅考虑正交移动，因此是“不可接受的”，它低估了比较便宜的对角线移动。过于保守的启发式函数唯一的代价是在找到最小路径之前访问更多的节点；过于激进的启发式函数的代价是返回非最优路径。OP应该使用以下启发式函数：

        7 * (deltaX + deltaY)

这是对直接对角线路径可能性的一个非常轻微的低估，因此也应该具有良好的性能。

要真正挤出性能，这几乎是最优的选择，同时仍然非常快：

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

上面的7来自于度量中对角线成本14的导出。只有你的启发式改变了；度量是“商业规则”，驱动着其他所有东西。如果您对六边形网格的A-star感兴趣，请查看我在此处的项目：http://hexgridutilities.codeplex.com/。我的对A-star的印象是它在O(N^2)性能区域和几乎O(N)性能区域之间徘徊。但这取决于网格或图形、障碍物的放置以及起点和终点，很难概括。对于已知特定形状或特点的网格和图形，有各种更有效的算法，但它们也变得更加复杂；TANSTAAFL。

- Pieter Geerkens

---

你如何“测量”图形节点（或网格单元）之间的距离。 - Pieter Geerkens

@Pieter Geerkens fromSource=fromSourceOfParent+10（用于水平或垂直移动）；或14（用于斜向移动） fromDestination = 10 *（positiveDifference（destY，currentY）+ positiveDifference（destX，currentX））； - Kraken

@PieterGeerkens 加了张图片。通常我很擅长数学，但我不明白你是怎么得出7的。如果您能解释一下，那就太感谢了。非常感谢。 - Kraken

@K 7 = 14/2，这里我使用14是因为那是你的对角线成本。 - Pieter Geerkens

是的，只有您的启发式更改；您的度量标准是“业务规则”，并将其余所有内容都强制执行。如果您对六边形网格的A-tar感兴趣，请查看我的项目：http://hexgridutilities.codeplex.com/ - Pieter Geerkens

Answer 2

我相信你在做某些事情时出了问题（也许是一些实现上的缺陷，但你使用 A* 的想法听起来是正确的）。A* 算法保证可以找到最短路径，这可以通过数学证明。

查看这个维基页面将为你提供解决问题所需的所有信息。

- Sayakiss

Answer 3

不是的

A*是最快的寻路算法之一，但不一定能给出最短路径。如果你更注重正确性而非时间，则最好使用Dijkstra算法。

- Sandri

---

如果满足条件（即使用可接受的启发式算法），A*算法有保证地找到最短路径。 - seaotternerd

有了正确的启发式算法，A算法可以保证找到最短路径；如果启发式算法不好，则A算法仍然能够找到最短路径，但只是一种BFS算法；而如果使用不同的启发式算法，则A*算法可能会给出一条不保证是最短路径的路径。 - Sir Rogers