为什么A*比Dijkstra的算法运行得更快？

Question

维基百科说A*在O(| E |)中运行,其中| E | 是图中边的数量.但是我的朋友说A*只是Dijkstra算法的一般情况,而Dijkstra的算法在O(| E | + | V | log | V |)中运行.所以我很困惑为什么A*跑得比Dijkstra算法快.

Answer 1

我认为维基百科上列出的A*的时间复杂度是不正确的(或者至少是误导性的).那个时间复杂性似乎只计算在搜索中扩展的状态数,而不是确定要探索哪些状态所需的时间.

为了提高效率,A*搜索需要存储一个优先级队列,该队列包含需要探索边缘的哪些节点,并且必须能够在这些优先级上调用reduce-key.在最坏的情况下,如果使用良好的优先级队列实现,则运行时间为O(n log n + m).因此,在最坏的情况下,你会期望A*降级为Dijkstra的算法.鉴于良好的启发式算法,A*不会扩展Dijkstra算法的所有节点和边缘,这是A*更快的主要原因.

当然,A*搜索的时间复杂度需要考虑计算启发式的成本.一些复杂的启发式方法可能无法在时间O(1)中计算,在这种情况下,A*的运行时实际上可能比Dijkstra的算法更差.

希望这可以帮助!