algorithm - 为什么 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 算法差。

希望这可以帮助！

Answer 2

从本质上讲，A* 更快，因为它可以使用启发式方法对哪条路线最好的情况做出更有根据的猜测，这是 Dijkstra 算法所没有的。