我正在使用 A-star 算法，其中有一个 2D 网格和一些障碍。现在，我只有垂直和水平障碍物，但它们可能变化很大。
现在，A-star 运行良好（即大多数情况下找到的最短路径），但如果我尝试从左上角到达右下角，那么我有时会看到，路径不是最短的，即有些笨拙在路径中。
路径似乎偏离了最短路径应该是什么。
现在这就是我正在用我的算法做的事情。我从源开始，在计算邻居值的同时向外移动，对于到源的距离+到目的地的距离，我不断选择最小的单元格，并不断重复，直到我遇到的单元格是目的地，此时我停止。
我的问题是，为什么A-star不能保证给我最短路径。或者是吗？我做错了什么？
谢谢。
A-star 保证根据您的度量函数提供最短路径（不一定是“鸟飞翔”），前提是您的启发式是“可接受的”，这意味着它永远不会高估剩余距离。
检查此链接：http ://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
为了帮助确定您的实施错误，我们将需要有关您的指标和启发式的详细信息。
更新：
OP 的度量函数对于正交移动是 10，对于对角线移动是 14。
OP 的启发式只考虑正交移动，因此是“不可接受的”；它通过忽略更便宜的对角线移动而高估了。
过于保守的启发式的唯一代价是在找到最小路径之前访问了额外的节点；过度激进的启发式方法的代价是可能返回的非最优路径。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) 性能区域之间交错。但这太依赖于网格或图形、障碍物的位置以及起点和终点，很难一概而论。对于已知特定形状或风格的网格和图形，有多种更有效的算法，但它们通常也会变得更复杂；坦斯塔夫。
我确定你做错了什么（也许是一些实现缺陷，你的 A* 想法听起来是正确的）。A* 保证给出最短路径，可以用数学证明。
查看此wiki 页面将为您提供解决问题的所有信息。
不
A* 是最快的探路者算法之一，但它不一定给出最短路径。如果您正在寻找随着时间推移的正确性，那么最好使用 dijkstra 算法。