算法设计-3.3_36.ppt

1、计算机算法,设计与分析 第三章 动 态 规 划,2,3.9 同顺序流水作业调度,设有m种加工用的机器： M1, M2, , Mm 所谓同顺序流水作业是指它的加工顺序是相同的，不妨为M1 M2 Mm 即先通过M1加工，然后依次为M2 ，等等。 现有n项任务其加工顺序一样，设为 J1, J2, , Jn 已知矩阵 T=(tij)mxn 其中 tij 作业Jj在机器Mi上的加工时间。 求所用时间最短的作业加工顺序及时间。,3,下面仅就m=2的情形讨论。 S0=J1, J2, , Jn, N=1, 2, , n 若n个任务的加工顺序不同，从第一个任务在机器M l上加工开始，到最后一个任务在机器M2上加

2、工完毕为止，所需的时间也不同。从直观上知道最佳的安排是使得机器M2的空闲时间达到最少，而对机器M 1不存在空闲问题。当然M2也存在任务等机器的状况，即M 1加工完毕，而M2还在加工前面一个任务。,4,设M1、M2加工作业i分别需要时间ai和bi 设S是任务的集合若机器M1开始加工S中的任务时，M2机器还在加工其它任务，t时刻后才可利用，在这样的条件下，加工S中任务所需的最短时间定义为T(S, t)，则流水作业调度问题的最优T(N,0)。 （1）最优子结构性质 设 是n个流水作业的一个最优调度，则 T=a(1)+T 其中T =T( S-(1), b(1) ),a(1),b(1),M1,M2,=t

3、,5,(2)递归计算最优值 T(N,0)=minai +T(N-i, bi) 1=i=n 推广： T(S,t)=minai +T(S-i, bi +maxt- ai,0) bi +maxt- ai,0的含义是：因为作业i要在maxt, ai时间之后才能开工，所以作业i在M1上完成后，还需要bi +maxt- ai,0时间才能在M2 上完成。,M1,M2,M1,M2,ai,t,bi,ai,t,bi,t= ai时,t ai时,T=a(1)+T ,6,流水作业调度的 Johnson法则 设 是作业集S在M2上等待时间为t的最优调度，安排在前两个的作业是i和j，那么 T(S,t)=ai +T(S-i,

4、 bi +maxt- ai,0) = ai + aj + T(S-i,j, tij ) 其中， tij =bj+maxbi+maxt- ai,0- aj ,0 = bj+ bi - aj + maxmaxt- ai,0 ,0, aj - bi = bj+ bi - aj + maxt- ai, 0, aj - bi = bj+ bi - aj - ai + maxt, ai + aj - bi , ai,7,如果作业i和j满足不等式 min(ai , bj)=max(-aj , -bi),8,ai + aj + max(-ai , -bj)= ai + aj + max(-aj , -bi)

5、max(ai + aj -bj , aj )= max(ai + aj -bi , ai ) T (S,t)= bj+ bi - aj - ai + maxt, ai + aj - bj , aj T(S,t)= bj+ bi - aj - ai + maxt, ai + aj - bi , ai T (S,t)= T(S,t) 结论：若Johnson不等式成立，则作业i应安排在作业j之前加工。即：在M1上加工时间短的任务应优先，而在机器M2上加工时间短的任务应排在后面。,9,例： 任务： J1 J2 J3 J4 J5 J6 工序：打字 30 120 50 20 90 110 排版 80 10

6、0 90 60 30 10 求最佳任务安排次序。 解： （1）第二道工序的10最小J6排在最后 （2）第一道工序的20此之J4排在第一 （3）以此类推，J1 、J5排在第二、倒数第二 最终次序：J4 J1 J3 J2 J5 J6,10,J4 J1 J3 J2 J5 J6 M1 20 30 50 120 90 110 M2 60 80 90 100 30 10 20/20 30/50 50/100 120/220 90/310 110/420 60/80 80/160 90/250 100/350 30/380 10/430 M1不停地工作，M2等M1完成作业J4后开始排版，中途不存在M2空闲问

7、题，但等M2完成J5后，要一直等420-380=40分钟，M1完成J6，M2再对J6排版10分钟，所以最终完成时间为： 420+10=430 分钟,11,Int Flowshop(int n,int a,int b,int c) Jobtype *d=new Jobtypen; for(int i=0;ibi ? bi:ai; di.job=ai=bi; di.index=I; sort(d,n); ?,class Jobtype public: int operator=(Jobtype a)const return(key=a.key); int key; int index; bool

8、job; ;,12,备忘录方法,动态规划求解问题的一个基本要素：子问题的重叠性质。利用此性质，在递推工程中，对每个问题只解一次，并保存在表格中，当再次需要求解此子问题时，只要简单地用常数时间查看结果。这就是动态规划优于直接递归计算的原因。例：矩阵连乘问题,13,备忘录方法：是动态规划法的一种变形，它也用表格保存子问题答案，以备查看，而不必重复计算，但属于自顶向下的递归方式。 备忘录方法为每个子问题建立记录项，开始存放一个特殊的初始值，表示该问题尚未求解。处理每个子问题时，先查看对应记录项，如果是初始值，则表明遇到，求解该问题并更新对应记录项。否则，说明该问题已求解过，只需要从记录项中取出该问题

9、解答即可。,14,例：用备忘录方法求解矩阵连乘最优次序问题（参见P51)。 时间：O(n3) 空间：O(n2) 什么时候用动态规划方法？ 当所有子问题都至少要解一次时，用动态规划算法。此时，动态规划方法没有任何多余计算。 什么时候用备忘录方法？ 当子问题空间的部分子问题不必求解时，用备忘录方法较为有利。,15,3.10 0/1背包问题,背包问题：已知有n种物品和一个可容纳C重量的背包，每种物品i的重量为Wi。假定将物品i的一部分Xi放入背包就会得到Pi的效益，这里，0Xi1，Pi0。那么，采用怎样的装包方法才会使装入背包物品的总效益最大呢？其形式化描述为： 极大化 目标函数 约束条件 C 其中

