摘 要：常用的解决电路布线问题的算法的时间和空间的复杂度都是O(n2)。这里n为一块电路板的上端（或下端）接线柱的个数。现给出一种时间复杂度为O(nlogn)的新算法。相对传统的算法来说，此算法是一种快速算法，提高了算法运行速度。
　　关键词：算法；电路布线；堆的数据结构
　　中图分类号:TP301.6 文献标识码:A
　　
　　One Fast Algorithm for the Circuit Wiring Question
　　ZHANG Li-xiang1,ZHAO Xue-feng1,WANG Yu2
　　(1. the North West Normal University,GanSu LanZhou 730070；2. Pingliang Maternal and Child Health Hospital, Gansu Pingliang 744000)
　　Key words: algorithm；circuit wiring；construction of data for heap
　　
　　在一块电路板的上下两端分别有n个接线柱。根据电路设计，要求用导线（i，j）将上端接线柱i和下端接线柱j相连，如图1所示。其中X=〈1,2,…n〉的一个排列，Y==〈1,2,…n〉的一个排列。导线（X,Y）称为电路板上的连线。因为上接线术是个递增的序列，要使电路连线不相交的充分必要条件是与连线对应的下接线柱形成的新序列必须是递增序列时才满足。在制作电路板时，要求将这n条连线分布到若干绝缘层上，在同一层上的连线不相交。电路布线问题要确定哪些连线安排在第一层上，使得该层上有尽可能多的连线。即该问题要求确定导线连线的最大不相交的条数。
　　


