A* 搜尋演算法

A 星搜尋演算法，簡稱「A*」，係電腦科學上一種常用嘅搵路用演算法。A 星搜尋演算法會攞一幅圖A* 搜尋演算法嘅做法係將個空間當做一幅有若干個節點嘅圖，喺每一步，個演算法會
Foreach 相鄰點計嗰個相鄰點嘅  值； 表示成本，數值係  同  嘅總和；
 表示由現時點去嗰個相鄰點要用嘅移動成本；
 係按某啲啟發法估計嘅「由嗰個相鄰點去最終點嘅成本」－例如如果最終點喺山頂，而望緊嗰個相鄰點位置低過現時點，按「盡可能喺高度上接近最終點」嘅啟發法，望緊嗰個相鄰點就會有高嘅  值；
然後個演算法會揀  值最低嗰點做下一個要去嘅點，唔好去經已去過嘅點，並且一路重複做上述嘅嘢，順利嘅話就會一路做到到達終點為止。迪卡斯特拉演算法係 A* 搜尋演算法嘅狹義化版，指  永遠等如 0 嘅 A* 搜尋演算法，即係話迪卡斯特拉演算法唔會嘗試估下一點有幾有利於最後去到終點。

虛擬碼 
A* 搜尋演算法可以用噉嘅虛擬碼表示：

初始化
  個程式有兩個 list，開放表同封閉表；
    // 開放表表示未去過嘅點，而封閉表表示去咗嘅點。
  將起點擺入去 open list；
  While open list 唔係空嘅，做...
    搵 open list 當中 f 值最低嘅點；
    將呢點變做現時點；
    將呢點擺入去 closed list； // 等個程式唔會返去經已去過嘅點。
    Foreach 由現時點去得到嘅點，
      if 嗰點喺 closed list 入面，忽略佢；
      if 呢點唔喺 open list 入面，將佢擺入去 open list；
      將現時點設做呢點嘅 parent；
      計呢點嘅 f 值；
      if 最終目的地入咗 closed list，終止運作； // 成功到咗目的地。
      if  open list 係空嘅，但又搵唔到目的地嗰點，終止運作； // 搵路失敗。
   將個演算法行過嗰條路線俾做 output。

計 h 

A* 同迪卡斯特拉演算法嘅分別在於 A* 會考慮  呢個數值。原則上， 可以用兩大方法計：
個演算法可以試吓計  嘅精確數值，即係例如考慮嗮所有由目標點去終點嘅可能路線，再計出  嘅最細可能數值；呢種做法有個明顯嘅缺點－噉做會消耗大量嘅運算資源，而且仲假設咗個演算法有能力鳥瞰噉睇嗮成幅地圖同埋事先知嗮每條路線嘅成本值。所以
喺實際應用上， 嘅數值通常會用某啲啟發法估計：啟發法係認知心理學上嘅一個概念，指人類或者人工智能思考嗰陣可以用嘅「認知捷徑」，即係一啲簡單、可以用嚟解難嘅法則，例如家陣個搵路演算法要由喺山腳嘅起點行去喺山頂嘅終點，一個可能嘅啟發法就可以係「盡可能行去高嘅點」。A* 演算法有多種啟發法可以用嚟估計  嘅數值，多數係靠計終點同望緊嗰點之間嘅距離，而「距離」嘅計法有幾種：
曼哈頓距離：想像兩個點之間嘅空間用格仔嚟代表，而假設一個個體淨係有得沿住啲格仔嘅邊線行嘅話，噉喺是但兩點之間穿梭都會有多條「最短路線」，呢啲路線嘅長度就係所謂嘅曼哈頓距離。喺二維空間嘅情況下，曼哈頓距離計法如下：
；當中  係指  嘅  座標值、 係指  嘅  座標值... 如此類推。
棋盤距離：指兩點之間最大座標差異，兩點之間嘅棋盤距離係指將兩點嘅同位座標相減所得嘅最大數值，條式如下：

歐幾里得距離：指兩點之間嘅直線距離，二維嘅歐幾里得距離計法如下：

搵路
迪卡斯特拉演算法
解迷宮演算法
D* 搜尋演算法
Theta*
任何角度路線計劃

參考文獻 
ilsson, N. J. (1980). Principles of Artificial Intelligence. Palo Alto, California: Tioga Publishing Company.

攷

拎 
Clear visual A* explanation, with advice and thoughts on path-finding.
Variation on A* called Hierarchical Path-Finding A* (HPA*).

搵路