在前幾天，我們介紹了 Dijkstra、Bellman-Ford、Floyd-Warshall，這些都是經典的最短路徑演算法。今天要談的是 A* 搜尋演算法 (A-star Search) —— 一個結合最短路徑與啟發式 (Heuristic) 的演算法，在人工智慧 (AI)、遊戲與導航中應用極為廣泛

演算法背景

• 發表於 1968 年，Peter Hart, Nils Nilsson, Bertram Raphael
• 適用於 圖的最短路徑搜尋，尤其是在地圖、遊戲、路徑規劃等場景
• 結合了 Dijkstra 的「最短距離」思想 與 Greedy Best-First Search 的「啟發式」思想

核心思想

A* 的代價函數定義為:

$$
f(n) = g(n) + h(n)
$$

• $g(n)$: 從起點到節點 $n$ 的實際距離
• $h(n)$: 從節點 $n$ 到目標的「估計距離」(啟發式函數，Heuristic Function)
• $f(n)$: 綜合評估函數，用來決定搜尋順序

若 $h(n)$ 設為 0，A* 就會退化成 Dijkstra
若 $h(n)$ 選得合理，A* 就能更快收斂到目標

常見啟發式函數

• 曼哈頓距離 (Manhattan Distance):

  $$ h(n) = |x_1 - x_2| + |y_1 - y_2| $$
  適合只能上下左右移動的網格

• 歐式距離 (Euclidean Distance):

  $$ h(n) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} $$
  適合允許對角線移動的場景

• 切比雪夫距離 (Chebyshev Distance):

  $$ h(n) = \max(|x_1 - x_2|, |y_1 - y_2|) $$

  適合王棋走法 (上下左右斜角都能走)

程式範例

import heapq

def a_star(graph, start, goal, heuristic):
    # graph: adjacency list 格式 {u: [(v, cost), ...]}
    # start: 起點
    # goal: 目標點
    # heuristic: 啟發式函數 h(n)，估計節點 n 到目標的距離

    # open list（優先佇列），存放候選節點
    # 優先依照 f(n) = g(n) + h(n) 的值排序
    open_list = []
    heapq.heappush(open_list, (0, start))  # (f值, 節點)

    # g(n)：記錄從起點到每個節點的實際最短距離
    g = {node: float('inf') for node in graph}
    g[start] = 0

    # parent：紀錄路徑，方便最後回溯最短路徑
    parent = {start: None}

    while open_list:
        f, u = heapq.heappop(open_list)  # 選擇當前 f 值最小的節點

        # 如果到達目標，回溯重建路徑並回傳
        if u == goal:
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return path[::-1], g[goal]  # 回傳路徑與最短距離

        # 探索鄰居節點
        for v, cost in graph[u]:
            temp_g = g[u] + cost  # 嘗試經由 u 到達 v 的距離
            if temp_g < g[v]:  # 如果更短，則更新
                g[v] = temp_g
                f = g[v] + heuristic(v, goal)  # 計算 f(n) = g + h
                heapq.heappush(open_list, (f, v))
                parent[v] = u  # 更新路徑

    return None, float('inf')  # 若找不到路徑，回傳 None


# 測試範例
graph = {
    'A': [('B', 1), ('C', 3)],
    'B': [('D', 3), ('E', 1)],
    'C': [('F', 5)],
    'D': [('G', 2)],
    'E': [('G', 1)],
    'F': [('G', 2)],
    'G': []
}

# 啟發式函數（這裡簡化成 0，退化成 Dijkstra）
def h(node, goal): 
    return 0  

path, cost = a_star(graph, 'A', 'G', h)

print("最短路徑:", path)  # 最短路徑: ['A', 'B', 'E', 'G']
print("總成本:", cost)   # 總成本: 3

複雜度分析

• 時間複雜度
  • 與啟發式函數品質高度相關
  • 最壞情況：$O(E \log V)$ (類似 Dijkstra)
• 空間複雜度
  • $O(V)$，需存儲 open/closed 集合與路徑資訊

優缺點

結語

A* 演算法結合了 Dijkstra 的保證最短路徑 與 啟發式的高效率，是一個非常實用的搜尋演算法。它的威力取決於啟發式設計，若設計良好，A* 幾乎能「直奔目標」，大幅減少搜尋時間。

至此，我們完成了 最短路徑演算法四大金剛:

• Dijkstra: 非負權重的單源最短路徑
• Bellman-Ford: 處理負權重與檢測負環
• Floyd-Warshall: 所有點對最短路徑
• A*: 帶啟發式的高效路徑搜尋