算法设计与分析电子教案 第3章 动态规划.ppt

电路布线 在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))将上端接线柱与下端接线柱相连，如图所示。其中π(i)是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第i条连线。对于任何1≤ij≤n，第i条连线和第j条连线相交的充分且必要的条件是π(i)π(j)。 电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。 * 记 。N(i,j)的最大不相交子集为MNS(i,j)。Size(i,j)=|MNS(i,j)|。 (1)当i=1时， (2)当i1时， 2.1 jπ(i)。此时， 。故在这种情况下，N(i,j)=N(i-1,j)，从而Size(i,j)=Size(i-1,j)。 2.2 j≥π(i)，(i,π(i))∈MNS(i,j) 。 则对任意(t,π(t)) ∈MNS(i,j)有ti且π(t)π(i)。在这种情况下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。 2.3 若 ，则对任意(t,π(t)) ∈MNS(i,j)有 ti。从而 。因此，Size(i,j)≤Size(i-1,j)。 另一方面 ，故又有Size(i,j)≥Size(i-1,j)， 从而Size(i,j)=Size(i-1,j)。 电路布线 (1)当i=1时 (2)当i1时 * 流水作业调度 n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。 流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。 分析： 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 设全部作业的集合为N={1，2，…，n}。S?N是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 * 流水作业调度 设?是所给n个流水作业的一个最优调度，它所需的加工时间为 a?(1)+T’。其中T’是在机器M2的等待时间为b?(1)时，安排作业?(2)，…，?(n)所需的时间。 记S=N-{?(1)}，则有T’=T(S,b?(1))。 证明：事实上，由T的定义知T’?T(S,b?(1))。若T’T(S,b?(1))，设?’是作业集S在机器M2的等待时间为b?(1)情况下的一个最优调度。则?(1)， ?’(2)，…， ?’(n)是N的一个调度，且该调度所需的时间为a?(1)+T(S,b?(1))a?(1)+T’。这与?是N的最优调度矛盾。故T’?T(S,b?(1))。从而T’=T(S,b?(1))。这就证明了流水作业调度问题具有最优子结构的性质。 由流水作业调度问题的最优子结构性质可知， * Johnson不等式 对递归式的深入分析表明，算法可进一步得到简化。 设?是作业集S在机器M2的等待时间为t时的任一最优调度。若?(1)=i, ?(2)=j。则由动态规划递归式可得: T(S,t)=ai+T(S-{i},bi+max{t-ai,0})=ai+aj+T(S-{i,j},tij) 其中， 如果作业i和j满足min{bi,aj}≥min{bj,ai}，则称作业i和j满足Johnson不等式。 * 流水作业调度的Johnson法则 交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为T’(S,t)=ai+aj+T(S-{i,j},tji) 其中， 当作业i和j满足Johnson不等式时，有 由此可见当作业i和作业j不满足Johnson不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度? ，使得作业?(i)和?(i+1)满足Johnson不等式。进一步还可以证明，调度满足Johnson法则当且仅当对任意ij有 由此可知，所有满足Johnson法则