A* 搜尋演算法

出自維基百科,自由嘅百科全書
展示 A* 搜尋演算法嘅動畫

A 星搜尋演算法粵拼A sing1 sau2 cam4 jin2 syun3 faat3英文A* search algorithm),簡稱「A*」,係電腦科學上一種常用嘅搵路演算法。A 星搜尋演算法會攞一幅(睇埋圖論)做輸入,並且運算出一條由指定起點去到指定終點嘅路線[1],喺廿世紀同廿一世紀初成日俾人用嚟教電子遊戲人工智能控制 NPC 喺遊戲世界入面移動[2][3]

A* 搜尋演算法嘅做法係將個空間當做一幅有若干個節點嘅圖,喺每一步,個演算法會

  • Foreach 相鄰點(可以由自己位置移去嘅地點)計嗰個相鄰點嘅 值; 表示成本(即係行去嗰點要嘥幾多時間精神等資源),數值係 嘅總和;
  • 表示由現時點去嗰個相鄰點要用嘅移動成本(時間同氣力等);
  • 係按某啲啟發法(heuristics)估計嘅「由嗰個相鄰點去最終點嘅成本」-例如如果最終點喺山頂,而望緊嗰個相鄰點位置低過現時點,按「盡可能喺高度上接近最終點」嘅啟發法,望緊嗰個相鄰點就會有高嘅 值;

然後個演算法會揀 值最低嗰點做下一個要去嘅點,唔好去經已去過嘅點,並且一路重複做上述嘅嘢,順利嘅話就會一路做到到達終點為止[2][4]迪卡斯特拉演算法(Dijkstra's algorithm)係 A* 搜尋演算法嘅狹義化版,指 永遠等如 0 嘅 A* 搜尋演算法,即係話迪卡斯特拉演算法唔會嘗試估下一點有幾有利於最後去到終點[5][6]

虛擬碼[編輯]

A* 搜尋演算法可以用噉嘅虛擬碼表示[2][7]

 初始化
 個程式有兩個 list,開放表(open list)同封閉表(closed 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* 會考慮 呢個數值。原則上, 可以用兩大方法計[7]

  • 個演算法可以試吓計 嘅精確數值,即係例如考慮嗮所有由目標點去終點嘅可能路線,再計出 嘅最細可能數值;呢種做法有個明顯嘅缺點-噉做會消耗大量嘅運算資源,而且仲假設咗個演算法有能力鳥瞰噉睇嗮成幅地圖同埋事先知嗮每條路線嘅成本值。所以
  • 喺實際應用上, 嘅數值通常會用某啲啟發法估計:啟發法係認知心理學上嘅一個概念,指人類或者人工智能思考嗰陣可以用嘅「認知捷徑」,即係一啲簡單(唔使做太大量嘅運算)、可以用嚟解難嘅法則,例如家陣個搵路演算法要由喺山腳嘅起點行去喺山頂嘅終點,一個可能嘅啟發法就可以係「盡可能行去高嘅點」( 嘅數值同望緊嗰點嘅高度成反比)。A* 演算法有多種啟發法可以用嚟估計 嘅數值,多數係靠計終點同望緊嗰點之間嘅距離,而「距離」嘅計法有幾種[8]
    • 曼哈頓距離(Manhattan distance,簡稱「MD」):想像兩個點之間嘅空間用格仔嚟代表,而假設一個個體淨係有得沿住啲格仔嘅邊線行(好似係一個喺曼哈頓揸車搵食嘅的士司機噉)嘅話,噉喺是但兩點(設呢兩點做 )之間穿梭都會有多條「最短路線」,呢啲路線嘅長度就係所謂嘅曼哈頓距離。喺二維空間嘅情況下,曼哈頓距離計法如下[9]
      ;當中 係指 座標值、 係指 座標值... 如此類推。
    • 棋盤距離(chessboard distance,):指兩點之間最大座標差異,兩點之間嘅棋盤距離係指將兩點嘅同位座標相減(兩點嘅 座標相減、兩點嘅 座標相減... 等等)所得嘅最大數值,條式如下[10]
    • 歐幾里得距離(Euclidean distance):指兩點之間嘅直線距離,二維嘅歐幾里得距離計法如下[8]

睇埋[編輯]

參考文獻[編輯]

  • ilsson, N. J. (1980). Principles of Artificial Intelligence. Palo Alto, California: Tioga Publishing Company.

[編輯]

  1. Zeng, W.; Church, R. L. (2009). "Finding shortest paths on real road networks: the case for A*". International Journal of Geographical Information Science. 23 (4): 531–543.
  2. 2.0 2.1 2.2 Zeng, W.; Church, R. L. (2009). "Finding shortest paths on real road networks: the case for A*". International Journal of Geographical Information Science. 23 (4): 531–543.
  3. Barnouti, N. H., Al-Dabbagh, S. S. M., & Naser, M. A. S. (2016). Pathfinding in strategy games and maze solving using A* search algorithm. Journal of Computer and Communications, 4(11), 15.
  4. Barnouti, N. H., Al-Dabbagh, S. S. M., & Naser, M. A. S. (2016). Pathfinding in strategy games and maze solving using A* search algorithm. Journal of Computer and Communications, 4(11), 15.
  5. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". Introduction to Algorithms (Second ed.). MIT Press and McGraw–Hill. pp. 595–601.
  6. Knuth, D.E. (1977). "A Generalization of Dijkstra's Algorithm". Information Processing Letters. 6 (1): 1–5.
  7. 7.0 7.1 A* Search Algorithm. GeeksforGeeks.
  8. 8.0 8.1 Euclidean vs Manhattan vs Chebyshev Distance.
  9. Black, Paul E. "Manhattan distance". Dictionary of Algorithms and Data Structures.
  10. Cyrus. D. Cantrell (2000). Modern Mathematical Methods for Physicists and Engineers. Cambridge University Press.

[編輯]