[Python] A*(A-Star) 演算法實作

A* (A-Star)演算法實作

A* (A-Star)是一種啟發式搜尋演算法，除了最短距離，還會考慮目標的估計距離（啟發式函數）。

實作步驟

1. 定義地圖和啟發式函數。
2. 初始化開放節點（Open Set）和已訪問節點（Closed Set）。
3. 計算代價函數 f(n) = g(n) + h(n)：
4. • g(n)：起點到當前節點的實際距離。
   • h(n)：當前節點到目標的估計距離。
4. 重複尋找最小代價路徑，直到找到目標或無法到達。

程式碼

import heapq

def a_star(graph, start, goal, heuristic):
    # 優先佇列 (open_set) 用於儲存需要探索的節點及其估計總代價 (f_score)
    # 初始包含起點，f_score 設為 0
    open_set = [(0, start)]  # (估計代價, 節點)
    
    # 字典 (came_from) 用於回溯路徑，儲存每個節點的父節點
    came_from = {}
    
    # 字典 (g_score) 儲存從起點到每個節點的實際距離，初始設為無限大
    # 起點的距離設為 0，表示起點到自身的距離為 0
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0
    
    while open_set:
        # 從 open_set 中取出代價最低的節點 (current_node)
        current_cost, current_node = heapq.heappop(open_set)
        
        # 如果已到達目標節點，回溯並返回完整路徑
        if current_node == goal:
            path = []  # 用於儲存最終路徑的列表
            while current_node:  # 回溯每個節點，從目標節點到起點
                path.append(current_node)
                current_node = came_from.get(current_node)  # 取得父節點
            return path[::-1]  # 反轉路徑順序，從起點到目標
        
        # 遍歷當前節點的所有鄰居 (neighbor)
        for neighbor, weight in graph[current_node].items():
            # 計算從起點到鄰居的臨時距離 (tentative_g_score)
            tentative_g_score = g_score[current_node] + weight
            
            # 如果新的距離小於已知的距離，更新資訊
            if tentative_g_score < g_score[neighbor]:
                # 更新鄰居的父節點為當前節點
                came_from[neighbor] = current_node
                # 更新鄰居的 g_score (實際距離)
                g_score[neighbor] = tentative_g_score
                # 計算鄰居的估計總代價 f_score
                f_score = tentative_g_score + heuristic[neighbor]
                # 將鄰居及其估計代價加入 open_set
                heapq.heappush(open_set, (f_score, neighbor))
    
    # 如果無法到達目標節點，返回 None
    return None  

# 啟發式函數 (heuristic)，估計從每個節點到目標節點的距離
heuristic = {
    'A': 7,  # 節點 A 到目標節點 D 的估計距離為 7
    'B': 6,  # 節點 B 到目標節點 D 的估計距離為 6
    'C': 2,  # 節點 C 到目標節點 D 的估計距離為 2
    'D': 1   # 節點 D 到自身 (目標) 的估計距離為 1
}

# 測試地圖 (graph)，以鄰接表表示每個節點及其相鄰節點的距離
graph = {
    'A': {'B': 1, 'C': 4},  # 節點 A 連接到 B (距離 1)，C (距離 4)
    'B': {'A': 1, 'C': 2, 'D': 5},  # 節點 B 連接到 A、C、D
    'C': {'A': 4, 'B': 2, 'D': 1},  # 節點 C 連接到 A、B、D
    'D': {'B': 5, 'C': 1}   # 節點 D 連接到 B、C
}

# 起點和目標節點
start_node = 'A'  # 起點節點 A
goal_node = 'D'   # 目標節點 D

# 執行 A* 演算法
path = a_star(graph, start_node, goal_node, heuristic)
print("Shortest path using A* from A to D:", path)

A 演算法輸出*

Shortest path using A* from A to D: ['A', 'B', 'C', 'D']

這段輸出是執行A * 演算法 後的結果，表示從起點節點 A 出發，到達其他節點（B、C、D）的最短距離。

1. a_star 函數簡介

