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

实用文案标准文档数学与计算科学学院学院信息与计算科学专业***班课程名称算法分析与设计题目电路布线任务起止日期：2010年12月20日～2010年1月3日学生姓名**学号200*******指导教师教研室主任年月日审查1目录第一章.问题描述..........................................................2第二章.问题分析..........................................................32.1用动态规划分析...................................................32.2用分支定界法分析.................................................3第三章．问题的解决.......................................................53.1方案一：动态规划.................................................53.2方案二:分支定界法................................................6第四章.总结.............................................................112第一章.问题描述在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))将上端接线柱i与下端接线柱π(i)相连，如下图。其中，π(i),1≤i≤n,是｛1,2,…,n｝的一个排列。导线(I,π(i))称为该电路板上的第i条连线。对于任何1≤i≤j≤n,第i条连线和第j条连线相交的充要条件是π(i)π(j).图1-1在制作电路板时，要求将这n条线分布到若干个绝缘层上，在同一层上的连线不能相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets=｛i，π(i)，1≤i≤n｝的最大不想交子集。3第二章.问题分析2.1用动态规划分析为确定导线集Nets=｛i，π(i)，1≤i≤n｝的最大不想交子集，将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。现分析最优子结构性质。记N(i,j)={t|(t,π(i))∈Nets,t≤i,π(t)≤j}.N(i,j)的最大不相交子集为MNS（i,j）。Size(i,j)=|MNS(i,j)|。1）当i=1时1},1,1{1,),1(),1(jjjNjMNS空2)当i1时，①jπ(i)。此时，(i,π(i))不属于N(i,j)。故在这种情况下，N(i,j)=N(i-1,j)，从而Size(i,j)=Size(i-1,j)。②j≥π(i)。此时，若(i,π(i))∈MNS(i,j)，则对任意(t,π(i))∈MNS(i,j)有ti且π(t)π(i)；否则，(t,π(t))与(i,π(i))相交。在这种情况下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。否则，子集MNS(i-1,π(i)-1)∪{(i,π(i))}N(i,j)是比MNS(i,j)更大的N(i,j)的不相交子集。这与MNS(i,j)的定义相矛盾。若(i,π(i))不属于MNS(i,j)，则对任意(t,π(t))∈MNS(i,j)，有ti。从而MNS(i,j)包含于N(i-1,j)，因此，Size(i,j)≤Size(i-1,j)。另一方面，MNS(i-1,j)包含于N(i,j),故又有Size(i,j)≥Size(i-1,j)，从而Size（i,j）=Size(i-1,j)。2.2用分支定界法分析在布线区域叠上一个网格，该网格把布线区域划分成n×m个方格，如图6-11a所4示。从一个方格a的中心点连接到另一个方格b的中心点时，转弯处必须采用直角，如图2-1（b）所示。如果已经有某条线路经过一个方格，则封锁该方格。我们希望使用a和b之间的最短路径来作为布线的路径，以便减少信号的延迟。a)7×7网格b)a与b之间的电线图2-1电路布线示例从起点位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，算法从活结点队列中取出对手结点作为下一个扩展结点，并将与当前扩展结点相邻并且未标记过的方格标记为2，并存入活结点队列，这个过程一直持续到算法搜索到目标方格b或活结点队列为空时为止。5第三章．问题的解决3.1方案一：动态规划经以上后分析，可电路布线问题的最优值为Size(n,n)。由该问题的最优子结构性质可知：1)当i=1时，)1(,1)1(,0),1(jjjSize2）当i1时，)(,1)}1)(,1(),,1(max)(),,1(),(ijiiSizejiSizeijjiSizejiSize据此可设计解电路布线问题的动态规划算法如下，其中，用二维数组单元size[i][j]表示函数Size(i，j)voidMNS(intC[],intn,int**size){//对于所有的i和j，计算size[i][j]//初始化size[1][*]for(intj=0;jC[1];j++)size[1][j]=0;for(j=C[1];j=n;j++)size[1][j]=1;//计算size[i][*],1infor(inti=2;in;i++){for(intj=0;jC[i];j++)size[i][j]=size[i-1][j];for(j=C[i];j=n;j++)size[i][j]=max(size[i-1][j],size[i-1][C[i]-1]+1);6}size[n][n]=max(size[n-1][n],size[n-1][C[n]-1]+1);}接着，构造最优解：根据算法MNS计算出的size[i][j]值，容易由算法traceback构造出最后解MNS（n,n）。voidTraceback(intC[],int**size,intn,intNet[],int&m){//在Net[0:m-1]中返回MMSintj=n;//所允许的底部最大针脚编号m=0;//网组的游标for(inti=n;i1;i--)//i号net在MNS中?if(size[i][j]!=size[i-1][j]){//在MNS中Net[m++]=i;j=C[i]-1;}//1号网组在MNS中?if(j=C[1])net[m++]=1;//在MNS中}此方案的计算复杂度：算法ＭＮＳ需要2n计算时间和2n空间。算法ｔｒａｃｅｂａｃｋ需要n计算时间。源程序及运行结果见附录。3.2方案二:分支定界法为了找到网格中位置a和b之间的最短路径，先从位置a开始搜索，把a可到达的相邻方格都标记为1（表示与a相距为1），然后把标号为1的方格可到达的相邻方格都标记为2（表示与a相距为2），继续进行下去，直到到达b或者找不到可到达的相邻方格为止。7图6-12a演示了这种搜索过程，其中a=(3,2)，b=(4,6)。图中的阴影方格都是被封锁的方格。a)标识间距b)电线路径图3-1电路布线按照上述搜索过程，当我们到达b时，就可以在b上标出b与a之间的距离，在图3-1(a)中，b上的标号为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)给出了所得到的路径。一个m×m的网格被描述成一个二维数组，其中用0表示空白的位置，1表示被封锁的位置。整个网格被包围在一堵由1构成的“墙”中。数组offsets用来帮助从一个位置移动到其相邻位置。用一个链表队列来跟踪这样的方格：该方格本身已被编号，而它的相邻位置尚未被编号。也可以采用公式化队列，所不同的是必须估计队列的最大长度，就像在求解迷宫问题时估计堆栈的大小一样。寻找电路布线最短路径的程序如下：boolFindPath(Positionstart,Positionfinish,int&PathLen,Position*&path){//寻找从start到finish的路径8//如果成功，则返回true，否则返回false//如果空间不足，则引发异常NoMemif((start.row==finish.row)&&(start.col==finish.col)){PathLen=0;returntrue;}//start=finish//初始化包围网格的“围墙”for(inti=0;i=m+1;i++){grid[0][i]=grid[m+1][i]=1;//底和顶grid[i][0]=grid[i][m+1]=1;//左和右}//初始化offsetPositionoffset[4];offset[0].row=0;offset[0].col=1;//右offset[1].row=1;offset[1].col=0;//下offset[2].row=0;offset[2].col=-1;//左offset[3].row=-1;offset[3].col=0;//上intNumOfNbrs=4;//一个网格位置的相邻位置数Positionhere,nbr;here.row=start.row;here.col=start.col;grid[start.row][start.col]=2;//封锁//标记可到达的网格位置LinkedQueuePositionQ;do{//标记相邻位置for(inti=0;iNumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){//unlabelednbr,labelitgrid[nbr.row][nbr.col]=grid[here.row][here.col]9+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成Q.Add(nbr);}//if结束}//for结束//已到达finish吗?if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成//未到达finish，可移动到nbr吗?if(Q.IsEmpty())returnfalse;//没有路径Q.Delete(here);//到下一位置}while(true);//构造路径PathLen=grid[finish.row][finish.col]-2;path=newPosition[PathLen];//回溯至finishhere=finish;for(intj=PathLen-1;j=0;j--){path[j]=here;//寻找前一个位置for(inti=0;iNumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==j+2)break;}here=nbr;//移动到前一个位置}returntrue;}在程序的中，假定起始位置和结束位置均未