A*搜揣演算法

A \ * 搜揣演算法（A \ * search algorithm）是一種佇圖形平面上，有真濟个節點的路徑，求出上低通過成本的演算法。定用於遊戲內底的 NPC 的移動計算，抑是網路的遊戲的 BOT 的移動計算上。

該演算法綜合了上良優先搜揣和 Dijkstra 演算法的優點：咧進行啟發式搜揣提懸演算法效率的同時，會當保證揣著一條最佳路徑（需要評估函式滿足單調性）。

在此演算法中，若以 $ g ( n ) $ 表示對起點到任意頂點 $ n $ 的實際距離，$ h ( n ) $ 表示任意頂點 $ n $ 到目標頂點的估算距離（根據所採用的評估函式的無仝而變化）， 遐爾 A \ * 演算法的估算函式為：

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

這个公式遵循以下特性：

• 若是 $ g ( n ) $ 為零，即只計算任意頂點 $ n $ 到目標的評估函式 $ h ( n ) $，若無計算起點到頂點 $ n $ 的距離，則演算法轉化為著使用貪心策略的上良優先搜揣，速度上緊咧，毋過可能著袂出最佳解；
• 若是 $ h ( n ) $ 無大於頂點 $ n $ 到目標頂點的實際距離，著愛一定會當求出最佳解，而且 $ h ( n ) $ 愈細，需要計算的節點愈濟，演算法效率愈低，常見的評估函式有—— 歐幾里著愛距離、曼哈頓距離、切比雪夫距離；
• 若是 $ h ( n ) $ 為零，即只需求出起點到任意頂點 $ n $ 的上短路徑 $ g ( n ) $，嘛無計算任何的評估函式 $ h ( n ) $，是轉化做短路問題，即 Dijkstra 演算法，現此時需要計算上濟的頂點；

相關連結

• 走路
• 闊度優先搜揣
• 深度優先搜揣

外部連結

• A \ * 演算法簡介 ( A \ * Algorithm Brief )