A* 搜尋演算法

核心公式

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

$g(n)$：從起點到節點 n 的實際成本
$h(n)$：從節點 n 到目標的估計成本（啟發函數）
$f(n)$：穿過節點 n 的總估計成本（$g + h$）

🔥 Vibe Prompt

"用 Pygame 建立 A* 視覺化工具：30x30 網格，點擊設定起點/終點/障礙物。動畫展示搜尋過程（探索節點綠色，最終路徑紅色）。"

啟發函數 (Heuristic Functions)

| 類型 | 公式 | 適用場景 | |:----:|:----:|---------| | 曼哈頓距離 | $|x_1-x_2| + |y_1-y_2|$ | 四方向網格地圖 | | 歐幾里得距離 | $\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$ | 自由移動 | | 切比雪夫距離 | $\max(|x_1-x_2|,|y_1-y_2|)$ | 八方向網格地圖 |

啟發函數的選擇關鍵

| 條件 | 結果 | |:----:|:----:| | $h(n) = 0$ | A* 退化為 Dijkstra（無啟發） | | $h(n) \leq \text{實際成本}$ | A* 保證找到最短路徑（可容許） | | $h(n) = \text{實際成本}$ | A* 直接走最佳路徑（完美啟發） | | $h(n) > \text{實際成本}$ | A* 更快但不保證最短路徑 |

A* vs Dijkstra 比較

| 比較 | Dijkstra | A* | |:----:|:--------:|:--:| | 探索範圍 | 全方位擴散 | 朝目標方向收斂 | | 時間複雜度 | $O(V^2)$ 或 $O(E \log V)$ | 通常比 Dijkstra 快 $10\times$ | | 空間複雜度 | $O(V)$ | $O(V)$ | | 需要啟發函數 | ❌ 不需要 | ✅ 需要 | | 保證最短路徑 | ✅ 保證 | ✅ 保證（若 $h$ 可容許） | | 適用場景 | 無方向資訊的圖 | 有方向資訊的地圖/導航 |

Dijkstra 探索：          A* 探索：
● ● ● ● ● ● ●          ● ● ● ● ● ○ ○
● ● ● ● ● ● ●          ● ● ● ● ● ○ ○
● ● ● ● ● ● ●          ○ ● ● ● ● ○ ○
● ● ● ● ● ● ●          ○ ○ ● ● ● ○ ○
● ● ● ● ● ● ●          ○ ○ ○ ● ● ○ ○
● ● ● ● ● ● ●          ○ ○ ○ ○ ● ● ○
● ● ● ● ● ● ●          ○ ○ ○ ○ ○ ● ●
                         (集中朝目標方向)

完整實作

import heapq

def astar(grid, start, goal):
    """
    A* 路徑搜尋
    grid: 2D 陣列，0=可通行，1=障礙物
    start: (x, y) 起點
    goal: (x, y) 終點
    """
    def heuristic(a, b):
        # 曼哈頓距離（四方向網格）
        return abs(a[0]-b[0]) + abs(a[1]-b[1])
    
    # 優先佇列：(f_score, g_score, x, y)
    pq = [(0, 0, start[0], start[1])]
    g_score = {start: 0}
    came_from = {start: None}
    explored = []
    
    while pq:
        _, g, x, y = heapq.heappop(pq)
        current = (x, y)
        
        if current == goal:
            # 重建路徑
            path = []
            while current is not None:
                path.append(current)
                current = came_from[current]
            return list(reversed(path)), explored
        
        if g > g_score.get(current, float('inf')):
            continue
        
        explored.append(current)
        
        for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx, ny = x+dx, y+dy
            neighbor = (nx, ny)
            
            if 0 <= nx < len(grid[0]) and 0 <= ny < len(grid) and grid[ny][nx] == 0:
                tentative_g = g + 1
                
                if tentative_g < g_score.get(neighbor, float('inf')):
                    g_score[neighbor] = tentative_g
                    f = tentative_g + heuristic(neighbor, goal)
                    heapq.heappush(pq, (f, tentative_g, nx, ny))
                    came_from[neighbor] = current
    
    return None, explored  # 找不到路徑