10、， 0 x1, p0, w0, 1in,16,满足约束条件的任一集合（x1,xn）是一个可行解（即能装下），使目标函数取最大值的可行解是最优解。 背包问题的另一个变形就是0/1背包问题。即限定Xi的取值为0或1，其余条件不变。 普通的背包问题采用贪心法来解决。 0/1背包问题可采用动态规划法、回溯法、分支限解法来解决。 如何用动态规划法求解0/1背包问题？,17,1）最优子结构性质 （反证法） 2）递归关系 m(i,j)的定义：背包容量为j，可选物品为i, i+1, , n时的背包问题最优值。 与以前的递归定义方向不同： m(i+1,j) m(i,j) m(n,j)=0 j= Wn (背包能装

11、下物品n) m(i,j)= m(i+1,j) j=Wi (将物品i装入背包是否有利？）,18,算法Knapsack描述 说明：由mn,c最优值m1,c ； jmax：设定的当前背包容量； 程序按mi,j定义的四种情形处理： （1）0Wn mn,j=Vi (3) 0Wi mi,j=maxmi+1,j, m(i+1,j-Wi) +Vi,19,Template Vid Knapsack(Type v,int w,int c,int n,Type *m) int jMax=min(wn-1,c); for(int j=0;j1;i-) jMax=min(wi-1,c); for(int j=0;j=w

12、1 m1c= maxm1c) , m2c-w1) +v1; ,20,Template Vid Taceback(Type *m ,int w,int c,int n,int x) /x数组用来存放是否第i个元素被装载进来 for(int i=0;i=n;i+) if(mic=mi+1c) xi=0; eles xi=1; c=c-wi; xn=(mnc) ? 1:0; ,21,算法Traceback 用于构造最优解 若m1,c=m2,C，说明物品1未装入背包，x1=0，否则x1=1； 若x1=0，由m2, C继续构造最优解； 若x1=1，由m2, C-W1继续构造最优解。 以此类推，最后得最优

13、解(x1,x2,xn) 时间复杂性 算法Knapsack ： 由第35个for循环语句可知 O(nC) 算法Traceback: O(n),22,例：n=5,c=10, w=2,2,6,5,4,V=6,3,5,4,6,23,上述算法的缺陷： 1）要求Wi为整数 2）当c2n时，时间空间消耗太大。 注意：mi,j是关于j的阶梯状单调不减函数。 例：m5,j=0 0=4 跳跃点（0，0）、（4，6）能确定m5,j Mi,j由其全部跳跃点唯一确定。,(x, m(i,x)=(4,m(5,4),x=4,c,j,M(i,j),6,24,对每个确定的i(1=i=n), 用Pi存放mi,j的全部跳跃点，每个跳

14、跃点由一对数据(j, m(i,j) 组成，按升序排列。它反映了当前背包的装载量与价值。,(x, m(i,x),x,c,j,M(i,j),25,如何计算Pi ？ Pn+1=(0,0) 因为 mi,j=maxmi+1,j, m(i+1,j-Wi) +Vi 所以，mi,j的全部跳跃点由mi+1,j的跳跃点集Pi+1与函数m(i+1,j-Wi) +Vi的跳跃点集Qi+1的并集组成。 Qi+1= Pi+1 (wi,vi) =(j+wi, mi,j+vi) 其中，(j, m(i,j) Pi+1，且j+wi=C,26,Pi = Pi+1 U Qi+1 受控跳跃点 设(a,b)和(c,d)属于上述并集，而且

15、c=a, d=a)的背包的价值为d(d=b)，那么(c,d)对应的装载方式不如(a, b)对应的装载方式，自然应将(c,d)排除。 举例：n=5,c=10, w=2,2,6,5,4,V=6,3,5,4,6 P6=(0,0), (w5,v5)=(4,6) Q6= P6 (w5,v5)=(4,6),27,P5= P6 U Q6 =(0,0), (4,6) (w4,v4)=(5,4) Q5=P5 (w4,v4)=(5,4), (9,10) P5U Q5=(0,0), (4,6), (5,4), (9,10) P4= (0,0), (4,6), (9,10) Q4= P4 (w3,v3)=(0,0),

16、 (4,6), (9,10) (6,5)=(6,5),(10,11) P4 U Q4=(0,0), (4,6), (9,10), (6,5),(10,11) P3= (0,0), (4,6), (9,10),(10,11),28,Q3= P3 (w2,v2)=(0,0), (4,6), (9,10) ,(10,11) (2,3)=(2,3),(6,9) P3 U Q3=(0,0), (4,6), (9,10),(10,11),(2,3),(6,9) P2= (0,0), (2,3),(4,6), (6,9), (9,10),(10,11) Q2= P2 (w1,v1)= P2 (2,6) =(2,6),(4,9),(6,12),(8,15) P2 U Q2=(0,0), (2,3),(4,6), (6,9), (9,10),(10,11), (2,6),(4,9),(6,12),(8,15) P1=(0,0),(2,6),(4,9),(6,12),(8,15) M1,c=15,29,时间复杂性