A* 搜尋演算法

出自維基百科,自由嘅百科全書
Jump to navigation Jump to search
展示 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。

睇埋[編輯]

參考文獻[編輯]

  • 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. A* Search Algorithm. GeeksforGeeks.

[編輯]