A*搜尋演算法

A*（讀作「A 星」）是一種在網路中尋找最短路線的更聰明的辦法——這個網路可以是地圖柵格、道路圖，或是電子遊戲關卡裡的方格。它的做法，是給戴克斯特拉演算法那種耐心的搜尋加上一種「方向感」。普通的戴克斯特拉演算法會像池塘裡的波紋一樣朝各個方向同等地向外探索，完全不知道目標在哪裡。A* 在每一步都會多問一句：從這裡到目標大約還有多遠？有了這個提示，它就會把搜尋向目標方向傾斜，而不是把力氣浪費在背離目標的亂走上，因此通常能快得多地到達目標，同時仍然找到一條真正最短的路徑。

對於每一個它要考慮的位置，A* 都會權衡兩個數字。第一個是從起點走到這裡已經實際花掉的代價——這和戴克斯特拉演算法記的帳是一樣的。第二個是一個估計值，叫做啟發值，表示從這裡到目標還剩多少代價；在柵格上，這往往就用直線距離或「橫平豎直」的街區距離來算，很容易得出。A* 把這兩個數加在一起，每次總是優先展開總和最小的那個位置。於是它會偏向那些既容易到達、又看起來離目的地近的位置，自然而然地把搜尋推向正確的方向。

需要注意的是，這個估計值絕不能高估真實的剩餘距離——它必須保持樂觀，永遠不能聲稱目標比實際更遠。只要啟發值始終這樣保持樂觀（專業說法叫「可採納的」），A* 就和戴克斯特拉演算法一樣，必定返回一條最短路徑，卻用少得多的搜尋量。事實上，如果你給 A* 一個永遠猜成零的啟發值，它就退化回了戴克斯特拉演算法——這也正是人們把 A* 形容為「戴克斯特拉加上一個好提示」的原因。