第3章动态规划ppt课件

1、 动态规划算法与分治法类似，其根本思想也是将待求解问题分解成假设干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 动态规划算法与分治法类似，其根本思想也是将待求解问题分解成假设干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 但是经分解得到的子问题往往不是相互独立的。不同子问题的数目经常只需多项式量级。在用分治法求解时，有些子问题被反复计算了许多次。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)

2、T(n/4)T(n/4) 假设可以保管已处理的子问题的答案，而在需求时再找出已求得的答案，就可以防止大量反复计算，从而得到多项式时间算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n) 找出最优解的性质，并刻划其构造特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。1单个矩阵是完全加括号的；2矩阵连乘积 是完全加括号的，那么 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 AABC)(BCADCBA , ,

3、,1050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB16000, 10500, 36000, 87500, 34500u完全加括号的矩阵连乘积可递归地定义为：u设有四个矩阵 ，它们的维数分别是：u总共有五中完全加括号的方式n给定n个矩阵 ， 其中 与 是可乘的， 。调查这n个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。n假设一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，那么可以依此次序反复调用2个矩阵相乘的规范算法计算出矩阵连乘积,.,21nAAAiA

4、1iA1,.,2 , 1ninAAA.21 给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2 ,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需求的数乘次数最少。u穷举法：列举出一切能够的计算次序，并计算出每一种计穷举法：列举出一切能够的计算次序，并计算出每一种计算次序相应需求的数乘次数，从中找出一种数乘次数最少的算次序相应需求的数乘次数，从中找出一种数乘次数最少的计算次序。计算次序。 算法复杂度分析：算法复杂度分析：对于对于n个矩阵的连乘积，设其不同的计算次序为个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加

5、括号问题：由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于可以得到关于P(n)的递推式如下：的递推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnku穷举法穷举法u动态规划动态规划将矩阵连乘积 简记为Ai:j ，这里ij jiiAAA.1调查计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，那么其相应完全加括号方式为).)(.(211jkkkiiAAAAAA计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量 特征：计算Ai:j的最优次序所包含

6、的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子构造性质。问题的最优子构造性质是该问题可用动态规划算法求解的显著特征。n设计算Ai:j，1ijn，所需求的最少数乘次数mi,j，那么原问题的最优值为m1,n n当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,nn当ij时，n可以递归地定义mi,j为：jkipppjkmkimjim1, 1,这里 的维数为 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只需 种能够kij n对于1ijn不同的有序对(i,j)对应于不同的

7、子问题。因此，不同子问题的个数最多只需n由此可见，在递归计算时，许多子问题被反复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。n用动态规划算法解此问题，可根据其递归式以自底向上的方式进展计算。在计算过程中，保管已处理的子问题答案。每个子问题只计算一次，而在后面需求时只需简单查一下，从而防止大量的反复计算，最终得到多项式时间的算法)(22nnnpublic static void matrixChain(int p, int m, int s) int n=p.length-1; for (int i = 1; i = n; i+) mii = 0; for (int r = 2;

8、r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t 0) return mij; if (i = j) return 0; int u = lookupChain(i+1,j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = lookupChain(i,k) + lo

9、okupChain(k+1,j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; 假设给定序列X=x1,x2,xm，那么另一序列Z=z1,z2,zk，是X的子序列是指存在一个严厉递增下标序列i1,i2,ik使得对于一切j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公

10、共子序列。 设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，那么(1)假设xm=yn，那么zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。(2)假设xmyn且zkxm，那么Z是xm-1和Y的最长公共子序列。(3)假设xmyn且zkyn，那么Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子构造性质。 由最长公共子序列问题的最优子构造性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y

11、1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其他情况下，由最优子构造性质可建立递归关系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110由于在所思索的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 Algorithm lcsLength(x,y,b)1: mx.length-1;2: ny.length-1;3: ci0=0; c0i=0;4: for (int i = 1; i = m; i+)5: for (int j = 1; j =

12、cij-1) 10: cij=ci-1j;11: bij=2;12: else 13: cij=cij-1;14: bij=3;构造最长公共子序列构造最长公共子序列Algorithm lcs(int i,int j,char x,int b) if (i =0 | j=0) return; if (bij= 1) lcs(i-1,j-1,x,b); System.out.print(xi); else if (bij= 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); 在算法lcsLength和lcs中，可进一步将数组b省去。现实上，数组元素cij的值仅由ci-1

13、j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。假设只需求计算最长公共子序列的长度，那么算法的空间需求可大大减少。现实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。用多边形顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1表示具有n条边的凸多边形。假设vi与vj是多边形上不相邻的2个顶点，那么线段vivj称为多边形的一条弦。

14、弦将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。 一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图 (a)所示。凸多边形v0,v1,vn-1的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示。 矩阵连乘积中的每个矩阵Ai对应于凸

15、(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，ij，对应于矩阵连乘积Ai+1:j。凸多边形的最优三角剖分问题有最优子构造性质。现实上，假设凸(n+1)边形P=v0,v1,vn-1的最优三角剖分T包含三角形v0vkvn，1kn-1，那么T的权为3个部分权的和：三角形v0vkvn的权，子多边形v0,v1,vk和vk,vk+1,vn的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。由于假设有v0,v1,vk或vk,vk+1,vn的更小权的三角剖分将导致T不是最优三角剖分的矛盾。 定义tij，1ijn为凸子多边形vi-1,vi,vj的最优三角剖分所对应的权函数值，

16、即其最优值。为方便起见，设退化的多边形vi-1,vi具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t1n。tij的值可以利用最优子构造性质递归地计算。当j-i1时，凸子多边形至少有3个顶点。由最优子构造性质，tij的值应为tik的值加上tk+1j的值，再加上三角形vi-1vkvj的权值，其中ikj-1。由于在计算时还不知道k确实切位置，而k的一切能够位置只需j-i个，因此可以在这j-i个位置中选出使tij值到达最小的位置。由此，tij可递归地定义为：jijivvvwjktkitjitjkijki)(1min01多边形游戏是一个单人玩的游戏，开场时有一个由n个顶点构成的多边形。每个

17、顶点被赋予一个整数值，每条边被赋予一个运算符“+或“*。一切边依次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：(1)选择一条边E以及由E衔接着的2个顶点V1和V2；(2)用一个新的顶点取代边E以及由E衔接着的2个顶点V1和V2。将由顶点V1和V2的整数值经过边E上的运算得到的结果赋予新顶点。最后，一切边都被删除，游戏终了。游戏的得分就是所剩顶点上的整数值。问题:对于给定的多边形，计算最高得分。在所给多边形中，从顶点i(1in)开场，长度为j(链中有j个顶点)的顺时针链p(i，j) 可表示为vi，opi+1，vi+j-1。假设这条链的最后一次合并运算在opi+s处发

18、生(1sj-1)，那么可在opi+s处将链分割为2个子链p(i，s)和p(i+s，j-s)。设m1是对子链p(i，s)的恣意一种合并方式得到的值，而a和b分别是在一切能够的合并中得到的最小值和最大值。m2是p(i+s，j-s)的恣意一种合并方式得到的值，而c和d分别是在一切能够的合并中得到的最小值和最大值。依此定义有am1b，cm2d(1)当opi+s=+时，显然有a+cmb+d(2)当opi+s=*时，有minac，ad，bc，bdmmaxac，ad，bc，bd 换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。 图像的变位紧缩存储格式将所给的象素点序列p1,p2,pn,0pi25

19、5分割成m个延续段S1,S2,Sm。第i个象素段Si中(1im)，有li个象素,且该段中每个象素都只用bi位表示。设 那么第i个象素段Si为设 ，那么hibi8。因此需求用3位表示bi,假设限制1li255，那么需求用8位表示li。因此，第i个象素段所需的存储空间为li*bi+11位。按此格式存储象素序列p1,p2,pn，需求 位的存储空间。 图像紧缩问题要求确定象素序列p1,p2,pn的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超越256位。11ikklit1maxlog1kilitkitiphmibilmi11*1设li，bi，是p1,p2,pn的最优分段。显而易见，l1，

20、b1是p1,pl1的最优分段，且li，bi，是pl1+1,pn的最优分段。即图像紧缩问题满足最优子构造性质。设si，1in，是象素序列p1,pn的最优分段所需的存储位数。由最优子构造性质易知：其中11), 1max(b*min256,min1ikikkisisik1maxlog),bmax(kjkipji算法复杂度分析：算法复杂度分析：由于算法由于算法compress中对中对k的循环次数不超这的循环次数不超这256，故对每一个确定的故对每一个确定的i，可在时间，可在时间O(1)内完成的计算。因内完成的计算。因此整个算法所需的计算时间为此整个算法所需的计算时间为O(n)。 在一块电路板的上、下2

21、端分别有n个接线柱。根据电路设计，要求用导线(i,(i)将上端接线柱与下端接线柱相连，如下图。其中(i)是1,2,n的一个陈列。导线(i,(i)称为该电路板上的第i条连线。对于任何1i(j)。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽能够多的连线。换句话说，该问题要求确定导线集Nets=(i,(i),1in的最大不相交子集。 记 。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

22、.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)有 t1时) 1 (1) 1 (0), 1 (jjjSize)()(1) 1)(, 1(), 1(max), 1(),(ijijiiSizejiSizejiSizejiSizen个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加任务业i所需的时间分别为ai和bi

23、。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开场加工，到最后一个作业在机器M2上加工完成所需的时间最少。分析：分析：直观上，一个最优调度应使机器直观上，一个最优调度应使机器M1没有空闲时间，且机器没有空闲时间，且机器M2的空闲时间最少。在普通情况下，机器的空闲时间最少。在普通情况下，机器M2上会有机器空上会有机器空闲和作业积压闲和作业积压2种情况。种情况。设全部作业的集合为设全部作业的集合为N=1，2，n。SN是是N的作业的作业子集。在普通情况下，机器子集。在普通情况下，机器M1开场加工开场加工S中作业时，机器中作业时，机器M2还在加工其他作业，要等时间还在

24、加工其他作业，要等时间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的定义知的定义知TT(S,b(1)。假设。假设TT(S,b(1)，设，设是作业集是作业集S在机器在机器M2的等待时间为的等待时间为b(1)情况下的一个最优调度。那

25、么情况下的一个最优调度。那么(1)， (2)， (n)是是N的一个调度，且该调度所需的时间为的一个调度，且该调度所需的时间为a(1)+T(S,b(1)a(1)+T。这与。这与是是N的最优调的最优调度矛盾。故度矛盾。故TT(S,b(1)。从而。从而T=T(S,b(1)。这。这就证明了流水作业调度问题具有最优子构造的性质。就证明了流水作业调度问题具有最优子构造的性质。由流水作业调度问题的最优子构造性质可知，),(min)0 ,(1iinibiNTaNT)0 ,max,(min),(iiiSiatbiSTatST对递归式的深化分析阐明，算法可进一步得到简化。设是作业集S在机器M2的等待时间为t时的任

26、一最优调度。假设(1)=i, (2)=j。那么由动态规划递归式可得:T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其中，,max0 ,max,0 ,maxmax0 ,0 ,maxmaxiijiijijijijijijijijjiijijabaataabbbaatabbbaatabbaatbbt假设作业i和j满足minbi,ajminbj,ai，那么称作业i和j满足Johnson不等式。交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为T(S,t)=ai+aj+T(S-i,j,tji)其中，当作业i和j满足Johnson不等

27、式时，有由此可见当作业i和作业j不满足Johnson不等式时，交换它们的加工顺序后，不添加加工时间。对于流水作业调度问题，必存在最优调度 ，使得作业(i)和(i+1)满足Johnson不等式。进一步还可以证明，调度满足Johnson法那么当且仅当对恣意i2n时，算法需求时，算法需求(n2n)计算计算时间。时间。 由m(i,j)的递归式容易证明，在普通情况下，对每一个确定的i(1in)，函数m(i,j)是关于变量j的阶梯状单调不减函数。腾跃点是这一类函数的描画特征。在普通情况下，函数m(i,j)由其全部腾跃点独一确定。如下图。对每一个确定的i(1in)，用一个表pi存储函数m(i，j)的全部腾跃

28、点。表pi可依计算m(i，j)的递归式递归地由表pi+1计算，初始时pn+1=(0，0)。 n=3，c=6，w=4，3，2，v=5，2，1。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0, 0)(2, 1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)函数m(i,j)是由函数m

29、(i+1,j)与函数m(i+1,j-wi)+vi作max运算得到的。因此，函数m(i,j)的全部腾跃点包含于函数m(i+1，j)的腾跃点集pi+1与函数m(i+1，j-wi)+vi的腾跃点集qi+1的并集中。易知，(s,t)qi+1当且仅当wisc且(s-wi,t-vi)pi+1。因此，容易由pi+1确定腾跃点集qi+1如下qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1 另一方面，设(a，b)和(c，d)是pi+1qi+1中的2个腾跃点，那么当ca且db时，(c，d)受控于(a，b)，从而(c，d)不是pi中的腾跃点。除受控腾跃点外，pi+1qi

30、+1中的其他腾跃点均为pi中的腾跃点。由此可见，在递归地由表pi+1计算表pi时，可先由pi+1计算出qi+1，然后合并表pi+1和表qi+1，并去除其中的受控腾跃点得到表pi。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)。p5=(0,0),(4,6)。q5=p5(w4,v4)=(5,4),(9,10)。从腾跃点集p5与q5的并集p5q5=(0,0),(4,6),(5,4),(9,10)中看到腾跃点(5,4)受控于腾跃点(4,6)。将受控腾跃点(5,4)去除后，得到p4=(0,0

31、),(4,6),(9,10)q4=p4(6，5)=(6，5)，(10，11)p3=(0，0)，(4，6)，(9，10)，(10，11)q3=p3(2，3)=(2，3)，(6，9)p2=(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)q2=p2(2，6)=(2，6)，(4，9)，(6，12)，(8，15)p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15)p1的最后的那个腾跃点(8,15)给出所求的最优值为m(1,c)=15。上述算法的主要计算量在于计算腾跃点集pi(1in)。由于qi+1=pi+1(wi，vi)，故计算qi+1需求O(|pi+1|)计算时间。合并pi+1和qi+1并去除受控腾跃点