第3章 动态规划_3.ppt

1、,例：6, 5, 7,5, 245, 180, 28,28,19, 22, 25,20,2-00000010 197-11000101,3,8,5,4*3+2*8+6*5=58,12*8=96位,4,2,6,3.7 图像压缩,6, 5, 7,5, 245, 180, 28,28,19, 22, 25,20,3,8,5,4*3+2*8+6*5,+3*3,+3*8,=91,要求找到一个最优分段，使存储空间最少。,例1：,定长：,001010 001001 001100 111000 110010 100011,少了5,6,7,3,6,4,8,图像压缩-最优子结构性质,设,是,的一个最优分段。,是,

2、的一个最优分段。,是,的一个最优分段。,图像压缩-递归计算最优值,00000010 00001111 10000010,图像压缩-练习,求像素序列4，6，5，7，129，138，1的最优分段。,解：,图像压缩-构造最优解,4，6，5，7,129，138，1,图像压缩-作业,求像素序列9,11,10,12,15,127,178,220,0的最优分段。,1,4,1,3,3,2,4,2,3.8 电路布线,5,电路布线问题：就是要确定将哪些连线安排在 第一层上,使得该层上有尽可能多的连线且不相交。,电路布线,算法思路: 化为多步决策,自底向上,先求出 只有一条连线的最大不相交子集,再求有2条 连线的最

3、大不相交子集.,电路布线,电路布线,1.最优子结构性质,1,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,Size,Size11=0,Size12=0,Size13=0,Size14=0,Size15=0,Size16=0,Size17=0,Size18=1,Size19=1,Size110=1,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,Size21,Size11,=,Size22 =Size12,Size23 =Size13,Size24 =Size14,Size25 =Size15,Size26 =Size16