　　图1 电路布线实例
　　1 用动态规划方法求解电路布线问题
　　设Size[i][j]为下端接线柱不超过j，上端接线柱不超过i的最大不相交集中边数(电路布线问题的最优值为Size(n,n))。则用动态规划方法求解的递推公式如下：
　　当i=1时:Size(1,j)=0 (j< a ); Size(1,j)=1 (j≥a1)
　　当i>1时:Size(i,j)=Size(i-1,j)(j　　据此可设计解电路布线问题的动态规划算法mnset如下。其中用二维数组单元size[i][j]表示函数Size(i,j)的值。由算法traceback构造出最优解MNS(n,n)，用数组net[0:m-1]存储MNS(n,n)中的m条连线。用JAVA实现的程序代码如下：
　　Public static void mnset(int []c, int [][]size)
　　 {
　　int n=c.length-1;
　　for (int j=0;j　　size[1][j]=0;
　　for (int j=c[1];j<=n;j++
　　size[1][j]=1;
　　for (int i=2;i　　{
　　 for (int j=0;j　　 size[i][j]=size[i-1][j];
　　for (int j=c[i];j<=n;j++)
　　size[i][j]=Math.max(size[i-1][j], size[i-1][c[i]-1]+1);
　　}
　　size[n][n]=Math.max(size[n-1][n], size[n-1][c[n]-1]+1);
　　}
　　Public static int traceback(int []c, int [][]size,int []net)
　　{
　　 int n=c.length-1;
　　 int j=n;
　　 int m=0;
　　 for (int i=n;i>1;i--)
　　if (size[i][j]!=size[i-1][j])
　　{
　　 net[m++]=i;
　　 j=c[i]-1;
　　}
　　 if (j>c[1])
　　 net[m++]=1;
　　return m;//m为电路连线最大条数；
　　}
　　算法mnset显然需要O(n2)计算时间和O(n2)空间。算法traceback需要O(n)计算时间。
　　
　　2 用堆的数据结构求解电路布线问题
　　
　　新算法采用了一种有趣的数据结构（堆的数据结构[3]）结合[4]中的技术来解决电路布线问题,该算法也是解决LCS问题的一种有效算法.如图2所示针对图1的实例来说明。M为配对点的集合，(i,j)为配对点在结构图中的位置（i为表的行，j为表的列）。
　　


　　图2 电路布线的配对点的结构图M(针对图1的实例)
　　从图2可以看出每个配对点(i,j)∈M是电路的连线，要使电路同层连线最多（不相交），必须是堆结构中的配对点的行列同时递增，才能前后相连形成最长的堆链。最长堆链的长度等于同层电路连线的最多条数，其堆链上的各个配对点(i,j )表示电路的各条连线。由图2的实例中可以验证新算法的正确性。图中最长堆链长度为5恰等于该电路同层的最多连线5条，5条连线分别为（1,2）（2,4）（3,5）（4,7）（7,8）或（1,2）（2,4）（3,5）（6,6）（7,8）。
　　按照动态规划的方法求解T[i,j]（见[4].）,依照下面公式(1).
　　当(i,j)∈M, T[i,j]没有定义;当i=1或j=1时, T[i,j]=1;当i,j≠1且(i,j)∈M时,T[i,j]=1+max{ T(li,lj)}(1≤li≤i,1≤lj≤j, (li,lj)∈M)（公式(1)）。
　　在新算法中用到了[4]中的算法1，需要按行来计算M的集合。同时应用公式(1)来计算每个M中T[i,j]也有效的应用了[4]中两个定理。
　　定理1.[4]设(i,j)∈M,那么对所有的i′>i,j′>j可推出T[i′,j]≥T[i,j],T[i,j′]≥T[i,j].
　　定理2.[4]要计算出T[i,j]( (i,j)∈M,1≤i,j≤n)是独立于任何T[i,q]( (i,q)∈M,1≤q≤n).
　　依照上面两个定理我们用[3]中的数据结构里的有界堆（Boundedheap）来对堆进行以下操作：
　　插入操作Insert(H,Pos,Value,Data),把Pos点的值插入到有界堆H中。
　　添加操作IncreaseValue(H,Pos,Value,Data),如果堆H中没有包含Pos点的值，执行上面的插入操作，否则，在此位置放入最大值max,max={max,max′},max′为先前的最大值，此操作之后更新当前的最大值。
　　求界堆的最大值操作BoundedMax(H,Pos).返回H中的最大的那个数据的值，且堆中的所有数据的位置小于返回数据的当前位置。如果H堆中没有任何数据的位置小于当前数据的位置，返回0值。
　　新算法的推理过程如下。首先按行执行操作，同时解决两个界堆的数据结构。当考虑第i行时，已经有界堆Hi-1的数据结构，来构造Hi的数据结构。
　　第一步，Hi初始化为Hi-1。设配对点(i,j)∈M，1≤j≤n，Mi={(i,j)| (i,j)∈M,1<=j<=n}.
　　第二步，按公式(2)、(3)计算T[i,j]. T[i,j].Value=BoundedMax(Hi-j,j).Value+1(公式（2）)
　　T[i,j].Prev=BoundedMax(Hi-j,j).data(公式（3）)。
　　第三步，执行添加操作：IncreaseValue(Hi,j,T[i,j].Value,(i,j)) (公式（4）).
　　由定理1和定理2可以验证以上步骤的正确性。一旦算出第j列新配对点T-Value值,就不用管第j列以前的配对点。因此在计算第i行的T[i,j]时，就把此值插入到堆Hi中，是为更新下一行的新值做准备。比如说，用堆Hi-1来计算第i行的配对点处的T-Value值且更新堆Hi。接着用Hi准备下行第i+1行的计算。具体新算法的实现代码如下:
　　Construct the set M using Algorithm 1 of [4].
　　Let M ={(i,j)| (i,j)∈M,1<=j<=n}.
　　globalLCS.Instance=∈
　　globalLCS.Value=∈
　　H0=∈//开始堆为空
　　for i=1 to n do//按行对Mi进行操作
　　Hi=Hi-1
　　for each(i,j)∈Mi do //对Mi中元素按从左向右执行
　　maxresult = BoundedMax(Hi-1,j)
　　T[i,j].Value = maxresult.Value+1
　　T[i,j].Prev = maxresult.Instance
　　if globalLCS.Value < T[i,j].Value then
　　 globalLCS.Value = T[i,j].Value
　　 globalLCS.Instance = (i.j)
　　end if
　　IncreaseValue(H ,j, T[i,j].Value,(i,j)).
　　end for
　　DeleteHi-1
　　end for
　　return globalCLS//返回堆链中最长那条链的长度即为所求连线的最多条数
　　此算法复杂度显然是O(nlogn)，n为上（或下）接线柱序列的长度。
　　
　　3 结束语
　　
　　本论文所写的电路布线问题的算法是针对传统算法复杂度较高的情况下，对其算法作出改进，采用堆的数据结构解决此问题，从而提高了算法的运行速度。
　　
　　参考文献：
　　[1]王晓东.算法设计与分析[M].北京:清华大学出版社,2008.
　　 [2]Costas S.Iliopouslos,M.Sohel Rahman.New efficient algorithms for the lcs and constrained lcs problems,England,UK.Information processing letters.106(2008)13-18.
　　[3]G.S. Brodal, K.Kaligosi, I. Katriel, M. Kutz, Faster algorithms for computing longest common increasing subsequences, in:M.Lewenstein, G.Valiente(Eds.) ,Annual Symposium on Combinatorial Pattern Matching(CPM), In: Lecture Notes in Computer Science,vol.4009,Springer,2006.330-341.
　　[4]M.S.Rahman, C.S. Iliopoulos,Algorithms for computing variants of the longest common subsequence.