07.1 Lee 演算法與迷宮搜尋：租用 AT&T 機器算一條線的年代#

一條線的代價#

今天我們打開任何一套 EDA 工具，按下 route 按鈕，幾百萬條線在幾分鐘內繞完，很少有人會想到：繞線演算法的起點，是一個連「租用電腦時間」都要精打細算的年代。1950 年代末期，電腦是價值數百萬美元的稀有事業設備，機器時間以秒計價；而電路設計師面對的問題卻越來越龐大——印刷電路板（PCB）上的數百個零件、數千條接線，靠人工在曬圖紙上畫線已經瀕臨極限。把繞線交給電腦，不只是技術理想，更是經濟上的必然；但反過來說，任何演算法只要多跑一秒，成本就以真金白銀累積。這個「計算本身很貴」的前提，塑造了整個 1960 年代繞線研究的樣貌。

C.Y. Lee 與迷宮搜尋的誕生#

1961 年，任職於 IBM 的 C. Y. Lee（李景章）發表了《An Algorithm for Path Connection and Its Applications》，收錄於 IRE Transactions on Electronic Computers。這篇論文提出的方法後來被稱為 Lee 演算法，也常被叫作迷宮搜尋（maze routing）或波前擴散（wavefront expansion）。它的核心直覺極其優雅：把接線區域看成一張格子圖，就像迷宮一樣；從起點開始，一層一層向外標記距離，直到碰到終點；再從終點沿著遞減的標記走回起點，走出的路徑必然是最短的那一條。

用現代的語言說，Lee 演算法就是廣度優先搜尋（BFS）。設格子圖為 \(G=(V,E)\) ，起點 \(s\) 、終點 \(t\) ，演算法分兩個階段。第一階段是擴散：建立一個 cost 陣列 \(C\) ，令 \(C(s)=0\) ，其餘格初值為 \(\infty\) ；維護一個波前佇列，每次取出波前上的格子，把四個（或六個，含兩層板層間的 via）鄰居中尚未標記者標記為 \(C(n)+1\) ，並加入波前。當 \(t\) 被標記時擴散停止。第二階段是回溯（backtrack）：從 \(t\) 開始，每次走向標記值恰比自己小 1 的鄰居，直到回到 \(s\) 。整個過程可寫成：

expand:  queue := {s};  C[s] := 0
         while queue not empty:
             p := dequeue(queue)
             if p == t: break
             for q in neighbors(p):
                 if C[q] == ∞ and q not blocked:
                     C[q] := C[p] + 1
                     enqueue(queue, q)
backtrack: p := t;  path := [t]
           while p != s:
               p := neighbor(p) with C[p] == C[path.head] - 1
               push(path, p)
           reverse(path)

因為 BFS 按距離分層擴散，第一個碰到 \(t\) 的波前半徑就是 \(s\) 到 \(t\) 的最短跳數，回溯得到的就是最短路徑。如果擴散直到波前用盡都沒碰到 \(t\) ，則兩點之間無路可通——Lee 演算法因此還是完備的：它不會漏解，只要解存在，它一定找得到；而且找到的一定是最短的。這種「寧可慢，但保證正確」的性格，使它成為繞線問題的黃金標準，此後數十年所有繞線演算法都以「與 Lee 演算法結果的比較」作為品質基準。

值得注意的是，Lee 本人在論文中討論的不只是兩點連線，還包括多端點網（multi-terminal net）的連接以及線段分配等應用，可見他已意識到這是一個通用性的圖搜尋框架，而非單純的「畫線程式」。

為什麼是 IBM？技術、經濟與制度的交會#

Lee 演算法出現在 IBM，並非偶然。1950 年代末的 IBM 正處於從打孔卡片機器公司轉型為電腦公司的關鍵期，System/360 計畫（1964 年發布）背後是數十億美元的豪賭，其電路板與固態邏輯技術（SLT）模組的佈局繞線量遠超人工能力。IBM 內部因此大力投資自動化設計：把元件位置、接線、製造資料全部數位化。Lee 的演算法正是這條自動化生產線上的一環——先由放置演算法決定元件位置，再由繞線演算法一根一根把線接起來。

這裡有一個重要的工程順序問題：繞線必須在放置之後、且要考慮線與線之間的互斥（一個格子只能被一條線使用），所以繞線是一連串「先繞者占格、後繞者繞道」的過程。Lee 演算法在每次搜尋時把已占用格視為 blocked，這使得繞線順序（net ordering）成為影響結果的關鍵——先繞的短線走直路，後繞的線被迫繞遠甚至失敗。1960 年代的工程師用各種啟發式排序（短線優先、關鍵線優先）與事後重繞（ripple routing，讓被擋住的線推開重繞）來緩解，這個「繞失敗了就拆掉重來」的思想，正是日後 rip-up and reroute 的雛形，我們會在 7.3 與 7.4 看到它的成熟形態。

經濟面的制約同樣深刻。當時的做法是：設計師把電路圖與元件座標打在卡片上，送到計算中心排隊，機器跑完再取回結果圖。一次完整的板級繞線可能耗費數小時的機器時間——以當時大型主機每小時數百美元的租金計算，一次繞線作業的電腦成本相當於一位工程師數天的薪水。這種成本結構帶來兩個直接後果：第一，演算法的記憶體與時間複雜度是論文裡最被認真討論的指標，勝過路徑品質的微小差異；第二，「一次跑對」的壓力極大，工程師寧可保守地多繞一次保證成功的流程，也不願反覆試錯。Lee 演算法確定性、可證明最短的性質，在這個脈絡下不只是數學美感，而是制度性的需求——它讓「繞線結果」可以被預期、被驗收。

Lee 論文中也誠實地討論了演算法的成本：對一個 \(w \times h\) 的格子區域，擴散最壞情況要標記整個區域，時間與空間都是 \(O(wh)\) 。對小電路板這還可以接受，但隨著晶片整合度上升，這個平方級成本迅速失控。1960 年代的研究者很早就展開兩條補救路線：一是縮小每次搜尋的搜索範圍、剪除不必要的擴散；二是乾脆放棄格點式搜尋，改用線段式的搜尋結構。這兩條路線分別在 1970 年代結出 Soukup 與 Hightower 的果實，是下一節的主題。

迷宮之外：Lee 演算法的延伸影響#

Lee 演算法的影響遠超繞線本身。它是連通性問題的通用求解器：論文標題中的 "and Its Applications" 不是客套，Lee 示範了同一個波前擴散可以用於檢查兩點是否已連通、計算最短的修正路徑、甚至做障礙迴避。後來的迷宮式時脈樹繞線、迷宮式 bus 分析、乃至遊戲產業的尋路（pathfinding）都直接或間接承襲這個框架。對軟體工程師而言，Lee 演算法就是「BFS 在二維網格上的應用」；但放在 EDA 史的脈絡裡，它是第一個被工業界大規模使用的自動繞線方法，證明了「數值計算可以取代製圖員」這件事，從而確立了 EDA 作為一門產業的正當性。

1960 年代後半，隨著積體電路取代印刷電路板成為主要載體，繞線問題的規模與限制都改變了：晶片上的線寬更細、層數更多、但單位面積的線網密度呈數量級成長。Lee 演算法的保證最短依然誘人，但每條線都要清空並重標整個 cost 陣列的做法，在數千條線網的晶片上已不經濟。繞線研究進入「如何在保證品質的同時把速度拉上來」的時代——這正是 Soukup、A* 與 line-search 演算法登場的舞台。