A* (A-Star)演算法實作
A* (A-Star)是一種啟發式搜尋演算法，除了最短距離，還會考慮目標的估計距離（啟發式函數）。
實作步驟
- 定義地圖和啟發式函數。
- 初始化開放節點（Open Set）和已訪問節點（Closed Set）。
- 計算代價函數
f(n) = g(n) + h(n)： - g(n)：起點到當前節點的實際距離。
- h(n)：當前節點到目標的估計距離。
- 重複尋找最小代價路徑，直到找到目標或無法到達。
程式碼
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不為空時，繼續處理。 - 每次處理時：
- 從 open_set 中取出代價最小的節點（heapq.heappop 保證最小堆結構）。
- 如果當前節點是目標節點，則回溯並返回路徑。
- 否則，更新相鄰節點的距離和父節點。
(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:{}
步驟
- 處理節點 A：
- 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')]
- 處理節點 C（
f(C)最小）： - 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')]
- 處理節點 D（已到目標）：
- 回溯路徑：D -> C -> B -> A
7. 最終輸出
最短路徑：
Shortest path using A* from A to D: ['A', 'B', 'C', 'D']
此結果是基於 g(n) 和 h(n) 綜合考慮後的最佳路徑。
