07.2 Soukup 與 A 星：讓迷宮搜尋跑得夠快#

速度成為第一優先#

Lee 演算法證明了迷宮搜尋可行，但它的成本結構——每連一條線就清空並重標整面格子——在晶片規模下難以承受。1970 年代的繞線研究者面對一個明確的問題：能否保留迷宮搜尋「完備、無所遺漏」的性格，但讓單次搜尋的時間下降一到兩個數量級？這個時代的答案有三條主線：Jiri Soukup 的方向性快速搜尋、源自機器人學的 A* 演算法、以及 David Hightower 的線段搜尋。它們共同改寫了繞線演算法的性價比曲線，也讓迷宮繞線從「大型主機上的昂貴作業」變成「工作站上可以反覆執行的日常工具」。

Soukup 演算法：朝目標狂奔的 BFS#

1978 年，IBM 的 Jiri Soukup 發表《Fast Maze Router》，提出一個精巧的混合策略。他的觀察是：Lee 演算法的時間花在「四面八方均勻擴散」，但實際上從 \(s\) 到 \(t\) 的線路大部分路段是直行的，只有在遇到障礙時才需要轉彎試探。因此 Soukup 演算法把搜尋分成兩種模式交替進行。

第一種是直進模式（fast search）：從目前格點朝著朝向目標的方向一路延伸，把整段直線上的空格一口氣標記，每一步的 cost 累加，直到撞到障礙、離開有界區域，或是越過目標才停下。第二種是環繞模式（circle expansion，即 BFS）：在直進行不通的時候，退回 Lee 式的逐格擴散，把候選方向周圍的格子一圈一圈展開，找到新的可行直進方向後再切回直進模式。其骨架如下：

Soukup(s, t):
    C[s] := 0;  frontier := {s}
    while t not reached:
        for each unvisited direction d from frontier:
            p := advance(frontier, d)
            while p is free and advancing d moves closer to t:
                C[p] := C[frontier] + 1;  mark(p);  push(p)
            # 直進被迫停止 -> 局部 BFS 擴張
            wave := BFS-expand(p, until a cell with a free line to t direction)
        frontier := newly marked cells
    backtrack along decreasing C  (與 Lee 相同)

這個方法的性質很特別：直進模式大幅削減了被標記的格子數，Soukup 在論文中報告的加速比常達兩個數量級；但代價是它不再保證找到最短路徑——直進時「搶先」走的路可能在繞障後並非整體最短。Soukup 演算法是完備的（只要路存在一定找得到，因為卡住時會退回 BFS），但它是 deviation-count 意義下的近似：找到的路徑的轉彎數不會超出最短路徑太多，實務上長度極接近最短。對 1970 年代的工程師而言，這是極划算的交易：用少數百分比的線長損失，換掉九成以上的機器時間。

A*：來自機器人學的啟發式#

第二條主線甚至不是從 EDA 內部長出來的。1968 年，SRI International（當時的 Stanford Research Institute）的 Peter Hart、Nils Nilsson 與 Bertram Raphael 為了讓行動機器人 Shakey 規劃路徑，發表了 A* 搜尋演算法。Shakey 是史上第一個具備感知—推理—行動閉環的機器人，它在房間裡推箱子、避障礙，需要一個既能保證找到路、又能少走冤枉路的路徑規劃器。A* 的核心思想是在 Dijkstra/BFS 的基礎上加入啟發式估計：評價每個候選格點的優先順序為

其中 \(g(n)\) 是從起點到 \(n\) 已走過的實際代價， \(h(n)\) 是從 \(n\) 到終點剩餘代價的估計值。搜尋時始終優先展開 \(f\) 最小的節點。只要 \(h\) 是可接納的（admissible，即不高估實際剩餘代價），A* 保證找到最短路徑，同時展開的節點數通常遠少於均勻擴散。

