A* 搜尋演算法
A* 搜尋：夢想與現實的精密天平
演算法背後的故事：給「Shakey」一個大腦
20 世紀 60 年代末，史丹佛國際研究院 (SRI) 的研究人員正在研製 Shakey——世界上第一台能夠對自己的行動進行邏輯推理的通用移動機器人。Shakey 需要在充滿房間和走廊的複雜世界中移動。
當時已有的工具並不够用。Dijkstra 演算法太慢了——它像一個不斷擴張的圓圈一樣向所有方向探索，把大量的算力浪費在了那些遠離目標的路徑上。團隊成員（Peter Hart, Nils Nilsson, 和 Bertram Raphael）意識到：如果機器人知道目標在哪裡，它就應該利用這個「夢想」來引導自己的腳步。
她們將 Dijkstra 演算法的數學嚴謹性與一種「啟發式 (Heuristic)」——也就是有根據的猜測——結合在一起，創造了 A*。這是現代啟發式搜尋的誕生。
為什麼需要它？
想像你正從巴黎開車去柏林。
- Dijkstra 演算法會探索通往倫敦、馬賽甚至大西洋的路徑，僅僅因為她們離巴黎很「近」。
- *A 演算法**則會死死盯著柏林。她會優先考慮那些真正指向東方的道路。
在工程界，A* 是 遊戲 AI 和 GPS 導航 的首選，因為她極大地減少了電腦需要檢查的路徑數量。
演算法是如何「平衡」的
A* 演算法的秘密隱藏在一個簡潔而深刻的等式中：。
這個演算法就像一個行路人，時刻關注著兩件事：
- (現實)： 「從起點走到這裡，我已經花了多少成本？」 這是來自過去的硬數據。
- (夢想)： 「從這裡到終點，大概還剩多少路？」 這就是 啟發式估算 (Heuristic)。我們還不知道確切答案，所以我們優先用直線距離（鳥飛距離）來代替。
在每一步中，A* 不只是挑選「最近」的節點，而是挑選那個 現實 + 夢想 總和最低的節點。
如果夢想 () 為 0，它就退化成了 Dijkstra。如果夢想太大，它可能會對妳撒謊並找到一條爛路。但只要夢想是 「樂觀」的（即她永遠不會高估真實距離），A* 就保證能找到完美的捷徑，同時無視地圖上 90% 的無效區域。
工程決策：指南針的選擇
A* 是世界上最流行的路徑規劃演算法，但她需要一個 啟發式函式。選擇合適的函式是工程師最重要的任務：
- 歐幾里得距離： 適用於可以在任何方向移動的開放世界遊戲。
- 曼哈頓距離： 最適合城市網格或拼圖遊戲，因為妳只能上/下/左/右移動。
A* 是「聰明人」的選擇。她比 Dijkstra 快，比純粹的貪婪搜尋準。她是任何已知目的地系統的黃金標準。
實作參考 (Python)
import heapq
def a_star(graph, start, goal, heuristic):
# g_score: 從起點到當前節點的實際代價 (現實)
g_score = {node: float('inf') for node in graph}
g_score[start] = 0
# f_score: 現實 + 夢想 (預估的總代價)
f_score = {node: float('inf') for node in graph}
f_score[start] = heuristic(start, goal)
# 優先佇列儲存: (f_score, 節點ID)
pq = [(f_score[start], start)]
while pq:
_, current = heapq.heappop(pq)
if current == goal:
return g_score[goal] # 到達終點！
for neighbor, weight in graph[current].items():
# 計算如果走這條路，到達鄰居的代價
tentative_g = g_score[current] + weight
# 如果這條新路比之前記錄的任何路徑都要好
if tentative_g < g_score[neighbor]:
g_score[neighbor] = tentative_g
# 核心邏輯：現實 + 夢想
f_score[neighbor] = tentative_g + heuristic(neighbor, goal)
heapq.heappush(pq, (f_score[neighbor], neighbor))
return float('inf')
# 啟發式函式範例：曼哈頓距離
# def manhattan_dist(p1, p2):
# return abs(p1.x - p2.x) + abs(p1.y - p2.y)小結
A* 告訴我們，了解過去很重要，但對未來有遠見才能讓妳更高效。透過在腳下的重量與目標的方向之間取得平衡，A* 在現實世界的混亂中找到了那條最優的路。