为什么A *比Dijkstra更快

Question

我知道这个问题已被问到，但它没有回答我的具体问题。 我明白Dijkstra算法和A *算法是如何工作的，而A *是Dijkstra的一般情况。

A *通常认为A *会更快找到解决方案，因为您使用启发式方法可以加快过程/减少有效的分支因子。

但我记得，为了使A *返回最优结果，您必须搜索所有成本低于目标成本的节点。这确保了最优性，并且据说不可能有更快的算法，因为A *查看等节点< =每个算法至少需要的目标成本。

但是迪杰斯特拉呢？它也仅支付节点< =目标成本，因为它在每一步都扩展了最小可能路径。

如果您为了确保最优性而扩展其他节点，A *启发式优点是什么？ 另外两种算法似乎有运行时的n log n个复杂

希望有人能清楚这件事:)

Answer 1

Dijkstra的算法不使用启发式功能扩展节点的前沿，它只寻找使到达与已经访问的节点直接连接的未访问节点的成本最小的路径，它将最终找到最短路径，但将不得不探索所有不直接连接到接收器的节点。 A *借助良好的启发式功能（必须是可接受的启发式：永远不会超过达到目标的成本）可以立即达到接收器始终扩展边界中的正确节点。因此，如果g(n)=cost to reach node n和h(n)=an admissible heuristic function我们得到f(n)=g(n)+h(n)评估函数由A *使用。相反，Dijkstra只知道它的边界并且忽略启发式信息，因此当启发式弱时它和A *一样好。