A* 搜尋演算法：啟發式路徑規劃

Dijkstra 演算法雖然保證找到最短路徑，但它有一個缺點：它會向四面八方均等擴散，即使目標在正北方，它還是會花時間探索南方。

A (A-Star) 演算法在 Dijkstra 的基礎上加入了「啟發函數 (Heuristic Function)」，讓搜尋朝著目標方向前進*，大幅減少不必要的探索。

A* 的核心公式

A* 的評估函數由兩部分組成：

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

  • $g(n)$：從起點到當前節點 $n$ 的實際成本（同 Dijkstra）
  • $h(n)$：從當前節點 $n$ 到目標的估計成本（啟發函數）
  • $f(n)$：節點 $n$ 的總估計成本

A* 每次從 Priority Queue 中取出 $f(n)$ 最小的節點來探索，而不是像 Dijkstra 只看 $g(n)$。

啟發函數的選擇

啟發函數是 A* 的靈魂。好的啟發函數能讓搜尋極度高效，壞的啟發函數會讓 A* 退化成 Dijkstra。

常見的啟發函數

1. 曼哈頓距離 (Manhattan Distance) — 適合網格地圖（只能上下左右移動） $$h(n) = |x_1 - x_2| + |y_1 - y_2|$$

2. 歐幾里得距離 (Euclidean Distance) — 適合自由移動 $$h(n) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$

3. 對角線距離 (Diagonal Distance) — 適合可以斜角移動 $$h(n) = \max(|x_1 - x_2|, |y_1 - y_2|)$$

啟發函數的性質

  • 可採納 (Admissible)：$h(n)$ 永遠不高於實際成本 → 保證找到最短路徑
  • 一致 (Consistent)：$h(n) \leq c(n, n') + h(n')$ → 保證效率

實作 A* 演算法

import heapq
import math

def astar(grid, start, goal):
    """
    A* 路徑規劃
    grid: 2D 陣列，0 = 可通行，1 = 障礙物
    start: (x, y) 起點
    goal: (x, y) 終點
    """
    height = len(grid)
    width = len(grid[0])
    
    def heuristic(a, b):
        """曼哈頓距離啟發函數"""
        return abs(a[0] - b[0]) + abs(a[1] - b[1])
    
    # 優先佇列: (f值, g值, x, y)
    pq = [(0, 0, start[0], start[1])]
    
    # 已知最佳 g 值
    g_score = {start: 0}
    
    # 路徑記錄
    came_from = {start: None}
    
    # 探索記錄（用於視覺化）
    explored = []
    
    while pq:
        f, 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 < width and 0 <= ny < height 
                and grid[ny][nx] == 0):
                
                tentative_g = g + 1  # 每一步成本為 1
                
                if tentative_g < g_score.get(neighbor, float('inf')):
                    g_score[neighbor] = tentative_g
                    f_score = tentative_g + heuristic(neighbor, goal)
                    heapq.heappush(pq, (f_score, tentative_g, nx, ny))
                    came_from[neighbor] = current
    
    return None, explored  # 找不到路徑

測試與比較

# === 建立測試地圖 ===
# 0 = 通道, 1 = 障礙物
maze = [
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 1, 1, 1, 0, 1, 0, 1, 1, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 1, 1, 1, 1, 0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 1, 1, 1, 0, 1, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
]

start = (0, 0)
goal = (9, 9)

# 執行 A*
path, explored = astar(maze, start, goal)

print(f"A* 搜尋結果:")
print(f"  探索節點數: {len(explored)}")
print(f"  路徑長度: {len(path)} 步" if path else "  找不到路徑!")
print(f"  路徑: {path[:10]}..." if len(path) > 10 else f"  路徑: {path}")

A* vs Dijkstra 效能比較

