算法——电路布线

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,动态规划,电路布线,1,动态规划算法整体思想,将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。,子问题之间不是相互独立的,保存已解决的子问题的答案，在需要时再找出已求得的答案，这样可以避免大量的重复计算,2,用一个表格记录所有已解决的子问题的答案,分解若干子问题,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,3,子问题不相互独立，被计算很多次,n,T(n),=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),4,保存已解决问题答案，需要时取出，避免重复计算,子问题之间不相互独立,n,=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,n/2,T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),T(n/4),5,找出最优解的性质，并刻划其结构特征。,递归地定义最优值。,以自底向上的方式计算出最优值。,根据计算最优值时得到的信息，构造最优解。,6,全是理论？,7,问题描述：,在一块电路板的上、下两端分别有n个接线柱。根,据,电路设计，要求用导线(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,8,在制作电路板时，要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets = i，(i)，1 i n的最大不相交子集。,9,1. 最优子结构性质,记N(i,j) = t|(t, (,t,) Nets,t i, (t) j . N(i,j)的最大不相交子集为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).,10, 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)的不相交子集。这与MNS(i,j)的定义相矛盾。,1： (i,(i)MNS(i,j) ，有Size(i,j)=Size(i-1, (i)-1)+1,i =1 2,i-1 i,(i),=1 2,i-1 i j-2 j-1 j ,11,若(i, (i)不属于MNS(i,j)，则对任意(t, (t)MNS(i,j)，有t1时,状态转移顺序,： 自底向上，先算上排接线柱只有1个，2个的最优布线，然后求上排接线柱有多个的最优布线。,关键一步，写出递归表达式,13,3. 根据上面递归式可以得到二维表：,红色标明的就是算法选择的路径,，,向上优先,。在斜角值改变时可以取得所求的子集。,即 9,10,7,9,5,5,3,4,14,设计动态规划算法如下。其中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; j1; i-),if (sizeij!=sizei-1j/,此时(i,c(i)是最大不相交子集中的一条边,Netm+=i;,j=Ci-1;/,更新扩展连线柱区间,if (j=C1) /,处理i=1的情形,Netm+=1;,16,