# 測試
if __name__ == "__main__":
    # 建立 10x10 網格，中央有障礙物
    grid = [[0]*10 for _ in range(10)]
    for i in range(3, 7):
        grid[5][i] = 1  # 障礙物牆
    
    start = (1, 5)
    goal = (8, 5)
    
    path, explored = astar(grid, start, goal)
    
    if path:
        print(f"找到路徑！共 {len(path)} 步")
        print(f"探索了 {len(explored)} 個節點")
        
        # 視覺化
        for y in range(len(grid)):
            row = ""
            for x in range(len(grid[y])):
                if (x, y) == start:
                    row += "S "
                elif (x, y) == goal:
                    row += "G "
                elif (x, y) in path:
                    row += "* "
                elif grid[y][x] == 1:
                    row += "# "
                elif (x, y) in explored:
                    row += ". "
                else:
                    row += "  "
            print(row)
    else:
        print("無法找到路徑！")

時間複雜度分析

| 變數 | 意義 | |:----:|------| | $V$ | 節點數量（網格大小） | | $E$ | 邊數量（每個節點 $\approx 4$） | | $b$ | 分支因子（平均每個節點的鄰居數） | | $d$ | 最短路徑的深度 |

| 演算法 | 時間複雜度 | 空間複雜度 | |:------:|:----------:|:----------:| | BFS | $O(V + E)$ | $O(V)$ | | Dijkstra | $O(E \log V)$ | $O(V)$ | | A* | $O(E \log V)$（實務上快 $10\times$） | $O(V)$ | | IDA* | $O(b^d)$ | $O(d)$（迭代加深） |

A* 在理論上與 Dijkstra 同為 $O(E \log V)$，但啟發函數讓它大幅減少實際探索的節點數。

A* 的實際應用

| 領域 | 應用範例 | |:----:|---------| | 🎮 遊戲 AI | NPC 路徑導航、尋路系統 | | 🗺️ 地圖導航 | Google Maps 路徑規劃 | | 🤖 機器人 | 自主移動機器人路徑規劃 | | 🏭 物流 | 倉儲機器人最佳路徑 | | 🌐 網路路由 | 資料封包最佳路徑選擇 |

常見優化技巧

| 技巧 | 效果 | |:----:|:----:| | 二元堆積 | 使用 heapq 取代陣列，大幅提升效率 | | 雙向 A* | 從起點與終點同時搜尋，減少探索範圍 | | 跳躍點搜尋 (JPS) | 在網格地圖上跳過不需要探索的節點 | | 層級 A* (HPA*) | 將地圖分層，先規劃高層再細化低層 | | 加權 A* | $f = g + w \cdot h$，$w > 1$ 更快但不保證最佳 |

關鍵要點

✅ A* 的核心：$f(n) = g(n) + h(n)$，平衡已花費成本與估計剩餘成本
✅ 啟發函數 $h(n)$ 必須可容許（不高於實際成本）才能保證最短路徑
✅ 曼哈頓距離是網格地圖最常用的啟發函數
✅ A* 比 Dijkstra 快 $10\times$ 以上，因為它朝目標方向集中探索
✅ 優先佇列（heapq）是 A* 效率的關鍵
✅ 實際應用中可犧牲最佳性換取速度（加權 A*）

A* 的實戰關鍵：啟發式函式的選擇

A* 的效能取決於 h(n) 的品質。不同的啟發式函式會產生截然不同的搜尋行為：

| 啟發式 | 公式 | 特性 | 找到最短路徑？ | |:------|:----|:----|:-------------| | 曼哈頓距離 | $|dx| + |dy|$ | 四方向移動標準 | ✅ 可採納 | | 歐幾里得距離 | $\sqrt{dx^2 + dy^2}$ | 任意方向 | ✅ 可採納 | | 對角線距離 | $\max(dx, dy)$ | 八方向移動 | ✅ 可採納 | | 零啟發式 | $h(n) = 0$ | 退化為 Dijkstra | ✅ 但很慢 |

在遊戲開發中的應用

遊戲中的 NPC 尋路通常使用 A* + 導航網格（NavMesh）：

將地圖轉換為圖（節點 = 可行走區域）
用 A* 找最短路徑
加上平滑化（路徑簡化）讓移動看起來自然

下一章預告：路徑規劃 API

這章你學會了 A* 的原理和實作。下一章將把它包裝成一個地圖導航 API——用 FastAPI 建立路徑規劃服務，提供 RESTful endpoint 讓前端或其他服務呼叫。