跳轉到

4.1 Kernighan-Lin 的 1970 年論文：成對交換與增益序列#

一篇誕生在貝爾實驗室的啟發式演算法#

1970 年，Bell Labs 的 Brian Kernighan 與 Shen Lin 在《Bell System Technical Journal》上發表了〈An Efficient Heuristic Procedure for Partitioning Graphs〉。這篇論文日後成為 EDA 史上被引用最多的文章之一，而它處理的問題看似平凡：把一個圖的頂點分成兩個大小相等的集合，使跨越兩集合的邊數最少。這個問題就是圖論中的最小割問題在平衡約束下的版本——眾所周知，加入平衡限制後它變成 NP-hard，因此任何實用的解法都必須是啟發式的。

Kernighan 與 Lin 當時面對的現實動機，是 Bell Labs 內部日益龐大的電路設計與電腦系統拆分需求。把電路板上的邏輯閘分配到兩塊電路板、把程式模組分配到不同的記憶體頁，本質上都是同一個數學問題。跨集合的每一條連線都代表真實的成本：接腳、線路、延遲。1960 年代末期，晶片與系統規模快速成長，人工分區已經不可行，「讓電腦自動把電路切好」成為一個有明確經濟價值的題目。

Bell Labs 在這個年代的研究文化值得特別一筆。這裡是 Unix 誕生地（Thompson 與 Ritchie 在 1969–1973 年間完成第一版），awk 也將在 1977 年由同一個 Kernighan 與 Aho、Weinberger 寫出。Kernighan 本人後來以《The C Programming Language》（與 Ritchie 合著的 K&R）與《The Unix Programming Environment》聞名於世，但他的研究軌跡橫跨軟體工具、排版系統與組合最佳化。他在回憶中屢次提到，Bell Labs 最大的資產是「可以花時間把一個問題想透」的自由——KL 論文正是這種文化的產物：不急著發表，而是把一個看似簡單的交換程序徹底分析到極致，包括收斂行為、隨機初始的統計性質、以及執行時間的下界。

成對交換的基本思路#

KL 之前流行的做法是所謂的「簡單交換」：任取一對分屬兩側的頂點，若交換能減少切邊就交換，否則停止。這種方法幾乎總是落入極差的局部極小——它像一個只肯走下坡路的登山者，遇到第一個小山頭就止步。

Kernighan 與 Lin 的洞察在於：即使眼前所有單一交換都會變差，連續做一串「先變差、後變好」的交換，總體仍可能大幅改善。換句話說，不要貪圖每一步的局部增益，而要規劃整條「增益序列」，再取序列中最有利的截斷點。

形式化地，對一對分屬 \(A\) 、 \(B\) 兩側的頂點 \((a, b)\) ，定義交換增益

\[ g(a,b) = D(a) + D(b) - 2c(a,b), \]

其中 \(D(a) = \sum_{y \notin A} c(a,y) - \sum_{y \in A} c(a,y)\) 是頂點 \(a\) 的「外連度減內連度」， \(c(a,b)\) 是 \(a\) 、 \(b\) 之間的邊權。 \(D(a)+D(b)\) 項估計了把兩點互換後切邊權的變化，而 \(-2c(a,b)\) 修正了 \(a\) 、 \(b\) 相連時被重複計算的部分。

一個 pass（KL 稱之為一輪「改善序列」）的流程如下：

  1. 對所有跨側頂點對計算 \(D\) 值，找出使 \(g_1\) 最大的對 \((a_1,b_1)\) ，將其「鎖定」（標記為已交換）。
  2. 更新其鄰居的 \(D\) 值，在未鎖定的頂點中再找增益最大的對 \((a_2,b_2)\) ，得到 \(g_2\) 。如此重複 \(n\) 次，得到序列 \(g_1, g_2, \dots, g_n\) 與前綴和 \(G_k = \sum_{i=1}^{k} g_i\) 。
  3. 找出使 \(G_k\) 最大的 \(k\) （best prefix，最佳前綴）。若 \(G_k > 0\) ，則真正執行前 \(k\) 個交換（注意：是前 \(k\) 個，不是全部 \(n\) 個），回到步驟 1 開始下一個 pass；若 \(G_k \le 0\) ，終止。

這個「先虛擬地鎖定整條序列、再取最佳前綴」的技巧，使演算法能夠翻越增益為負的谷地，逃脫簡單交換無法逃脫的局部極小。原論文用大量實驗顯示：從隨機初始解出發，通常少數幾個 pass 就收斂，且結果接近最佳解。

KL-pass(G, A, B):
  unlock all vertices
  for k = 1 to n/2:
    for each (a in A_unlocked, b in B_unlocked):
      compute g(a,b) = D(a) + D(b) - 2c(a,b)
    pick (a_k, b_k) with max g_k
    lock a_k, b_k ; record g_k
    update D of neighbors
  find k* maximizing G_k = g_1 + ... + g_k
  if G_k* > 0: swap first k* pairs ; return improved
  else: return no improvement

複雜度與實務性質#

一個 pass 中，第 \(k\) 步要在剩餘的 \((n/2-k+1)^2\) 個頂點對中挑最大增益；若以簡單掃描實作，總成本為

\[ \sum_{k=1}^{n/2} O\!\left((n/2-k)^2\right) = O(n^3), \]

而 KL 論文採用對每個頂點維護排序的 \(D\) 值表，把單步降到 \(O(n \log n)\) ，整體為 \(O(n^2 \log n)\) 。對 1970 年的電腦而言，這已足以處理數百個頂點的電路——當年這正是實用規模的上限。

KL 有兩個實務上重要的性質。其一是確定性與可重現性：給定初始解，結果可預期，這在工程流程中極受歡迎。其二是對初始解不敏感到令人驚訝的程度——論文實驗顯示隨機初始化往往也能抵達同一批高品質局部極小。代價則是對頂點度數大的圖（電路 netlist 正是如此）每個 pass 都很昂貴，而且每次只能交換一對頂點、嚴格維持兩側大小相等，這對真實電路「面積可不等」的需求顯得過於僵硬。

歷史位置：被 FM 改寫的後續#

KL 演算法確立了「iterative improvement + gain 序列 + best prefix」這個範式，之後十餘年間幾乎所有分區研究都以它為起點。但它的兩個限制——圖（而非超圖）模型、以及成對交換的 \(O(n^2 \log n)\) 成本——很快就被挑戰。1982 年，Fiduccia 與 Mattheyses 把同樣的增益思想搬到超圖上，並以一次只移動一個單元配合 gain bucket 資料結構，把單一 pass 的時間降到 \(O(n)\) 。這就是下一節的主角：FM 演算法。

KL 本身的生命並未終結。在頂點數被縮減（clustering/coarsening）之後的粗化圖上，KL 依然是高品質的精修工具；Kernighan 本人在 1972 年還將同樣的思想推廣到多路分區（與 Schweikert 合作的 quadrant interchange）。一個耐人尋味的文化註腳是：Kernighan 在 1970 年代把心力轉向程式語言與軟體工具，而 Lin 則繼續在組合最佳化深耕（他與 Kernighan 合作的旅行商問題 2-opt/3-opt 改善法同樣是經典）。分區問題則交給了下一世代——而下一世代將證明，把「圖」換成「超圖」、把「對」換成「點」，收益會大得多。