A* 搜尋：夢想與現實的精密天平

演算法背後的故事：給「Shakey」一個大腦

20 世紀 60 年代末，史丹佛國際研究院 (SRI) 的研究人員正在研製 Shakey——世界上第一台能夠對自己的行動進行邏輯推理的通用移動機器人。Shakey 需要在充滿房間和走廊的複雜世界中移動。

當時已有的工具並不够用。Dijkstra 演算法太慢了——它像一個不斷擴張的圓圈一樣向所有方向探索，把大量的算力浪費在了那些遠離目標的路徑上。團隊成員（Peter Hart, Nils Nilsson, 和 Bertram Raphael）意識到：如果機器人知道目標在哪裡，它就應該利用這個「夢想」來引導自己的腳步。

她們將 Dijkstra 演算法的數學嚴謹性與一種「啟發式 (Heuristic)」——也就是有根據的猜測——結合在一起，創造了 A*。這是現代啟發式搜尋的誕生。

為什麼需要它？

想像你正從巴黎開車去柏林。

• Dijkstra 演算法會探索通往倫敦、馬賽甚至大西洋的路徑，僅僅因為她們離巴黎很「近」。
• *A 演算法**則會死死盯著柏林。她會優先考慮那些真正指向東方的道路。

在工程界，A* 是 遊戲 AI 和 GPS 導航 的首選，因為她極大地減少了電腦需要檢查的路徑數量。

演算法是如何「平衡」的

A* 演算法的秘密隱藏在一個簡潔而深刻的等式中：$f(n) = g(n) + h(n)$。

這個演算法就像一個行路人，時刻關注著兩件事：

1. $g(n)$ (現實)： 「從起點走到這裡，我已經花了多少成本？」 這是來自過去的硬數據。
2. $h(n)$ (夢想)： 「從這裡到終點，大概還剩多少路？」 這就是 啟發式估算 (Heuristic)。我們還不知道確切答案，所以我們優先用直線距離（鳥飛距離）來代替。

在每一步中，A* 不只是挑選「最近」的節點，而是挑選那個 現實 + 夢想 總和最低的節點。

如果夢想 ($h$) 為 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* 在現實世界的混亂中找到了那條最優的路。