A*在真实世界寻路中真的比Dijkstra好吗？

Question

A*在真实世界寻路中真的比Dijkstra好吗？

Han*_*nXu 21 algorithm a-star dijkstra

我正在开发一个寻路程序.据说理论上A*比Dijkstra好.事实上,后者是前者的特例.但是,在现实世界中进行测试时,我开始怀疑A*真的更好吗？

我使用纽约市的数据,从第9个DIMACS实施挑战 - 最短路径,其中给出了每个节点的纬度和经度.

当应用A*时,我需要使用Haversine公式计算两点之间的球面距离,该公式涉及sin,cos,arcsin,平方根.所有这些都非常耗时.

结果是,

使用Dijkstra:39.953 ms,扩展了256540个节点.

使用A*,108.475 ms,扩展255135个节点.

注意到在A*中,我们扩展了1405个节点.但是,计算启发式的时间远远超过保存的时间.

根据我的理解,原因在于,在一个非常大的实数图中,启发式的权重将非常小,并且可以忽略它的效果,而计算时间占主导地位.

Answer 1

Nie*_*jes 34

我认为你或多或少错过了A*的观点.它旨在成为一个非常高效的算法,部分是通过有意识地做更多的工作,但是使用廉价的启发式算法,并且当你使用极其准确的预测启发式加载它时,你会有点撕裂.

对于A*中的节点选择,您应该使用距离的近似值.简单地使用(latdiff ^ 2)+(lngdiff ^ 2)作为近似距离应该使您的算法比Dijkstra更高效,并且在任何现实世界场景中都不会给出更糟糕的结果.实际上,如果您使用Haversine正确计算所选节点上的行进距离,结果应该完全相同.只需使用便宜的算法来选择潜在的下一次遍历.

作为我自己的答案的一个小小的补充:请注意,我甚至不建议采用近似距离的平方根 - 这是CPU的不必要的负担,因为你需要的是相对距离,而不是绝对距离,所以为了比较它就像可用. (5认同)
除此之外,所有A*需要启发式的是它永远不会高估距离.因此,对于启发式,使用欧几里德距离将完全[可接受](http://en.wikipedia.org/wiki/Admissible_heuristic). (4认同)
@Niels不会将"不精确"与"启发式"混合在一起.A*可以100%准确(对于我使用graphhopper的实验更快)如果启发式是可以接受的! (3认同)
@Niels:为了让A*启发式可以接受,它绝不能高估到目标的距离.你提出的启发式算法(dx ^ x + dy ^ 2)经常*会高估距离,除非你采用平方根 - 所以如果你使用那个函数作为你的启发式,你不再能保证找到最佳解决方案. (2认同)

Answer 2

Ann*_*sum 11

A*可以通过设置一些平凡的参数来简化为Dijkstra.Dijkstra有三种可能的改进方式:

使用的启发式是不正确的:它不是所谓的允许启发式.A*应该使用一种启发式算法,它不会高估与目标的距离,作为其成本函数的一部分.
启发式算法太昂贵了.
真实世界的图形结构很特殊.

在后者的情况下,你应该尝试建立现有的研究,例如Abraham等人的"公路维度,最短路径和可证明的高效算法".

Answer 3

Sha*_*baz 9

像宇宙中的其他一切一样,还有一个权衡.你可以采用dijkstra的算法来精确计算启发式算法,但那会失败的目的不是吗？

A*是一个很好的算法,因为它让你倾向于有一个基本的想法,即首先扩展哪个方向.也就是说,你应该保持启发式尽可能简单,因为你需要的只是一个大方向.

事实上,不是基于实际数据的更精确的几何计算并不一定能为您提供更好的方向.只要它们不是基于数据,所有这些启发式方法都只能给出一个方向,它们都是正确的.

归档时间：	12 年，7 月前
查看次数：	6648 次
最近记录：	9 年，6 月前