电路布线
在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i)) 将上端接线柱i与下端接线柱π(i)相连,如下图。
)]
其中π(i),1≤ i ≤n,是{1,2,…,n}的一个排列。导线(i, π(i))称为该电路板上的第i条连线。对于任何1 ≤ i ≤ j ≤n,第i条连线和第j条连线相交的充要条件是π(i)> π(j).
在制作电路板时,要求将这n条线分布到若干个绝缘层上,在同一层上的连线不能相交。
换句话说,该问题要求确定导线集Nets = {i,π(i),1 ≤ i ≤ n}的最大不相交子集。
分析(最优子结构的构造):
设(i,π(i) )为 上方第i个接线柱接到下方第π(i)个接线柱。
N(i,j)是上方有i个接线柱,下方有j个界限组的情况。
MNS(i,j)是N(i,j)情况下的最优解。Size(i,j)=|MNS(i,j)|。
当i=1时,上方只有一个接线柱,当j>=π(i) 时,N(i,j)才有线,且为一根.
当i>1时:
1.j<π(i): (i,π(i)) 都不在N(i,j)的情况之内,故可以直接忽略该条导线,即忽略上方第i个接线柱.此时 N(i,j)=N(i-1,j),即Size(i,j)=Size(i-1,j)
2.j>=π(i):
(i,π(i)) 属于最优解 MNS(i,j),此时任意的(t, π(t))∈ MNS(i,j)有t < i且π(t)<
π(i),(t, π(t))与(i, π(i))相交(t<i,因为i是当前上方最后的一个接线柱,π(t)<
π(i),不这样的话,会相交)…
在这种情况下,MNS(i,j)-{(i, π(i))}是N(i-1, π(i)-1)的最大不相交子集
(因为,如果说MNS(i,j)-{(i, π(i))} 不是N(i-1, π(i)-1)的最大不相交子集,也就是N(i-1,
π(i)-1)的最大不相交子集另有其他集合假设为x吧,那么这个集合的导线与(i, π(i)) 肯定不会相交,那么N(i-1,
π(i)-1) 并上 x
其导线数必然大于MNS(i,j),这就与MNS(i,j)是N(i,j)的最优解的条件相矛盾.故MNS(i,j)-{(i,
π(i))}是N(i-1, π(i)-1)的最大不相交子集)
于是有Size(i,j)=Size(i-1,π(i)-1)+1
(i,π(i)) 不属于最优解 MNS(i,j)
,也就是说在(i,π(i))这条导线之前,必有至少两条导线在下方的接线柱是在π(i)的后面.这种情况下我们可以直接忽略(i,π(i))这条导线,就有N(i,j)=N(i-1,j),于是有Size(i,j)=Size(i-1,j)
经过上述的分析有如下递推公式:
这里想一下,为啥 A,B可以合并成max这个东西:
当(i,π(i)) 属于最优解
MNS(i,j)时:Size(i,j)=Size(i-1,π(i)-1)+1, Size(i-1,π(i)-1)+1一定大于等于Size(i-1,j),为啥? 因为(i,π(i))
属于最优解,那么在i之前必不可能会有超过两根导线在下方的接线柱大于π(i):
如果在i之前有1根导线在下方的接线柱大于π(i),
那么 size(i-1,j) == size(i,j) == Size(i-1,π(i)-1)+1.
如果如果在i之前没有导线在下方的接线柱大于π(i)
size(i-1,j) < size(i,j) ,即<Size(i-1,π(i)-1)+1
当(i,π(i)) 不属于最优解 MNS(i,j)时:Size(i,j)=Size(i-1,j) >=
Size(i-1,π(i)-1)+1为啥? 首先这种情况下Size(i,j) > Size(i-1,π(i)-1),
Size(i,j)=Size(i-1,j),既然这样Size(i-1,j)>=Size(i-1,π(i)-1)+1
来个例子:
π={8,7,4,2,5,1,9,3,10,6},即电路连线为(1,8)(2,7)(3,4)(4,2)(5,5)(6,1)(7,9)(8,3)(9,10)(10,6)
回溯:我们看当(i,π(i)) 属于最优解 MNS(i,j)时:Size(i,j)=Size(i-1,π(i)-1)+1,根据这个条件来进行回溯
从最右下角开始:
Size(10,10) 不等于Size(9,5)+1,故(10,6)不选,说明Size(i,j)=Size(i-1,j)
再来看Size(9,10) 等于 size(8,9)+1,说明选中了Size(i,j)=Size(i-1,π(i)-1)+1
再就看size(8,9) 这样依次类推
最终选出(9 ,10),(7,9),(5,5),(3,4).
第一次发博客,排版有点烂
如果觉得《电路布线-----问题详解》对你有帮助,请点赞、收藏,并留下你的观点哦!