我正在开发一个寻路程序。理论上说A*优于Dijkstra。事实上，后者是前者的特例。但是，当在现实世界中进行测试时，我开始怀疑 A* 真的更好吗？
我使用了纽约市的数据，来自9th DIMACS Implementation Challenge - Shortest Paths，其中给出了每个节点的纬度和经度。
应用 A* 时，我需要使用Haversine Formula计算两点之间的球面距离，其中涉及 sin、cos、arcsin、平方根。所有这些都非常非常耗时。
结果是，
使用 Dijkstra：39.953 毫秒，扩展 256540 个节点。
使用 A*，108.475 毫秒，扩展 255135 个节点。
注意到在 A* 中，我们扩展了更少的 1405 个节点。然而，计算启发式的时间比节省的时间要多得多。
据我了解，原因是在一个非常大的实数图中，启发式的权重会非常小，它的影响可以忽略不计，而计算时间占主导地位。
I think you're more or less missing the point of A*. It is intended to be a very performant algorithm, partially by intentionally doing more work but with cheap heuristics, and you're kind of tearing that to bits when burdening it with a heavy extremely accurate prediction heuristic.
For node selection in A* you should just use an approximation of distance. Simply using (latdiff^2)+(lngdiff^2) as the approximated distance should make your algorithm much more performant than Dijkstra, and not give much worse results in any real world scenario. Actually the results should even be exactly the same if you do calculate the travelled distance on a selected node properly with the Haversine. Just use a cheap algorithm for selecting potential next traversals.
A*可以通过设置一些琐碎的参数来简化为 Dijkstra。在 Dijkstra 上没有改进的三种可能方式：
A*应该使用不会高估目标距离的启发式方法作为其成本函数的一部分。对于后者，您应该尝试建立在现有研究的基础上，例如Abraham 等人的“Highway Dimension, Shortest Paths, and Provably Efficient Algorithms”。
就像宇宙中的其他事物一样，需要权衡取舍。您可以使用 dijkstra 的算法来精确计算启发式，但这会破坏目的，不是吗？
A* 是一个很棒的算法，因为它让你倾向于目标，大致了解首先要扩展哪个方向。也就是说，您应该使启发式方法尽可能简单，因为您所需要的只是一个大方向。
事实上，不基于实际数据的更精确的几何计算并不一定能给你更好的方向。只要它们不基于数据，所有这些启发式方法都会为您提供一个同样（不）正确的方向。
一般来说，A* 比 Dijkstra 的性能更高，但它实际上取决于您在 A* 中使用的启发式函数。您需要一个乐观的 h(n) 并找到最低成本路径，h(n) 应该小于真实成本。如果 h(n) >= cost，那么您最终会遇到您所描述的情况。
你能发布你的启发式函数吗？
还要记住，这些算法的性能很大程度上取决于图的性质，这与启发式的准确性密切相关。
如果您在导航出迷宫时比较 Dijkstra 与 A*，其中每个段落对应于单个图形边缘，性能可能几乎没有差异。另一方面，如果图在“远”节点之间有许多边，则差异可能会非常显着。想象一个机器人（或人工智能控制的计算机游戏角色）在几乎开放的地形中导航，有一些障碍物。
我的观点是，尽管您使用的纽约数据集绝对是“真实世界”图的一个很好的例子，但它并不能代表所有真实世界的寻路问题。