(Day 25) A* 搜尋演算法 (A-star Search)

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