4、,Size27,Size17,Size27=Size17+1=1,Size28,Size18,=,1),2),3),当i=1时, nets(1, j)=(1, (1),MNS(1, j) =,(1,(1) ，j (1), ， j (1),当i1时 1)若j(i), (i, (i) N(i, j) , 此时N(i, j)=N(i-1, j) 则 MNS(i, j)=MNS(i-1, j), Size(i, j)=Size(i-1, j); 2)若j(i), (i,(i)可在也可不在MNS(i, j)中: 若(i,(i) MNS(i, j), 对(t, (t)MNS(i, j) 有ti, (t)

5、(i) 此时MNS(i, j)=MNS(i-1, (i)-1)(i,(i), Size(i, j)= Size(i-1,(i)-1)+1; 若(i, (i) MNS(i, j), 则对任意(t, (t)MNS(i, j), 有ti. 此时MNS(i, j)=MNS(i-1, j), Size(i, j)=Size(i-1, j)。,电路布线,递归计算最优值,电路布线问题的最优值为Size(n,n)，满足,1),2),电路布线-示例,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,电路布线-,构造最优解,10,9,8,7,6,5,4,3,2,1,1,2,3,4

6、,5,6,7,8,9,10,j,i,3.9 流水作业调度(同顺序),设有m种加工用的机器： M1, M2, , Mm 所谓同顺序流水作业是指它的加工顺序是相同的，不妨为M1 M2 Mm 即先通过M1加工，然后依次为M2 ，等等。 现有n个作业其加工顺序一样，设为 J1, J2, , Jn 已知矩阵 T=(tij)m*n 其中 tij 作业Jj在机器Mi上的加工时间。 求所用时间最短的作业加工顺序及时间。,下面仅就m=2的情形讨论。 S0=J1, J2, , Jn, N=1, 2, , n 设M1、M2加工作业i分别需要时间ai和bi 若n个作业的加工顺序不同，从第一个作业在机器Ml上加工开始，

7、到最后一个作业在机器M2上加工完毕为止，所需的时间也不同。从直观上知道最佳的安排是使得机器M2的空闲时间达到最少，而对机器M 1不存在空闲问题。当然M2也存在作业等机器的状况，即M1加工完毕，而M2还在加工前面一个任务。,M1,M2,h1,h2,t,其中：,是固定值。,因此：要缩短完工时间，关键是要缩短t. 子集合S中作业调度受到开始前的M2的等待时间的限制。,设S是作业的集合若机器M1开始加工S中的任务时，M2机器还在加工其它任务，t时刻后才可利用，在这样的条件下，加工S中任务所需的最短时间定义为T(S, t)，则流水作业调度问题的最优T(N,0)。 （1）最优子结构性质 设 是n个流水作业

8、的一个最优调度，则 T=a(1) + T 其中可以证明T = T( S(1), b(1) ),(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时,流水作业调度的 Johnson法则,设 是作业集S在M2上等待时间为t的最优调度，安排

9、在前两个的作业是i和j，那么 T(S,t)=ai +T(Si, bi +maxtai,0) = ai + aj + T(S-i,j, tij ) 其中， tij =bj+maxbi+maxtai,0aj , 0 = bj+ biaj + maxmaxt- ai,0 ,0, aj bi = bj+ bi - aj + maxtai, 0, aj bi = bj+ biajai + maxt, ai + ajbi , ai,如果调度中i和j交换位置，则得出 T(S,t)=ai + aj + T(Si,j, tji) 其中tji=bj+biajai+maxt,ai+ajbj,aj 而前面得出：T(S

10、,t)= ai + aj + T(Si,j, tji ) tij = bj+ biajai + maxt, ai + ajbi , ai 如果T(S,t)= T(S,t) /i排在前j在后是最优调度 则 maxt,ai+ajbi,ai maxt, ai + ajbj , aj 为了使上述式子对所有t的取值都成立，则必须 maxai+ajbi, ai maxai + ajbj, aj 即ai+aj+max(-bi, -aj) ai+aj+max -bj , -ai 或 min(bi,aj) minbj, ai,第一台加工时间短的任务排在前 第二台加工时间长的任务应排在前,（1）如果作业i和j满足

11、不等式 min(aj, bi)=min(ai , bj) 则称作业i和j满足Johnson不等式。 （2）若不满足Johnson不等式，则交换i和j的加工 顺序，从而满足Johnson不等式。 流水线作业最优调度中前一个作业和后一个作业一定满足Johnson不等式,结论：若Johnson不等式成立，则作业i应安排在作业j之前加工。即：在M1上加工时间短的任务应优先，而在机器M2上加工时间短的任务应排在后面。 即可以断定存在一种最优调度，在这调度中，对于每一临近的作业对(i,j)，有： min(bi,aj)=min(bj,ai) 也即ai最小i就应排在最前面，bj最小应排在最后面 mina1,a

12、2,an,b1,b2,bn=ai,那么作业i就应该是最优调度中的第一个作业 mina1,a2,an,b1,b2,bn=bj, 那么作业j就应该是最优调度中的最后一个作业。,流水作业调度示例：,例：作业： J1 J2 J3 J4 J5 J6 工序：打字 30 120 50 20 90 110 排版 80 100 90 60 30 10 求最佳任务安排次序。 解：(1)第二道工序的10最小J6排在最后 (2)第一道工序的20次之J4排在第一 (3)以此类推，J1 、J5排在第二、倒数第二 最终次序：J4 J1 J3 J2 J5 J6,J4 J1 J3 J2 J5 J6 M1 20 30 50 12

13、0 90 110 M2 60 80 90 100 30 10 20/20 30/50 50/100 120/220 90/310 110/420 80/80 80/160 90/250 100/350 30/380 10/430,M1不停地工作，M2等M1完成作业J4后开始排版，中途不存在M2空闲问题，但等M2完成J5后，要一直等420-380=40分钟，M1完成J6，M2再对J6排版10分钟，所以最终完成时间为： 420+10=430 分钟。,流水作业调度-练习,5个作业J1,J2,J3,J4,J5在两台机器上的加工时间分别为5,1,8,5,3,4和7,2,2,4,7,4，求最佳安排次序。,

14、0-1背包问题,目标函数,3.10 0-1背包问题,0-1背包问题,0-1背包问题是一个特殊的整数规划问题。,0-1背包问题-最优子结构,反证法,0-1背包问题-递归关系,设所给0-1背包问题的子问题,的最优值为m(i,j),放入,装不下物品 i,将物品i装入背包是否有利？,0-1背包问题-示例,要求：1)写出最优解的递归定义 2)背包所装物品的最大价值是多少？ 3)最优解是什么？,解：,1,2,1,0,3,4,5,2,3,4,5,6,7,8,9,10,0,0,0,0,0,0,0,0,6,6,6,6,6,6,6,0,0,0,6,6,6,6,6,10,10,0,0,0,6,6,6,6,10,11

15、,6,0,3,3,6,6,9,9,10,11,9,15,0-1背包问题-构造最优解,Yes,No,10,1,2,1,0,3,4,5,2,3,4,5,6,7,8,9,10,0,0,0,0,0,0,0,0,6,6,6,6,6,6,6,0,0,0,6,6,6,6,6,10,10,0,0,0,6,6,6,6,11,10,6,0,3,3,6,6,9,9,10,11,9,15,(1,1,0,0,1),跳跃点(0,0)和(4,6),pi 递归?,背包的装载量与价值,10,1,2,1,0,3,4,5,2,3,4,5,6,7,8,9,10,0,0,0,0,0,0,0,0,6,6,6,6,6,6,6,0,0,0,6,6,6,6,6,10,10,0,0,0,6,6,6,6,11,10,6,0,3,3,6,6,9,9,10,11,9,15,0-1背包问题-示例,例1,解：