算法-电路布线课件

动态规划电路布线动态规划电路布线1动态规划算法整体思想将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。子问题之间不是相互独立的保存已解决的子问题的答案，在需要时再找出已求得的答案，这样可以避免大量的重复计算动态规划算法整体思想将待求解问题分解成若干个子问题，先求解子2用一个表格记录所有已解决的子问题的答案

分解若干子问题

nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=3子问题不相互独立，被计算很多次nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)子问题不相互独立，被计算很多次nT(n)=n/2T(n/4)4保存已解决问题答案，需要时取出，避免重复计算

子问题之间不相互独立

n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)保存已解决问题答案，需要时取出，避免重复计算n=n/2T(n5找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。找出最优解的性质，并刻划其结构特征。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｝的最大不相交子集。在制作电路板时，要求将这n条连线分布到若干绝缘层上。在91.最优子结构性质

记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).1.最优子结构性质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)+1i=｛12…i-1i｝π(i)=｛12…i-1ij-2j-1j｝②j≥π(i)。此时，若(i,π(i))∈MNS11若(i,π(i))不属于MNS(i,j)，则对任意(t,π(t))∈MNS(i,j)，有t<i。从而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：(i,π(i))不属于MNS(i,j)，有Size(i,j)=Size(i-1,j)i=｛12…i-1i｝π(i)=｛12…i-1ij-1j｝若(i,π(i))不属于MNS(i,j)，则对任意(t,122.递归计算最优值电路布线问题的最优值为Size(n,n)。由该问题的最优子结构性质可知，子问题最优值的递归关系如下：

(1)当i=1时(2)当i>1时

状态转移顺序：自底向上，先算上排接线柱只有1个，2个的最优布线，然后求上排接线柱有多个的最优布线。关键一步，写出递归表达式2.递归计算最优值(1)当i=1时状态转移顺133.根据上面递归式可以得到二维表：

红色标明的就是算法选择的路径，向上优先。在斜角值改变时可以取得所求的子集。即9→10,7→9,5→5,3→43.根据上面递归式可以得到二维表：

红色标明的14设计动态规划算法如下。其中size[i][j]表示函数Size（i，j）的值。voidMNS(C[],n,**size){

for(j=0;j<C[1];j++)size[1][j]=0;for(j=C[1];j<=n;j++)size[1][j]=0;for(i=2;i<n;i++){for(j=0;j<C[i];j++)size[i][j]=size[i-1][j];//j<π(i)的情况for(j=C[j];j<=n;j++)//j〉=π(i)的情况

size[i][j]=max{size[i-1][j],size[i-1][C[i]-1]+1};}size[n][n]==max{size[n-1][n],size[n-1][C[n]-1]+1};}算法——电路布线课件154.构造最优解voidTraceback(C[],**size,n,Net[],m){intj=n;m=0;for(inti=n;i>1;i--)if(size[i][j]!=size[i-1][j]//此时(i,c(i))是最大不相交子集中的一条边{Net[m++]=i;j=C[i]-1;//更新扩展连线柱区间}if(j>=C[1])//处理i=1的情形Net[m++]=1;}4.构造最优解voidTraceback(C[],**s16动态规划电路布线动态规划电路布线17动态规划算法整体思想将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。子问题之间不是相互独立的保存已解决的子问题的答案，在需要时再找出已求得的答案，这样可以避免大量的重复计算动态规划算法整体思想将待求解问题分解成若干个子问题，先求解子18用一个表格记录所有已解决的子问题的答案

分解若干子问题

nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=19子问题不相互独立，被计算很多次nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)子问题不相互独立，被计算很多次nT(n)=n/2T(n/4)20保存已解决问题答案，需要时取出，避免重复计算

子问题之间不相互独立

n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)保存已解决问题答案，需要时取出，避免重复计算n=n/2T(n21找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。找出最优解的性质，并刻划其结构特征。22全是理论？全是理论？23问题描述：

在一块电路板的上、下两端分别有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｝问题描述：24在制作电路板时，要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets=｛i，π(i)，1≤i≤n｝的最大不相交子集。在制作电路板时，要求将这n条连线分布到若干绝缘层上。在251.最优子结构性质

记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).1.最优子结构性质26

②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)+1i=｛12…i-1i｝π(i)=｛12…i-1ij-2j-1j｝②j≥π(i)。此时，若(i,π(i))∈MNS27若(i,π(i))不属于MNS(i,j)，则对任意(t,π(t))∈MNS(i,j)，有t<i。从而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：(i,π(i))不属于MNS(i,j)，有Size(i,j)=Size(i-1,j)i=｛12…i-1i｝π(i)=｛12…i-1ij-1j｝若(i,π(i))不属于MNS(i,j)，则对任意(t,282.递归计算最优值电路布线问题的最优值为Size(n,n)。由该问题的最优子结构性质可知，子问题最优值的递归关系如下：

(1)当i=1时(2)当i>1时

状态转移顺序：自底向上，先算上排接线柱只有1个，2个的最优布线，然后求上排接线柱有多个的最优布线。关键一步，写出递归表达式2.递归计算最优值(1)当i=1时状态转移顺293.根据上面递归式可以得到二维表：

红色标明的就是算法选择的路径，向上优先。在斜角值改变时可以取得所求的子集。即9→10,7→9,5→5,3→43.根据上面递归式可以得到二维表：

红色标明的30设计动态规划算法如下。其中size[i][j]表示函数Size（i，j）的值。void