《《算法电路布线》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《算法电路布线》PPT课件.ppt（16页珍藏版）》请在三一办公上搜索。
1、动态规划,电路布线,动态规划算法整体思想,将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。子问题之间不是相互独立的保存已解决的子问题的答案，在需要时再找出已求得的答案，这样可以避免大量的重复计算,用一个表格记录所有已解决的子问题的答案 分解若干子问题,子问题不相互独立，被计算很多次,保存已解决问题答案，需要时取出，避免重复计算,子问题之间不相互独立,找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。,全是理论？,问题描述：在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线
2、(i,(i)将上端接线柱i与下端接线柱(i)相连，如下图。其中，(i),1 i n,是1,2,n的一个排列。导线(I,(i)称为该电路板上的第i条连线。对于任何1 i j n,第i条连线和第j条连线相交的充要条件是(i)(j).（i）=8，7，4，2，5，1，9，3，10，6,在制作电路板时，要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets=i，(i)，1 i n的最大不相交子集。,1.最优子结构性质 记N(i,j)=t|(t,(t)Nets,t i,(t)j.N(i,j)
3、的最大不相交子集为MNS（i,j）Size(i,j)=|MNS(i,j)|。（1）当i=1时（2）当i 1时，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,(t)MNS(i,j)有t i且(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)的不相
4、交子集。这与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.递归计算最优值 电路布线问题的最优值为Size(n,n)。由该问题的最优子结构性质可知，子问题最优值的递归关系如下：,(1)当i=1时(2)当i1时,状态转移顺序：自底向上，先算上排接线柱只有1个，2个的最优布线，然后求上排接线
5、柱有多个的最优布线。,关键一步，写出递归表达式,3.根据上面递归式可以得到二维表：,红色标明的就是算法选择的路径，向上优先。在斜角值改变时可以取得所求的子集。即 9 10,79,55,34,设计动态规划算法如下。其中sizeij表示函数Size（i，j）的值。void MNS(C,n,*size)for(j=0;jC1;j+)size1j=0;for(j=C1;j=n;j+)size1j=0;for(i=2;in;i+)for(j=0;jCi;j+)sizeij=sizei-1j;/j(i)的情况 for(j=Cj;j=n;j+)/j=(i)的情况 sizeij=maxsizei-1j,sizei-1Ci-1+1;sizenn=maxsizen-1n,sizen-1Cn-1+1;,4.构造最优解,void Traceback(C,*size,n,Net,m)int j=n;m=0;for(int i=n;i1;i-)if(sizeij!=sizei-1j/此时(i,c(i)是最大不相交子集中的一条边 Netm+=i;j=Ci-1;/更新扩展连线柱区间 if(j=C1)/处理i=1的情形 Netm+=1;,
