8.1 迷宮繞線 Lee 演算法#

概念說明#

Lee 演算法（1961，貝爾實驗室）是繞線的開山之作，本質是 BFS 波前擴展（wavefront expansion）：把版圖切成網格，每格有成本（障礙 = ∞，金屬層、通道各有成本），從起點以同心圓方式向外擴散標記距離，直到抵達終點，再沿數字遞減回溯得到路徑。它保證：若存在路徑必能找到，且找到的是最短（最少成本）路徑——完備且最優，這是它至今仍在教學與小規模工具中存活的原因。

缺點同樣經典：BFS 探索的格子數與「起終點距離的平方」成正比，大版圖上記憶體與時間都吃不消；且每次只繞一條 net，先繞者占住資源，後繞者可能失敗（順序依賴），需要 rip-up & reroute（拆線重繞）輔助。

Lee 演算法的演進家族：

Soukup 演算法：波前擴展時偏向目標方向加速（不保證最短，但快很多）。
Hadlock 演算法：以「偏離曼哈頓方向的次數」為成本，保證最短且探索格數較少。
Maze routing with costs：為不同層/資源賦不同成本，可處理擁塞與設計規則近似。

Lee 的三階段：擴展（expansion）、回溯（retrace）、清理（clean-up，把路徑標記為障礙）。擴展時用兩個佇列交替（現在波前/下一波前），實現 BFS 的層次擴散。

演算法步驟#

初始化網格：障礙格（已用走線、元件）標記為不可用；起點距離 0。
擴展：維護當前波前佇列，取出格 g，對四鄰居若為空且未標記，標記 dist(g)+1 並加入下一波前。
重複直到終點被標記（找到）或佇列空（無路徑，回報失敗）。
回溯：從終點出發，每步找「標號恰好小 1」的鄰居，直到回到起點。
把路徑格標為障礙，處理下一條 net。

Python 程式碼範例#

from collections import deque

def lee_route(grid, start, goal):
    """
    grid: 2D list，0=空、1=障礙
    start, goal: (r, c)；回傳路徑或 None
    """
    R, C = len(grid), len(grid[0])
    if grid[goal[0]][goal[1]] == 1:
        return None
    dist = [[None] * C for _ in range(R)]
    dist[start[0]][start[1]] = 0
    cur, nxt = deque([start]), deque()
    depth = 0
    found = False
    while cur and not found:
        depth += 1
        while cur:
            r, c = cur.popleft()
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r+dr, c+dc
                if not (0 <= nr < R and 0 <= nc < C):
                    continue
                if grid[nr][nc] == 1 or dist[nr][nc] is not None:
                    continue
                dist[nr][nc] = depth
                if (nr, nc) == goal:
                    found = True
                    break
                nxt.append((nr, nc))
            if found:
                break
        cur, nxt = nxt, deque()
    if not found:
        return None
    # 回溯階段：沿遞減標號走回起點
    path, cell = [goal], goal
    d = dist[goal[0]][goal[1]]
    while cell != start:
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = cell[0]+dr, cell[1]+dc
            if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] == d - 1:
                path.append((nr, nc))
                cell = (nr, nc)
                d -= 1
                break
    return path[::-1]

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)

# 版圖：10x10，中間一道帶缺口的障礙牆
grid = [[0]*10 for _ in range(10)]
for c in range(10):
    if c != 4:                       # c=4 是牆的缺口
        grid[5][c] = 1               # 橫牆在第 5 列
start, goal = (0, 0), (9, 9)
path = lee_route(grid, start, goal)
print(f"繞線成功，路徑長 = {len(path)-1} 步")
print_grid(grid, set(path), start, goal)

# 展示 Lee 演算法的「無路徑」偵測：封死缺口
grid2 = [row[:] for row in grid]
grid2[5][4] = 1
print("\n封死缺口後:", lee_route(grid2, start, goal))

輸出：

繞線成功，路徑長 = 18 步
  S.........
  .*........
  .*........
  .*........
  .*........
  .*...#####
  .*.*/.....
  ..*.*.....
  ....*..*..
  .......*G

封死缺口後: None

路徑先向下、穿過缺口、再折向右下——BFS 保證這是 18 步的最短繞線；當缺口被封死，演算法正確回報無路徑（None），體現其完備性。

複雜度分析#

時間：最壞 O(R·C)（探索全網格）；典型情況與「起終點包圍的面積」成正比，約 O(d²)，d 為曼哈頓距離。
空間：距離陣列 O(R·C)——大版圖的主要瓶頸，催生了 A* 與區域繞線。
與 A* 比較：Lee 無啟發資訊；A* 以 h(n) 引導可減少探索格數數十倍，且在 h 可容許（admissible）時仍保證最短。

練習#

修改成本模型：垂直走線成本 1、水平成本 2（模擬 preferred direction），重跑並觀察路徑形狀變化。
實作 Soukup 演算法（擴展時優先沿「朝向目標」的方向直進），比較與 Lee 在 50×50 網格上的探索格數。
兩條 net 依序繞線時，第二條可能失敗。實作簡單的 rip-up & reroute：失敗時移除相關走線再試，並討論其收斂性。