在網格迷宮上，最常用的可接納啟發式是曼哈頓距離： \(h(n) = |x_n - x_t| + |y_n - y_t|\) 。它顯然不高估——再怎麼繞，剩餘的線長不會小於水平垂直位移之和——因此 A* 在格點繞線上保有最優性保證，卻把擴散的方向性「拉」向目標，被展開的格子集中在 \(s\) 到 \(t\) 之間的橢圓區域內。把 Lee 演算法看成 \(h \equiv 0\) 的 A，就能一眼看懂兩者的關係：啟發式不影響正確性，只影響效率； \(h\) 越接近真實剩餘代價，搜尋越聚焦。這個觀點把 1961 年的 Lee 與 1968 年的 A 統一在同一個框架下，是後世教科書的標準講法。

值得一提的是，A* 進入繞線領域的時間點恰逢 EDA 學界與機器人學界對圖搜尋的共同興趣期；到 1980 年代，迷宮繞線教科書已把 A* 當成預設選項，權衡僅在啟發式的選擇：除了曼哈頓距離，還有人用加入估計轉彎數、估計 via 數的加權版本，把繞線目標（例如「寧可長一點也不要多打 via」）直接編碼進 \(h\) 或 \(g\) 的權重。

Hadlock：以障礙計數為度量#

在 A* 框架之外，Frank Hadlock 於 1977 年提出一個針對「最小化障礙繞行」的變體。他的度量不是跳數，而是定義

其中 \(\mathrm{DT}(p)\) 是從 \(p\) 出發到達 \(t\) 的直線方向上必須「偏離」（detour）的次數。直觀地說，Hadlock 把「必須繞障」視為額外成本：每偏離最短方向一步，路徑最終必須折返，等於多付兩格。以這個度量做波前擴散（等價於一個以障礙數為主的 A*），搜尋會自然貼著障礙邊緣走，被展開的格子數與「繞障次數」成正比而非與面積成正比。對障礙稀疏的場景，Hadlock 演算法的表現接近線性於路徑長度，是 1970 年代末迷宮加速研究的代表作之一。

記憶體才是真正的牆#

時間加速之外，1970 年代的另一道牆是記憶體。Lee 式方法需要整面 grid 的 cost 陣列——以當時的記憶體價格，一張大面積、細格距的晶片平面就要吃掉機器絕大部分的記憶，甚至根本放不下。這催生了完全不同思路的線段搜尋（line-search）：Kimmi Mikami 在 1965 年代末至 1970 年間提出的改良（Mikami-Tabuchi 演算法）與 David Hightower 在 1969 年提出的 Hightower 演算法，都不維護格點陣列，而是從起點與終點出發，沿著水平與垂直線段延伸，在每個「可能轉彎的位置」（例如障礙的邊線延伸）產生候選線段，遞迴地窮舉線段序列直到起終點的線段相交。它們的記憶體用量與線段數成正比，而非與格點數成正比；代價是不再有「最短」保證——找到的是可行路徑，且在某些障礙配置下會漏解（不完備）。1970 年代商業繞線系統普遍在「格點迷宮（慢、大、最優）」與「線段搜尋（快、省、啟發）」之間做取捨，甚至混合使用：先用線段搜尋找路，找不到再退回迷宮搜尋。

一條主軸的延續#

回頭看，這十幾年的演算法史有一條清晰的主軸：Lee 演算法提供了正確性基準，其後的每一步都是在「放棄一點最優性或完備性」與「換取數量級的速度與記憶體節省」之間交易。這種交易思想是 EDA 的核心品味之一——工程師永遠在品質保證與計算成本之間找甜蜜點。但迷宮搜尋本身仍是「一次連一條線」的局部視角：每條線各憑本事搶格子，全局的擁塞沒有人負責。當晶片上線網數量與層數再上一個台階，繞線問題必須被拆解成分層負責的架構——全局繞線先規劃每條線大概走哪一區，詳細繞線再一格一格落實。這個分工的理論基石 Steiner 樹，是下一節的主題。