Dijkstra 和 A* 最短路徑

該部落格上撰寫的文章是出於教學目的而創建的。 另外，文章中的資訊可能不正確，請謹慎。

如果每個區塊的行動成本不同，僅靠簡單的 BFS 無法保證最便宜的路線。 這時候就用到了Dijkstra、A*等最短路徑演算法。

Dijkstra

從起點到現在累計成本最低的頂點首先進行擴展。

新成本 = 目前成本 + 下一條幹線成本

如果新的成本低於舊的記錄
更新距離和先前的頂點。

使用優先權佇列時，一般O((V + E) log V)可以執行到這個程度。 不應使用預設的 Dijkstra，因為負邊的存在可能會減少已建立的最短距離。

A*

A* 是從起點算起的實際成本g以及達到目標的預計成本。h新增以確定優先順序。

f(n) = g(n) + h(n)

在網格中，曼哈頓距離或歐幾裡得距離可以用作啟發式。 對於六角網格，必須使用適合六角座標的距離函數。

如果估計成本沒有高估實際的最低剩餘成本，則可以確保最短路徑。 如果 Heuristic 為 0，A* 的行為類似於 Dijkstra。

使用哪一個？

需要從一個起點出發的多個目的地成本：Dijkstra
快速導航至一個目的地：A*
所有中繼成本相同：BFS

路徑搜尋效能不僅由演算法名稱決定。 還必須檢查鄰居生成成本、障礙物表示、優先隊列和啟發式品質。