A* 搜尋演算法

展示 A* 搜尋演算法嘅動畫

A 星搜尋演算法粵拼A sing1 sau2 cam4 jin2 syun3 faat3英文A* search algorithm),簡稱「A*」,係電腦科學上一種常用嘅搵路演算法。A 星搜尋演算法會攞一個(睇埋圖論)做輸入,並且運算出一條由指定起點去到指定終點嘅路線[1],喺遊戲編程上可以攞嚟教人工智能探索遊戲空間[2]。個演算法用虛擬碼寫嘅話如下:

 設 P 做源頭,
 將 g、h 同 f 三個數值俾落 P 嗰度,
 g 代表由源頭去呢點嘅成本(包含兩點之間嘅路線嘅 g 嘅總和),h 代表由源頭去呢點嘅預計成本,而 f 代表 g 同 h 嘅總和(f = g + h),用嚟估計呢條路嘅總成本。
 將 P 加落去開放表open list)嗰度;
 重複以下步驟:
   搵開放表當中 f 值最低嘅點;
   將呢個點變做現時點;
   將呢個點加落去封閉表closed list)嗰度;
   Foreach 由現時點去得到嘅點,
     如果呢點喺封閉表入面,忽略佢。
     如果呢點唔喺開放表入面,加佢落開放表嗰度。
     將現時點設做呢個點嘅母點(parent)。
     計呢點嘅 g、h 同 f 值。
   如果目的地嗰點進入咗封閉點,終止運作(成功到咗目的地),又或者
   如果開放表係空嘅但又搵唔到目的地嗰點,終止運作(搵路失敗)。
 由個演算法行過嗰條路線俾做輸出。

睇埋

參考

  • 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. 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.