1961 - Lee 繞線演算法：讓機器在迷宮裡找路#

案件摘要#

1961 年，Bell Labs 的 C. Y. Lee 發表「An Algorithm for Path Connection and Its Applications」， 把晶片上的金屬連線問題轉成「網格迷宮找最短路徑」——wavefront（波前）擴張法誕生。 這個看似樸素的 BFS 演算法，日後成為 place & route 工具、FPGA 布線器，乃至今日晶片設計流程中仍在服役的老兵。

前因 -- 為什麼會有這個案子#

• 接線全靠手工與電纜板：1960 年代的印刷電路板與早期積體電路，連線由佈線員照接線表人工畫出；數十條網路交錯，錯一條就重來。
• 電腦已被證明「會找路」：Shannon（1949）與 Moore（1959）早已指出，圖上的最短路徑可用廣度優先搜索在 \(O(|V|+|E|)\) 內找到；Lee 的關鍵推理是把 IC 版圖離散化成網格，讓「兩點之間該怎麼走」變成 BFS 能回答的問題。
• 網格化的代價：記憶體需求為 \(O(W \times H)\) （每格存一個 label），1960 年代的機器跑得動小晶片，但跑不動大版圖——這筆債要到 1978 年 Soukup、1979 年 Hightower 才償還。
• 關鍵推理：繞線不只是「找路」，還要「分層分配」——兩層金屬交錯的問題在 channel routing 裡獨立成案（Deutsch 1976、left-edge algorithm），本質是區間圖著色：

區間圖是 perfect graph，著色數等於最大團（clique），而區間圖的最大團恰好是「任一縱切線上重疊的網路數」——這個定理讓 channel routing 從 NP-hard 迷霧中脫身。

線索與推理 -- 數學式、程式、理論#

1. 案件現場：wavefront 擴張的三步曲#

Lee 演算法把版圖切成網格，障礙物（已佈線、禁區）標成 blocked，其餘為 free：

1. 標記起點：起始格 label 設為 0，加入波前（wavefront）。
2. 波前擴張：從波前逐格向外擴張，每個相鄰 free 格的 label = 當前格 label + cost；抵達終點即停。這就是 BFS——在均一 cost 下，第一次抵達終點的路徑必為最短路：

1. 回溯：從終點沿 label 遞減 1（或 cost）的方向走回起點，即得路徑。

2. BFS 保證最短路：歸納法證明#

命題：均一 cost 網格上，BFS 首次標記某格時的 label 即最短距離。

• 基底：起點 label = 0，顯然最短。
• 歸納：假設 label \(< k\) 的格都拿到最短距離；label \(= k\) 的格只可能從 label \(= k-1\) 的鄰居到達，任何「更短」的路徑都得經過一個 label \(< k-1\) 的中繼格——但該格若存在，早在更早的波就被標記了，矛盾。
• 引申：若 cost 不均一（如 via 要加權、上層金屬較貴），BFS 失效，需改用 Dijkstra（ \(O(E \log V)\) ）或 A*；Lee 演算法的繼承者們全都走這條路。

3. Soukup（1978）與 Hightower（1979）：替 BFS 減肥#

• Soukup 演算法：觀察到 BFS 是「無方向」的亂槍打鳥，於是改成偏向目標方向的深度優先——沿直線朝終點猛衝，撞牆才轉彎；找到路的速度快數十倍，但不再保證最短。這是「速度 vs 品質」的第一筆交易。
• Hightower line-search：更激進——只沿「經過起點與終點的水平/垂直延伸線」上的障礙物端點做候選轉折點，記憶體需求從 \(O(W \times H)\) 降到 \(O(\text{障礙物數})\) 。大版圖繞線自此可行。
• 迷宮繞線的殘留價值：即使有了 line-search，全域繞線（global routing）之後的 detail routing 在擁塞區仍常退回 Lee 演算法——因為它保證找到路（若存在），且實作簡單、易於平行化。

4. Channel routing 與 left-edge theorem#

兩層金屬的通道繞線（channel routing）：水平線段放在一層（軌道 track）、垂直線段放在另一層，問題變成「區間分配」：

