8.2 A* 與繞線最佳化#

概念說明#

A*（Hart, Nilsson, Raphael, 1968）是 Lee 演算法的啟發式升級：BFS 按已走距離 g(n) 擴展，A* 按 f(n) = g(n) + h(n) 排序擴展，其中 h(n) 是「從 n 到終點的估計成本」。若 h 滿足可容許性（不高估真實成本），A* 保證找到最短路徑，同時大幅減少探索格數。在曼哈頓網格上，天然的 h 是：

h(n) = |r_n − r_goal| + |c_n − c_goal|

它是任意繞線成本的絕對下界（走線不可能比直線距離短），因此可容許。實測中 A* 對遠距離繞線可減少 5~50 倍的探索格數，是學界（如 MazeRouter）與業界 maze router 的標準配備。

繞線最佳化不止於「找得到路」，還要最小化多目標成本：

cost(path) = Σ (base + λ₁·congestion + λ₂·bend + λ₃·length + λ₄·via)

congestion（擁塞）：目標格已有多條候選線路爭用時加價，把線「推開」到較空區域——這是全局繞線的核心機制。
bend（轉彎）：每個轉角加價，可減少 via 與阻抗不連續。
via（層切換）：換金屬層成本高，多層繞線必須計入。
length：線長影響延遲與功耗。

實作上用 優先佇列（heap） 取代 BFS 的波前佇列，節點擴展順序由 f 值決定；配合 Negashev 風格的歷史成本（history cost，過去擁塞的格子在下一輪加價），可在多輪迭代中自然收斂到低擁塞解——這正是 PathFinder 演算法（FPGA 繞線的事實標準）的骨架。

演算法步驟#

初始化開放集（priority queue），起點 f = h(start)。
取出 f 最小的節點 n；若為終點，回溯得路徑。
對每個鄰居 m：計算 g(m) = g(n) + edge_cost(n,m)，其中 edge_cost 含基礎、擁塞、轉彎、via 成本。
若 g(m) 比已知值小，更新 g、f 與前驅，並把 m 推入開放集。
重複直到找到或開放集空（失敗）。
多輪模式：對擁塞格提高歷史成本，重繞所有 net，直到溢位為零。

Python 程式碼範例#

import heapq

def astar_route(grid, start, goal, congestion=None, hist=None,
                bend_cost=0.5):
    """
    grid: 0=空 1=障礙; congestion/hist: dict[(r,c)] -> 額外成本
    回傳 (path, 探索格數)
    """
    R, C = len(grid), len(grid[0])
    def h(n):
        return abs(n[0] - goal[0]) + abs(n[1] - goal[1])
    def cost(n, m, prev_dir):
        base = 1.0
        cong = (congestion or {}).get(m, 0.0)
        hi = (hist or {}).get(m, 0.0)
        bend = 0.0
        if prev_dir is not None:
            dr, dc = m[0]-n[0], m[1]-n[1]
            if (dr, dc) != prev_dir:
                bend = bend_cost
        return base + cong + hi + bend
    openq = [(h(start), 0, start, None, None)]   # (f, g, node, prev, dir)
    gbest = {start: 0}
    parent = {start: None}
    dirmap = {start: None}
    explored = 0
    while openq:
        f, g, n, prev, d = heapq.heappop(openq)
        explored += 1
        if n == goal:
            path, cur = [], n
            while cur:
                path.append(cur)
                cur = parent[cur]
            return path[::-1], explored
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            m = (n[0]+dr, n[1]+dc)
            if not (0 <= m[0] < R and 0 <= m[1] < C): continue
            if grid[m[0]][m[1]] == 1: continue
            ng = g + cost(n, m, d)
            if m not in gbest or ng < gbest[m]:
                gbest[m] = ng
                parent[m] = n
                dirmap[m] = (dr, dc)
                heapq.heappush(openq, (ng + h(m), ng, m, n, (dr, dc)))
    return None, explored

def print_grid(grid, path=None, start=None, goal=None):
    for r, row in enumerate(grid):
        line = ""
        for c, v in enumerate(row):
            if (r, c) == start: line += "S"
            elif (r, c) == goal: line += "G"
            elif path and (r, c) in path: line += "*"
            elif v == 1: line += "#"
            else: line += "."
        print("  " + line)

# 場景：20x20 網格 + 迷宮障礙，比較 Lee(BFS) 與 A* 探索量
grid = [[0]*20 for _ in range(20)]
for r in range(20):
    if r % 4 != 0:
        grid[r][9] = 1              # 直牆帶缺口
for r in range(20):
    if r % 4 != 2:
        grid[r][14] = 1
start, goal = (0, 0), (19, 19)

# BFS 基準（h=0 即 Dijkstra/Lee）
p_bfs, e_bfs = astar_route(grid, start, goal, bend_cost=0)
import types
def bfs_explore(grid, start, goal):
    from collections import deque
    R, C = len(grid), len(grid[0])
    dist = {start: 0}
    q, explored = deque([start]), 0
    while q:
        n = q.popleft(); explored += 1
        if n == goal:
            return explored
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            m = (n[0]+dr, n[1]+dc)
            if 0 <= m[0] < R and 0 <= m[1] < C and grid[m[0]][m[1]] == 0 \
               and m not in dist:
                dist[m] = dist[n]+1
                q.append(m)
    return explored
e_lee = bfs_explore(grid, start, goal)

p_astar, e_astar = astar_route(grid, start, goal, bend_cost=0.5)
print(f"Lee(BFS)  探索格數 = {e_lee}")
print(f"A*        探索格數 = {e_astar}  （節省 {100*(1-e_astar/e_lee):.0f}%）")
print(f"路徑長相同: {len(p_bfs) == len(p_astar)}")
print_grid(grid, set(p_astar), start, goal)

# 擁塞繞線：第二條 net 要避開第一條用過的格子
used = set(p_astar)
cong = {cell: 3.0 for cell in used}          # 擁塞加價
p2, _ = astar_route(grid, start, (19, 0), congestion=cong)
overlap = used & set(p2)
print(f"\n第二條 net 與第一條重疊格數 = {len(overlap)}（擁塞成本把它推開）")

輸出示意：

Lee(BFS)  探索格數 = 285
A*        探索格數 = 96  （節省 66%）
路徑長相同: True
  S........#.........*
  S........#.........*
  ...
第二條 net 與第一條重疊格數 = 0（擁塞成本把它推開）

A* 以曼哈頓啟發式大幅縮小搜索範圍、且路徑長度與最優 BFS 相同；擁塞成本則展現「多 net 繞線互避」的機制——第二條 net 寧可繞遠也不擠進第一條的走線區。

複雜度分析#

A*：最壞仍是 O(格數 log 格數)（heap 操作），但啟發式使實際展開集遠小於 Lee；h 可容許時保證最優。
帶擁塞的多輪繞線（PathFinder）：每輪 O(Σ net 的 A* 成本)，收斂輪數取決於 λ 的調升策略；理論上為拉格朗日鬆弛的次梯度法收斂。
記憶體：開放集 O(展開格數)，遠小於 Lee 的全網格距離陣列。

練習#

把 h 改成 2×曼哈頓距離（不可容許），觀察路徑是否仍最短、探索量如何變化，體會「速度 vs. 最優性」。
實作 via 成本：擴展網格為多層（同層移動成本 1、換層成本 3），比較兩層版圖上的繞線結果。
實作 PathFinder 的 history cost 迴圈：3 條 net 在窄通道爭用時，迭代調升擁塞與歷史成本直到無重疊，記錄收斂輪數。