這個函數用來執行 A* 演算法，計算從起點節點 start 到目標節點 goal 的最短路徑，並返回節點列表作為結果。

2. 主要變數和結構

輸入參數

• graph:
• • 表示地圖的鄰接表結構，包含節點及其相鄰節點的連線權重。
  • 格式：{'節點': {'鄰居1': 距離, '鄰居2': 距離}}
• start:
• • 起點節點名稱。
• goal:
• • 目標節點名稱。
• heuristic:
• • 啟發式函数，用於估算當前節點到目標節點的距离。

變數初始化

• open_set:
• • 優先佇列（用 heapq 實現），儲存目前需要探索的節點及其估計總代價（f(n)）。
  • 初始為起點 (0, start)，代價為 0。
• came_from:
• • 字典，儲存每個節點的父節點，用來回溯最短路徑。
• g_score:
• • 字典，儲存從起點到某節點的實際距離（g(n)）。
  • 初始設為無限大，起點距離設為 0。

3. 主要邏輯

(1) while open_set:

• 當 open_set 不為空時，繼續處理。
• 每次處理時：
• 1. 從 open_set 中取出代價最小的節點（heapq.heappop 保證最小堆結構）。
  2. 如果當前節點是目標節點，則回溯並返回路徑。
  3. 否則，更新相鄰節點的距離和父節點。

(2) 回溯路徑

當到達目標節點 goal 時：

• 初始化空列表 path。
• 從目標節點 goal 開始回溯 came_from，直到找到起點。
• 返回路徑（反轉順序 [::-1]）。

(3) 更新相鄰節點

• 對於當前節點的所有鄰居：
• • 計算臨時距離 tentative_g_score：

tentative_g_score = g_score[current_node] + weight

• • 如果新距離小於已知距離：更新 g_score[neighbor] 為新距離。更新 came_from[neighbor] 為當前節點。

計算估計總代價 f(n)：f(n)=g(n)+h(n)將鄰居及其代價加入 open_set。

4. 啟發式函數（heuristic）

啟發式函數估算當前節點到目標節點的距離：

• 範例中，直接提供每個節點到目標的距離作為估計值。
• heuristic = {'A': 7, 'B': 6, 'C': 2, 'D': 1}：
• • A 到 D 的估計距離是 7。
  • B 到 D 的估計距離是 6，依此類推。

5. 測試地圖解讀

圖結構（graph）表示節點及其相鄰關係：

A --(1)-- B --(5)-- D
 \       /  \       /
 (4)   (2)   (1)
  \   /       \
   C --------- D

• 節點：
• • A 連接到 B 和 C，權重分別是 1 和 4。
  • B 連接到 A、C 和 D，權重分別是 1、2 和 5。
  • C 連接到 A、B 和 D，權重分別是 4、2 和 1。
  • D 連接到 B 和 C，權重分別是 5 和 1。

6. 路徑計算流程

初始設定

• open_set: [(0, 'A')]
• g_score: {'A': 0, 'B': inf, 'C': inf, 'D': inf}
• came_from: {}

步驟

1. 處理節點 A：
2. • g(A) = 0, h(A) = 7, f(A) = 7
   • 鄰居：B：g(B) = 1, f(B) = 1 + 6 = 7C：g(C) = 4, f(C) = 4 + 2 = 6
   • 更新 open_set 為 [(6, 'C'), (7, 'B')]
2. 處理節點 C（f(C) 最小）：
3. • g(C) = 4, h(C) = 2, f(C) = 6
   • 鄰居：B：g(B) = 6，不更新（已有更小值）。D：g(D) = 5, f(D) = 5 + 1 = 6
   • 更新 open_set 為 [(6, 'D'), (7, 'B')]
3. 處理節點 D（已到目標）：
4. • 回溯路徑：D -> C -> B -> A

7. 最終輸出

最短路徑：

Shortest path using A* from A to D: ['A', 'B', 'C', 'D']

此結果是基於 g(n) 和 h(n) 綜合考慮後的最佳路徑。