A *（星號）算法解釋

Question

我被要求研究對Dijkstra算法的改進。我一直在研究A星算法，但我發現許多解釋使用不熟悉的單詞和數學符號。

我明白星只考慮目標節點的邊緣。例如，如果將A Star算法應用於英國的公路網，並且目的地是鄧迪，並且我在倫敦開始，則只檢查北部邊界。

這是否至少是正確的？

Answer 1

A *使用啓發式來猜測節點到目標的最小成本。因此，在選擇節點時，不僅要分析從開始到該節點的成本，還要分析從節點到目標的可能成本。這允許忽略可能導致錯誤方向的路徑。

如果您示例中的啓發式使用節點的地理距離，那麼將首先檢查北部的道路（因爲它們的總體成本估計很小）。但是，在算法執行過程中，這些道路可能會從一開始就聚集一個非常大的實際距離（可能是因爲有很多曲線）。然後還可以檢查通往南方的道路。因此，如果這條路線比北方所有彎曲的道路（不考慮GB的實際路線圖）短，那麼可以往南走一點，然後直行。

啓發式的本質定義了算法的質量。如果啓發式給出了距離的下限（即不可能以比啓發式算法更便宜的成本到達目標），那麼路徑確實是最短的路徑。如果啓發式不是一個下界，也可以允許其他路徑（這可能是算法運行時間和路徑質量之間的折衷）。啓發式方法估計的最小成本越低，您將檢查的錯誤方向越少。即如果啓發式是恆定的，那麼最終會得到一個普通的Dijkstra算法。如果啓發式計算目標的實際成本，則只會遵循最短路徑，並且不會檢查其他節點。