爲什麼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 *一樣好。