def dijkstra_grid(grid, start, goal):
    """Dijkstra 在網格上的實作（不使用啟發函數）"""
    height = len(grid)
    width = len(grid[0])
    
    pq = [(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 < width and 0 <= ny < height and grid[ny][nx] == 0):
                tentative_g = g + 1
                if tentative_g < g_score.get(neighbor, float('inf')):
                    g_score[neighbor] = tentative_g
                    heapq.heappush(pq, (tentative_g, nx, ny))
                    came_from[neighbor] = current
    
    return None, explored

# 比較
astar_path, astar_explored = astar(maze, start, goal)
dijkstra_path, dijkstra_explored = dijkstra_grid(maze, start, goal)

print(f"\n=== 效能比較 ===")
print(f"A* 探索節點數:       {len(astar_explored)}")
print(f"Dijkstra 探索節點數: {len(dijkstra_explored)}")
print(f"效率提升:            {len(dijkstra_explored) / len(astar_explored):.1f}x")
print(f"\nA* 路徑長度:       {len(astar_path)}")
print(f"Dijkstra 路徑長度: {len(dijkstra_path)}")

視覺化 A* 搜尋過程

import matplotlib.pyplot as plt
import numpy as np

# 將地圖轉為 numpy 陣列
grid_array = np.array(maze)

plt.figure(figsize=(12, 5))

# 左圖：A* 探索區域
plt.subplot(1, 2, 1)
plt.imshow(grid_array, cmap='gray_r', alpha=0.7)

# 畫出探索區域
for x, y in astar_explored:
    plt.plot(x, y, 'y.', alpha=0.3, markersize=3)

# 畫出路徑
if astar_path:
    path_x = [p[0] for p in astar_path]
    path_y = [p[1] for p in astar_path]
    plt.plot(path_x, path_y, 'b-', linewidth=3, label='A* 路徑')

plt.plot(start[0], start[1], 'go', markersize=12, label='起點')
plt.plot(goal[0], goal[1], 'ro', markersize=12, label='終點')
plt.title(f'A* 搜尋 (探索 {len(astar_explored)} 節點)')
plt.legend()
plt.grid(True, alpha=0.3)

# 右圖：Dijkstra 探索區域
plt.subplot(1, 2, 2)
plt.imshow(grid_array, cmap='gray_r', alpha=0.7)

for x, y in dijkstra_explored:
    plt.plot(x, y, 'y.', alpha=0.3, markersize=3)

if dijkstra_path:
    path_x = [p[0] for p in dijkstra_path]
    path_y = [p[1] for p in dijkstra_path]
    plt.plot(path_x, path_y, 'b-', linewidth=3, label='Dijkstra 路徑')

plt.plot(start[0], start[1], 'go', markersize=12, label='起點')
plt.plot(goal[0], goal[1], 'ro', markersize=12, label='終點')
plt.title(f'Dijkstra 搜尋 (探索 {len(dijkstra_explored)} 節點)')
plt.legend()
plt.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

實戰：使用 OSMnx 從 OpenStreetMap 抓取真實地圖

pip install osmnx

import osmnx as ox

# 下載台北市大安區的道路網路
place_name = "Da'an District, Taipei, Taiwan"
G = ox.graph_from_place(place_name, network_type='drive')

print(f"圖形資訊:")
print(f"  節點: {len(G.nodes)}")
print(f"  邊: {len(G.edges)}")

# 找出最接近兩個地址的節點
origin_point = (25.0260, 121.5430)  # 大安森林公園附近
target_point = (25.0340, 121.5640)  # 忠孝復興附近

origin_node = ox.distance.nearest_nodes(G, origin_point[1], origin_point[0])
target_node = ox.distance.nearest_nodes(G, target_point[1], target_point[0])

print(f"\n起點節點: {origin_node}")
print(f"終點節點: {target_node}")

# 使用 NetworkX 的 A* 實作
path = nx.astar_path(G, origin_node, target_node, weight='length')
path_length = nx.astar_path_length(G, origin_node, target_node, weight='length')

print(f"A* 最短路徑長度: {path_length:.0f} 公尺 ({path_length/1000:.2f} 公里)")

# 視覺化
fig, ax = ox.plot_graph_route(G, path, node_size=0, route_color='red',
                             route_linewidth=4, bgcolor='black',
                             figsize=(12, 12))
plt.title(f"台北市大安區 A* 路徑規劃 ({path_length/1000:.2f}km)")
plt.show()

使用 Vibe Coding 實作 A*

🔥 【A 詠唱範例】* 「請幫我建立一個 A* 路徑規劃視覺化工具： 1. 使用 Pygame 繪製 30x30 網格地圖。 2. 使用者點擊設定起點、終點與障礙物。 3. 實作 A* 演算法（可選曼哈頓/歐幾里得/對角線啟發函數）。 4. 動畫展示探索過程（綠色=已探索，紅色=最短路徑）。 5. 顯示搜尋統計：探索節點數、路徑長度、執行時間。 6. 支援儲存/載入地圖。」

本日總結

在本章中，你學到了：

  1. ✅ A 核心思想*：f(n) = g(n) + h(n)，結合實際成本與啟發估計
  2. ✅ 啟發函數：曼哈頓、歐幾里得、對角線距離的選擇
  3. ✅ A 實作*：使用 Priority Queue 的完整程式碼
  4. ✅ Dijkstra vs A*：啟發函數讓搜尋效率提升數倍
  5. ✅ 真實地圖資料：使用 OSMnx 從 OpenStreetMap 抓取道路網路
  6. ✅ 視覺化：比較兩種演算法的探索範圍差異

下一章，我們將把路徑規劃技術整合到網頁應用中！

解鎖完整教學內容

本章為付費內容。加入專案即可解鎖超過 5000 字的深度解析，包含 10 個以上神級 Prompt 與真實 Source Code 範例！

💳 查看付費方案 (NT$ 99)已經購買了？點此登入