算法分析与设计课程设计电路布线.doc

算法分析与设计课程设计电路布线.doc:..数学与计算科学学院学院信息与计算科学专业怛班课程名称 算法分析与设计 题目 电路布线 任务起止H期:2010年12月20H〜2010年1月3H学生姓名** 学号200*******教研室主任指导教 32」用动态规划分析 53」方案一:动态规划 :分支定界法 11第一章•问题描述在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(ij(i))将上端接线柱i与下端接线柱兀⑴相连,如下图。英中,兀(i),lWivWn,是{1,2,…,n}的一个排列。导线(I,兀⑴)称为该电路板上的第i条连线。对于任何1WiWjWn,第i条连线和第j条连线相交的充要条件是兀(i)>兀①.123456789 ********** 10图1-1在制作电路板时,要求将这n条线分布到若干个绝缘层上,在同一层上的连线不能相交。电路布线问题要确定将哪些连线安排在第-层上,使得该层上有尽可能多的连线。换句话说,s二{i,兀(i),1WiWn}的最大不想交子集。{i,兀⑴,1WiWn}的最大不想交子集,将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。现分析最优子结构性质。记N(i,j)= n(i))eNets,tWi,兀⑴Wj}.N(i,j)的最大不相交子集为MNS(i,j)oSize(i,j)=|MNS(i,j)|o1)当i二1时(空,丿5(1)叫皿沪I爲)U)2)当i>l时,①jG(i)。此时,(i"(i))不属于N(i,j)。故在这种情况下,N(i,j)=N(i-l,j),从而Size(i,j)=Size(i-1,j)。②j»(i)0此时,若(i,n(i))eMNS(i,j),则对任意(t,n(i))WMNS(i,j)有tvi且兀(t)<n(i);否则,(t,兀(t))与(i,兀(i))相交。在这种情况下MNS(i,j)・{(i,"))}是N(i-1,n(i)-l)的最大不相交子集。否则,子集MNS(i・l,兀(i)・l)U{(i,n(i))}cN(i,j)是比MNS(i,j)更大的N(i,j)的不相交子集。这与MNS(i,j)的定义相矛盾。若(i,口⑴)不属于MNS(i,j),则对任意(t,兀⑴疋MNS(i,j),有tvi。从而MNS(i,j)包含于N(i・l,j),因此,Size(i,j)WSize(i・l,j)。另一方面,MNS(i-l,j)包含于N(i,j),故又有Size(i,j)$Size(i・l,j),从而Size(i,j)=Size(i-1j),该网格把布线区域划分成nXm个方格,如图6・11a所示。从一个方格a的中心点连接到另一个方格b的中心点时,转弯处必须采用直角,如图2-1(b)所示。如果已经有某条线路经过一个方格,则封锁该方格。我们希望使用a和b之间的最短路径来作为布线的路径,以便减少信号的延迟。•1-111ba)I!ba)7X7网格图2・1电路布线示例b)b)a与b之间的电线从起点位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中,并且将这些方格标记为1,即从起始方格a到这些方格的距离为1。接看,算法从活结点队列中取出对手结点作为下一个扩展结点,并将与当前扩展结点相邻并且未标记过的方格标记为2,并存入活结点队列,这个过程一直持续到算法搜索到目标方格b或活结点队列为空时为止。:动态规划经以上后分析,可电路布线问题的最优值为Size(n,n)0由该问题的最优子结构性质可知:1)当i=l时,[0,7<>T(1)Size(lJ)=\2)当i>l时,S・「・)js滋(i-1丿,八兀0)','1max{Szze(z-1,j),Size(i-\,兀⑴+j>兀⑴据此可设计解电路布线问题的动态规划算法如下,其屮,用二维数组单元size[i][j]表示函数Size(i,j)voidMNS(intC[],intn,int**size){//对于所有的i和j,计算size[i][j]//初始化size[1][*]for(intj=0;j<C[l];j++)size[l][j]=0;for(j=C[l];j<=n;j++)size[l][j]=1;//计算size[i][*],1<i<nfor(inti=2;i<n;i++){for(intj=0;j<C[i];j++)size[ilfj]=size[i-l][j];for(j=C[i];j