算法分析报告与设计课程设计：电路布线

1、2岁密/殳#数学与计算科学学院 学院 信息与计算科学 专业 匚班课程名称 算法分析与设计题 目 电路布线学生姓名学号200*任务起止日期：2010年12月20日2010年1月3日指导教师教研室主任年 月 日审杳目录0 / 10222第三章问题的解决 33.1方案一：动态规划 33.2方案二：分支定界法59在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线(i, n (i) 将w i n,是 1,2,n 上端接线柱i与下端接线柱n (i)相连，如如下图。其中，n (i),1的一个排列。导线(I, n (i)称为该电路板上的第i条连线。对于任何 1 w i w j w n,第i条连

2、线和第j条连线相交的充要条件是n (i) n (j).23+56759102孑 斗 567 S 910图1-1在制作电路板时，要求将这n条线分布到假如干个绝缘层上，在同一层上的连线不能相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets = i , n (i) , 1 w i w n 的最大不想交子集。为确定导线集 Nets =i , n (i) , 1 w i 1时, j n (i)。此时，假如(i,n (i) MNS(i,j),如此对任意(t,n (i) MNS(i,j)n (i)n (i)盾。且 n (t)是 N(i-1,N

3、(i,j)假如(i, nn (i);否如此,(t,n (t)与(i, n (i)相交。在这种情况下MNS(i,j)-(i,n (i)-1)的最大不相交子集。否如此，子集是比MNS(i,j)更大的N(i,j) 的不相交子集。(i)不属于MNS(i,j)，如此对任意(t, n (t)MNS(i-1, n (i)-1) U (i,这与 MNS(i,j)的定义相矛 MNS(i,j)，有 t Size(i-1,j) ，从而 Sizei,j = Size(i-1,j) 。在布线区域叠上一个网格，该网格把布线区域划分成n x m个方格，如图6 - 11a 所示。从一个 方格a的中心点连接到另一个方格 b的中

4、心点时，转弯处必须采用直角，如图2-1 b所示。如果 已经有某条线路经过一个方格，如此封锁该方格。我们希望使用a和b之间的最短路径来作为布线的路径，以便减少信号的延迟。1ai- 5a)曲a) 7 x 7网格b) a与b之间的电线图2-1电路布线示例从起点位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可 行结点被参加到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，算法从活结点队列中取出对手结点作为下一个扩展结点，并将与当前扩展结 点相邻并且未标记过的方格标记为2,并存入活结点队列，这个过程一直持续到算法搜索到目标方格b或活结点队列为空时为止

5、。第三章.问题的解决3.1方案一：动态规划经以上后分析，可电路布线问题的最优值为Size( n,n)。由该问题的最优子结构性质可知：1)当i=1时，Size(1, j)0，j1，j(1)(1)2当i1时,Size(i, j)Size(i 1,j),j(i)max Size(i 1, j), Size(i 1, (i) 1) 1, jsizeij据此可设计解电路布线问题的动态规划算法如下，其中，用二维数组单元 表示函数Size(i ，j)void MNS(int C, int n, int *size) / /对于所有的i和j，计算s i z e i j / / 初始化 s i z e 1 *

6、for (int j = 0; j C1; j+)size1j = 0;for (j = C1; j = n; j+)size1j = 1;/ 计算 sizei*, 1 i nfor (int i = 2; i n; i+) for (i nt j = 0; j Ci; j+)sizeij = sizei-1j;for (j = Ci; j 1; i-)/ i 号 n e t 在 M N S 中？if (sizeij != sizei-1j)Netm+ = i;j = Ci - 1；/ 1 号网组在M N S中？if (j = C1)netm+ = 1; / 在 M N S 中此方案的计算复杂

7、度：算法MNS需要2n计算时间和2n空间。算法traceback需要 n计算时间。源程序与运行结果见附录。3.2方案二：分支定界法为了找到网格中位置 a和b之间的最短路径，先从位置a开始搜索，把a可到达的相邻方格都标记为1表示与a相距为1，然后把标号为1的方格可到达的相邻方格都标记 为2表示与a相距为2，继续进展下去，直到到达 b或者找不到可到达的相邻方格为止。图6-12a演示了这种搜索过程，其中a = ( 3,2 ), b = ( 4,6 )。图中的阴影方格都是被封锁的方格。b)电线路径图3-1电路布线按照上述搜索过程，当我们到达b时，就可以在b上标出b与a之间的距离，在图3-1(a) 中，

8、匕上的标号为9。为了得到a与b之间的最短路径，从b开始，首先移动到一个比b的编号小的相邻位置上。一定存在这样的相邻位置，因为任一个方格上的标号与它相邻方格上 的标号都至少相差1。在图3-1(a)中，可从b移动到(5 , 6 )。接下来，从当前位置开始， 继续移动到比当前标号小1的相邻位置上，重复这个过程，直至到达a为止。在图3-1(a)的例子中，从(5,6 ) 移动到(6,6 ), ( 6,4 ), ( 5,4 )，。图3-2(b) 给出了所得到的路径。一个mK m的网格被描述成一个二维数组，其中用0表示空白的位置，1表示被封锁的位置。整个网格被包围在一堵由1构成的“墙中。数组offsets用

9、来帮助从一个位置移动到其相邻位置。用一个链表队列来跟踪这样的方格：该方格本身已被编号，而它的相邻位置尚未被编号。也可以采用公式化队列，所不同的是必须估计队列的最大长度，就像在求解迷宫问题时估计堆栈的大小一样。寻找电路布线最短路径的程序如下：bool Fin dPath(Positi on start, Positi on fini sh, int& PathLe n, Positi on *&path) / / 寻找从s t a r t 到f i n i s h 的路径/如果成功，如此返回t r u e，否如此返回f a l s e/如果空间不足，如此引发异常N o M e mif (star

10、t.row = fini sh.row) &(start.col = fini sh.col)PathLe n = 0; return true; / start = finish/初始化包围网格的“围墙for (int i = 0; i = m+1; i+) grid0i = gridm+1i = 1; /底和顶gridi0 = gridim+1 = 1; /左和右/初始化o ff s e tit+ 1;/完成o ffset0.row =0; offset0.col =:1; /右o ffset1.row =1; offset1.col =:0; /下o ffset2.row =0; off

11、set2.col =:-1; /左o ffset3.row =-1; offset3.col :=0; /上Position off s e t 4 ;int NumOfNbrs = 4; /一个网格位置的相邻位置数Positi on here, nbr;here.row = start.row;here.col = start.col;gridstart.rowstart.col = 2; /圭寸锁/标记可到达的网格位置Lin kedQueue Q;do /标记相邻位置for (int i = 0; i = 0; j-) pathj = here;/寻找前一个位置for (int i = 0

12、; i NumOfNbrs; i+) n b r.row = here.row + off s e t i . r o w ;n b r.col = here.col + off s e t i . c o l ;if (gridnbr. r o w n b r.col = j+2) break;here = nbr; /移动到前一个位置return true;在程序的中，假定起始位置和完毕位置均未被封锁。程序首先检查s t a r t和fi n i s h是 否一样，如果一样，如此路径长度为0,程序终止。否如此设置一堵由封锁位置构成的“围墙，把网格包围起来。然后对o ff s e t数组进展

13、初始化，并在起始位置上标记2。所有标号都增加了2,因为数组中采用 0和1来表示空白位置和封锁位置，为了得到如图6-12a所示的标号，必须把程序中的每个标号减去2。借助于队列 Q并从位置s t a r t 开始，首先移动到与 s t a r t 相距为1的网格位置，然后移动到与 s t a r t相距为2的网格位置，不断进展下去，直到到达位置 f i n i s h或者无法继续移动到一个新的、空白的位置。在后一种情况下，将不存在到达位置f i n i s h的路径，而在前一种情况下，位置 f i n i s h将得到一个相应的编号，如果到达了位置f i n i s h ,如此可以利用网格上的标号来重构路径。路径上的位置start 除外均被存储在数组p at h之中。由于任意一个网格位置都至多在队列中出现1次，所以完成网格编号过程需耗时8 / 10m2 对一个 m x m的网格来说。而重构路径的过程需耗时0(L)，其中L为最短路径的长度。对于在一块电路板的上、 下两端分别有n个接线柱，在制作电路板时，要求将这n条线 分布到假如干个绝缘层上，在同一层上的连线不能相交德问题。要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。方案一将待求解问题分解成假如