为什么A*比Dijkstra的算法跑得更快？
维基百科说A*在O(E)中运行，其中E是图中的边数。但我的朋友说a*只是Dijkstra算法的一般情况，而Dijkstra算法运行在O(E+V log V）中。所以我很困惑为什么A*比Dijkstra的算法跑得更快。
共有1个答案
我认为维基百科上列出的a*的时间复杂度是不正确的（或者至少是误导性的）。那个时间复杂度似乎只计算搜索中扩展的状态数，而不是确定要探索哪些状态所需的时间。
为了提高效率，a*搜索需要存储一个优先级队列，其中包含需要探索的边缘节点，并且它必须能够在这些优先级上调用reduce-key。如果使用良好的优先级队列实现，则在最坏的情况下，运行时为O(nlogn+m)。因此，在最坏的情况下，您会期望a*降级为Dijkstra的算法。给出一个好的启发式，a*不会像Dijkstra算法那样扩展出所有的节点和边，这是a*更快的主要原因。
当然，a*搜索的时间复杂度需要考虑计算启发式的成本。一些复杂的启发式可能无法在O(1)时间内计算，在这种情况下A*的运行时间实际上可能比Dijkstra的算法更差。
希望这有帮助！
-
我一直试图理解Dijkstra算法的内在原理，以找到加权图的最短路径。 在访问一个顶点后，为什么我们必须将相邻顶点存储到优先级队列而不是普通队列中？ 我问上述问题的原因是：我知道使用PriorityQueue，我们可以从队列中获得最大/最小的数字。但是在Dijkstra算法的情况下，我们无论如何都会访问所有的顶点，而不管距离/优先级如何。在这种情况下，为什么我们需要使用具有O（log N）复杂度的
-
2）在火花中： 同样的，在Spark中需要30秒，在Python中需要1秒。 我的Spark比纯Python慢得多的几个可能原因：
-
问题内容： 我试图实施Miller- Rabin素数测试 ，并且对为什么中型数字（〜7位数字）花费如此长时间（> 20秒）感到困惑。我最终发现以下代码行是问题的根源： （其中，和都是相似的，但不相等的中号，是幂运算符，并且是模运算符） 然后，我尝试将其替换为以下内容： 相比之下，它几乎是瞬时的。 对于上下文，这是原始功能： 定时计算示例： 输出（与PyPy 1.9.0一起运行）： 输出（在Pyth
-
本文向大家介绍什么是A*算法？相关面试题，主要包含被问及什么是A*算法？时的应答技巧和注意事项，需要的朋友参考一下 个人感觉类似最佳优先算法，都是维护一个优先队列或堆，将结点按照某个值优先的情况放进去，不同的是这次需要一个估计函数h(n) 算法思想：对于优先队列，每取出一个结点n，将他的所有儿子结点n'放入优先队列，优先级由函数f(n)计算出 g(n)：起点到结点n的代价 h(n)：结点n到终点的
-
我有一个数组。我想对它们进行排序并删除重复项。这个答案建议使用和进行这种操作。运算的顺序不应该改变结果，所以我测量了计算的时间。 是什么使一个比另一个快？还有，有没有更快的办法呢？
-
我想学习更多关于图和Dijkstra算法的知识，所以我有一个函数，可以随机生成加权无向图，保存在如下文件中： 然后我运行Dijkstra，输出从节点0到所有其他节点的距离，但有时从节点0到其他节点的距离是0，这意味着从节点0到该节点没有连接<我还有另一个问题，Dijkstra的作品是什么样的？