转载

【动态规划】---电路布线

问题描述:

在一块电路板的上、下两端分别有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}

在制作电路板时,要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。换句话说,该问题要求确定导线集Nets = {i,π(i),1 ≤ i ≤ n}的最大的一个子集,这个子集中的导线互相不相交。

问题分析:

 显然这是一个组合问题,对于组合问题中求最优解的方法基本都是动态规划算法。现在表述一下如何划分子问题:

用B(i,j)表示最优解,其中,i是上端接线柱的序号,j是下端接线柱的序号,B(i,j)表示序号小于或等于i的上端接线柱和序号小于或等于j的下端接线柱中不相交连线的最大集合。  用size(i,j)表示集合中导线的数目(size(i,j)=|B(i,j)|)。B(i,j)的值蕴含在B(i-1,j)和B(i,j-1)这俩个子问题中,对于有2xN个接线柱的电路板,那么B(N,N)就是其解了。

对于上端接线柱t,用 π(t)表示与他相连的下端接线柱

那么递推公式为:

B(i-1,j-1)U{(i,j)},( j==π(i))

B(i,j)=

size(i-1,j)>size(i,j-1)?B(i-1,j):B(i,j-1) ,(j!== π(i))

Size(i-1,j-1)+1, (j==π(i))

Size(i,j)=

Max(size(i-1,j),size(i,j-1)), (j!== π(i))

递推公式证明:

对于从B(i-1,j)或B(i,j-1)到B(i,j)要么会多加一条导线,要么不加。

1. 当 j==π(i)时,(i,j)则是一条导线,且这条导线对B(i-1,j-1)的值没有影响,因为B(i-1,j-1)中的任意的一条导线的节点序号(无论是上端节点序号还是下端节点序号)都小于i,j,这由其空间位置决定的。

现在求B(i,j), 即求序号小于或等于i的上端接线柱和序号小于或等于j的下端接线柱中不相交导线的最大集合。显然应是B(i-1,j-1)U(i,j).

2 . 当j!= π(i)时。假如问题是从B(i,j-1)到B(i,j),那么下端新加入的接线柱j要么与上端的1至i-1个接线柱构成导线(与第i个接线柱构成导线的情况在上面已经讨论),要么不构成。

如果构成的话那么这种情况其实已经在B(i-1,j)中讨论了,这里不再考虑。那么B(i,j) 应是序号区间比他小一点的子问题的解。小一点是多少,肯定就是少一个接线柱了,也就是B(i-1,j)。

如果不构成的话,那么B(i,j)肯定就是序号区间比他小一点的子问题的解了。

对于B(i,j)可能由B(i-1,j)或B(i,j-1)过渡而来,所以B(i,j)取其中较大的一个。

 1 int main()  2 {  3      int  sub[n]={...};//按序存放下端对应接线柱序号  4      int matrix[n+1][n+1][2]={0};  5      for(int i=1;i<n+1;i++)  6      {  7          for(int j=1;j<n+1;j++)  8          {  9            if(j==sub[i]) 10           { 11             matrix[i][j][0]=matrix[i-1][j-1][0]+1; 12                matrix[i][j][1]=0; 13           }else 14           { 15              matrix[i][j][0]=matrix[i-1][j][0]>matrix[i][j-1][0]?matrix[i-1][j][0]:matrix[i][j-1][0]; 16                matrix[i][j][1]=matrix[i-1][j][0]>matrix[i][j-1][0]?1:2; 17             } 18       } 19     } 20     cout<<"the result is :"<<matrix[n][n][0]<<endl;//输出的是最大导线集中导线的数目,有保存中间决策结果 21  return 0; 22  }
正文到此结束
Loading...