电路布线
在一块电路板的上、下两端分别有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).
第一次发博客，排版有点烂
