跳轉到

1961-Lee迷宮繞線#

案件摘要#

1961 年，貝爾實驗室的 C. Y. Lee 發表《An Algorithm for Path Connections and Its Applications》，為「兩點之間繞一條最短、且不撞任何障礙的線」給出第一個系統性保證：以廣度優先搜尋（BFS）從起點掀起一道「波前」，波前先抵達的格子必然最短。這個被暱稱為「Lee 迷宮演算法」的程序，是印刷電路板與早期 IC 自動繞線的第一個實用引擎，也是此後所有格子繞線演算法（A*、線搜尋、通道繞線）偵辦時都要回頭傳閱的第一份卷宗。

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

  • 接線表會告訴你「誰連誰」，但不會告訴你「怎麼走」：IBM 的設計自動化（1957）解決了文件層，物理走線仍是手工。
  • PCB 時代來臨：印刷電路板把走線從空中（導線）壓到平面（銅箔），平面上的障礙碰撞問題首次大規模出現。
  • Shannon 的機械鼠（1950）：Shannon 的「Theseus」已用繼電器實體示範「波前探索迷宮」，證明概念可行，缺的是可規模化的演算法。
  • 最短線是工程鐵律：線越長，延遲、雜訊、成本越高——必須保證「存在即找到最短」。

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

核心：BFS 波前 = 最短路的離散證明#

把板面離散化成格子圖 \(G=(V,E)\) ，障礙格標記為 blocked。Lee 演算法三階段：

  1. 擴波（wave expansion）：從源點 \(s\) 起，逐層標記距離：距離 1 的格子、距離 2 的格子……像水波擴散；
  2. 回溯（traceback）：到達目標 \(t\) 後，沿距離遞減的方向走回 \(s\) ，得到路徑；
  3. 標記清除：清除波前標記，保留路徑。
from collections import deque

def lee_route(grid, start, goal):
    """grid: 2D list, 0=空格, 1=障礙。回傳最短路徑（4-鄰接）。"""
    R, C = len(grid), len(grid[0])
    dist = {start: 0}
    q = deque([start])
    while q:
        r, c = q.popleft()
        if (r, c) == goal: break
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r+dr, c+dc
            if (0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 0
                    and (nr, nc) not in dist):
                dist[(nr, nc)] = dist[(r, c)] + 1
                q.append((nr, nc))
    if goal not in dist: return None          # 不存在路徑
    path, cur = [goal], goal
    while cur != start:                        # 沿距離遞減回溯
        r, c = cur
        cur = min(((r+dr, c+dc) for dr, dc in ((1,0),(-1,0),(0,1),(0,-1))),
                  key=lambda p: dist.get(p, 10**9))
        path.append(cur)
    return path[::-1]

grid = [[0]*5 for _ in range(5)]
grid[2][1] = grid[2][2] = grid[2][3] = 1    # 中間一道牆
print(len(lee_route(grid, (0,0), (4,4))))   # 8（繞過牆的最短步數）

為何正確：BFS 的不變量是「隊列按距離遞增出隊」，故任何格子第一次被標記時的距離即最短距離——這是無權重圖上 Dijkstra（1959）的特例，卻因「距離只有小整數」而可用簡單隊列，不需優先佇列。

複雜度的雙面刃#

  • 時間/空間 \(O(|V|)\) ：每格只進隊一次——最壞情形要淹沒整張板。設板有 \(n\) 格，一次繞線的記憶體即 \(O(n)\) 。
  • 這在 1961 年的磁心記憶體上是殘酷的——Lee 演算法的可靠性與它的記憶體飢渴同樣出名，逼出後來的線搜尋（1969）與 A*（1977）。

多終端推廣#

多點連接（net 有 \(k\) 個 pin）用迭代法：先連兩點，把結果視為新終端再連下一點，貪心建出 Steiner 樹的近似——Steiner 樹理論（Hanan, 1966）隨即接手。

結案 -- 後果與影響#

  • 自動繞線成為可能：1960-70 年代商用 PCB/IC 繞線器幾乎都以 Lee 演算法為核心，直接支撐主機板與早期 IC 的量產。
  • 演算法族譜的根：Hightower 線搜尋（1969）與 Hadlock A（1977）都是針對「Lee 記憶體爆炸」的破案續集；今日 EDA 的 detailed routing 引擎，內核仍是 Lee + A 的混合體。
  • 障礙懲罰的伏筆：Lee 在論文中已允許給格子標「代價」而非只標 0/1——這正是現代繞線器處理擁塞（congestion cost）的思想原點。
  • 貝爾體系的接力：Hanan（1966）、Kernighan-Lin（1970）、McCluskey 都在同一棟樓裡，讓貝爾實驗室成為 EDA 演算法的第一個黃金產地。

關鍵人物與文獻#

  • C. Y. Lee（李振遠）（1925–）：貝爾實驗室，網路可靠度與繞線演算法先驅。
  • 文獻：
  • C. Y. Lee, "An Algorithm for Path Connections and Its Applications," IRE Trans. Electronic Computers EC-10, 346 (1961).
  • E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik 1, 269 (1959)（最短路理論基礎）。
  • C. E. Shannon, "Presentation of a Maze-Solving Machine," 1951（Theseus 機械鼠）。