電路布線問題求解的改進算法

摘要：常用的解決電路布線問題的算法的時間和空間的復雜度都是O(n2)。這里n為一塊電路板的上端（或下端）接線柱的個數。現給出一種時間復雜度為O(nlogn)的新算法。改進了傳統的算法。

關鍵詞：算法；電路布線；二分法

中圖分類號：TP301.6文獻標識碼：A 文章編號：1009-3044(2008)35-2205-02

An Improved Algorithm for the Circuit Wiring Problem

ZHANG Li-xiang， ZHAO Xue-feng

(Colleg of Mathematics and Information Science，the North West Normal University，Lanzhou 730070，China)

Abstract: In common，the algorithm for circuit wiring proble's complexity of time and space are of O(n2).Here n is the number of the circuit board upper end (or bottom-end).A new algorithm of time complexity being O(nlogn) is presented to improve the traditional algorithm.

Key words: algorithm; circuit wiring; dichotomy

1 引言

電路布線問題是一個很基本，較常見的小問題，但這個問題的求解方法卻并不是那么顯而易見，需要較深入的思考和良好的算法素養才能得出較好的算法。

2 問題描述

在一塊電路板的上下兩端分別有n個接線柱。根據電路設計，要求用導線（X，Y）將上端接線柱X和下端接線柱Y相連，如圖1所示。其中X =〈b1，b2，…bn〉=〈1，2，…n〉的一個排列，Y=〈C1，C2，…Cn〉=〈1，2，…n〉的一個排列。導線（X，Y）稱為電路板上的連線，與上線柱相連形成連線的對應下接線柱的新序列L=〈a1，a2，…an〉。對于任何1≤bi≤bj≤n，第i條連線和第j條連線不相交的充分必要條件是ai≤aj。

在制作電路板時，要求將這n條連線分布到若干絕緣層上，在同一層上的連線不相交。電路布線問題要確定哪些連線安排在第一層上，使得該層上有盡可能多的連線。即：該問題要求確定導線連線的最大不相交的條數[1]。

設Size[i][j]為下端接線柱不超過i，上端接線柱不超過j的最大不相交集中邊數(電路布線問題的最優值為Size(n，n))。則用動態規劃方法求解的遞推公式如下：

當i=1時: Size(1，j)=0 (j< a1); Size(1，j)=1 (j≥a1)

當i>1時: Size(i，j)= Size(i-1，j) ( j< ai); Size(i，j)=max｛Size(i-1，j)， Size(i-1， ai-1)+1｝ (j≥ ai)

從上面的遞推公式可以看出些算法顯然需要O(n2)計算時間和O(n2)空間。

3 問題轉換

在介紹新算法之前先定義幾個基本名詞。

定義1子序列(Subsequence)。給定字符串A= A[1]A[2]...A[m]，(A[i]是A的第i個字母，A[i]∈字符集∑，1<=i

定義2最長遞增子序列問題。設L=是n個不同的實數的序列，L的遞增子序列是這樣一個子序列Lin=，其中k1

新算法是從電路布線問題解決和關鍵點(求同層電路連線的最多條數)出發。電路板的上接線柱X序列可看成一個升序排列的字符串序列，而與上接線柱相連的連線對應下接線柱形成的新序列L是無序的字符串序列。要使連線不相交，因為上接線柱X序列是遞增的，僅有相應連線對應下接線柱形成的新序列L是遞增序列時才滿足，且連線的最多條數恰等于新序列L中最長遞增子序列的長度。因此電路布線問題就轉換為求最長遞增子序列長度的問題。由圖1所示實例可以驗證其問題轉化的正確性。

從該實例中可以看出：上接線柱序列X=〈1，2，3，4，5，6，7，8〉，連線對應下接線柱形成新序列L=〈2，4，5，7，1，6，8，3〉，序列L的最長遞增子序列為2 4 5 7 8或2 4 5 6 8，最長遞增子序列的長度為5，很容易得出該電路連線的最多線路條數為5條，5條同層的電路連線分別為：（1，2）、（2，4）、（3，5）、（6，6）、（7，8）或（1，2）、（2，4）（3，5）、（4，7）、（7，8）。

4 用二分法求解電路布線問題的算法

設f(i)表示L中以ai為末元素的最長遞增子序列的長度。則有如下的遞推方程：這個遞推方程的意思是，在求以ai為末元素的最長遞增子序列時，找到所有序號在L前面且小于ai的元素aj，即j

lis1(int[] L，int[][]size)

{

int n = L.length;

int[] B = new int[n+1];//數組B；

B[0]=-1;//把B[0]設為最小，假設任何輸入都大于-1；

B[1]=L[0];//初始時，最大遞增子序列長度為1的最末元素為a1

int Len = 1;//Len為當前最大遞增子序列長度，初始化為1；

int p，r，m;//p，r，m分別為二分查找的上界，下界和中點；

for(int i = 1;i

{

p=0;r=Len;

while(p<=r)//二分查找最末元素小于ai+1的長度最大的最大遞增子序列；

{

m = (p+r)/2;

if(B[m]

else r = m-1;

}

B[p] = L[i];//將長度為p的最大遞增子序列的當前最末元素置為ai+1;

if(p>Len) Len++;//更新當前最大遞增子序列長度；

}

System.out.println(Len);//打印輸出該電路連線的最多條數；

}

現在來證明這個算法為什么是正確的。要使算法正確只須證如下命題：

命題1：每一次循環結束數組B中元素總是按遞增順序排列的。

證明：用數學歸納法，對循環次數i進行歸納。

當i=0時，即程序還沒進入循環時，命題顯然成立。

設iB[j2]，因為第i次循環之前數組B是遞增的，因此第i次循環時B[j1]或B[j2]必有一個更新，假設B[j1]被更新為元素ai+1，由于ai+1=B[j1]> B[j2]，按算法ai+1應更新B[j2]才對，因此產生矛盾；假設B[j2]被更新，設更新前的元素為s，更新后的元素為ai+1，則由算法可知第i次循環前有B[j2]＝s< ai+1< B[j1]，這與歸納假設矛盾。命題得證。

命題2：B[c]中存儲的元素是當前所有最長遞增子序列長度為c的序列中，最小的最末元素，即設當前循環次數為i，有B[c]={aj| f(k)=f(j)=c∧k，j≤i+1→aj≤ak}(f(i)為與第二種算法中的f(i)含義相同)。

證明：程序中每次用元素ai更新B[c]時(c=f(i))，設B[c]原來的值為s，則必有ai

命題3：設第i次循環后得到的p為p(i+1)，那么p(i)為以元素ai為最末元素的最長遞增子序列的長度。

證明：只須證p(i)等于第二種算法中的f(i)。顯然一定有p(i)<＝f(i)。假設p(i) p(i))的最長遞增子序列后面，就應該能接在B[L]后面，那么就應該有p(i)=L，與L> p(i)矛盾。因此一定有p(i)＝f(i)，命題得證。

算法的循環次數為n，每次循環二分查找用時logn，所以算法的時間復雜度為O(nlogn)。

5 結束語

本論文所寫的電路布線問題的算法是針對傳統算法復雜度較高的情況下，對其算法作出改進，采用二分法求解此問題提高了算法的運行速度。

參考文獻：

[1] 王曉東.算法設計與分析[M].北京:清華大學出版社，2008:85-88.

[2] Cormen T H，Leisersen C E，Rivest R L，et al.Introduction to Algorithms[M].2nd ed.New York:Mc Graw-Hill，2001.

[3] Sara Baase.Computer Algorithms:Introduction to Design and Analysis[M].3rd ed. Reading， MA:Addison-Wesley，2001.