• Left-edge algorithm（Hashimoto–Stevens, 1971）：把每個網路在通道內的水平跨度看成區間 \([l_i, r_i]\) ；兩區間重疊者不能放同一軌道。把所有區間依左端點排序，貪婪地依序放入第一個放得下的軌道——結果軌道數等於最大重疊數 \(\omega\) ，即最佳解。證明：區間圖是 perfect graph， \(\chi = \omega\) ，且 left-edge 的貪婪順序恰好實現這個著色數。
• Burstein 難例（Burstein's difficult channel）：left-edge 搞不定的經典測試例（含 switchbox 約束），1976 年 Albert Nanshi Deutsch 在 IBM 用基因演算法（genetic algorithm）解出理論最小軌道數，成為 channel routing 的里程碑。
• Negotiable channel routing：1990 年代後的工具允許「先繞線、後協商」——擁塞網路加權懲罰、迭代放寬，把 channel routing 與 detail routing 統一成一個 negotiable 框架。

5. Verilog 速記：一條需要繞線的網路#

// 兩個模組放在版圖兩端，中間的連線該怎麼走？
module top (input a, output y);
    wire [3:0] bus;             // 4 條網路要穿過 channel
    reg [3:0] mem;
    always @(*) mem = {a, a, ~a, a};
    assign y = &bus;
    assign bus = mem;           // EDA 布線器要為 bus 在 channel 內找 4 條軌道
endmodule
// 佈局結果（示意）：channel 內 4 條水平軌道，left-edge 分配：
// track 0: bit0   track 1: bit1   track 2: bit2   track 3: bit3
// （若 bit0 與 bit2 跨度重疊，則分別佔 track 0 與 track 1）

6. Python 實作：wavefront 迷宮繞線#

from collections import deque

def lee_route(grid, start, goal):
    """Lee wavefront：BFS 在網格上找最短路徑，回傳路徑與標記矩陣"""
    H, W = len(grid), len(grid[0])
    label = [[None] * W for _ in range(H)]
    label[start[0]][start[1]] = 0
    wave = deque([start])
    while wave:
        r, c = wave.popleft()
        if (r, c) == goal:
            break
        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):   # 四鄰居
            nr, nc = r + dr, c + dc
            if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] == 0 and label[nr][nc] is None:
                label[nr][nc] = label[r][c] + 1
                wave.append((nr, nc))
    if label[goal[0]][goal[1]] is None:
        return None, label                                  # 不可達
    path, (r, c) = [goal], goal                             # 回溯
    while (r, c) != start:
        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            pr, pc = r + dr, c + dc
            if 0 <= pr < H and 0 <= pc < W and label[pr][pc] == label[r][c] - 1:
                path.append((pr, pc)); r, c = pr, pc; break
    return path[::-1], label

def show(grid, label, path):
    for r in range(len(grid)):
        row = ''
        for c in range(len(grid[0])):
            if (r, c) in path:        row += '*'
            elif grid[r][c] == 1:     row += '#'
            elif label[r][c] is not None: row += str(label[r][c] % 10)
            else:                     row += '.'
        print(row)

grid = [
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 0, 0],
    [0, 1, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 1, 0, 1, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
]
path, label = lee_route(grid, (0, 0), (6, 7))
show(grid, label, path)
print("path length:", len(path) - 1)
# 0.......
# *#####..
# *#...#..
# *#.*.#..
# *#*#*...
# *#####**
# *......*
# path length: 13

注意：# 是障礙物（已佈線區），* 是繞出的最短路徑；若 (0,0) 到 (6,7) 存在路，BFS 必找到最短者——這是 Lee 演算法的招牌保證。

結案 -- 後果與影響#

• Place & route 工具核心：Lee 演算法成為所有自動佈局布線（P&R）工具的 detail routing 起點；沒有它，就沒有現代 EDA 的「擺完就接線」。
• FPGA 布線器：Xilinx、Altera 的 FPGA 內部可程式互連（switch box + routing channel），其布線演算法的祖師正是 Lee 的 wavefront。
• channel routing 獨立成案：left-edge algorithm、Burstein 難例、negotiable routing 讓「分層分配」從經驗法則變成有定理支撐的最佳化。
• 延續至今：global routing 的擁塞估計、detail routing 的 maze search、FPGA 的 negotiated congestion（如 PathFinder 演算法）——1961 年這條線上的演算法至今仍在量產晶片上服役。

關鍵人物與文獻#

• C. Y. Lee（Bell Labs）："An Algorithm for Path Connection and Its Applications", IRE Transactions on Electronic Computers, 1961。
• Shannon、Moore：圖上最短路徑搜索的先驅（1949、1959）。
• Soukup（1978）：偏向目標方向的加速版迷宮繞線。
• Hightower（1979）：line-search 繞線，把記憶體需求降到 \(O(\text{障礙物數})\) 。
• Hashimoto–Stevens（1971）：left-edge algorithm，channel routing 的區間著色定理。
• Albert Nanshi Deutsch（IBM, DAC 1976）：基因演算法解 Burstein 難例，channel routing 的里程碑。