《动态规划》ppt课件

1、2学习要点:理解动态规划算法的概念。掌握动态规划算法的根本要素1 最优子构造性质2 重叠子问题性质掌握设计动态规划算法的步骤。1 找出最优解的性质，并刻划其构造特征。2 递归地定义最优值。3 以自底向上的方式计算出最优值。4 根据计算最优值时得到的信息，构造最优解。23通过应用范例学习动态规划算法设计策略1 矩阵连乘问题；2 最长公共子序列；3 最大子段和;4 凸多边形最优三角剖分；5 多边形游戏； 6 图像压缩；7 电路布线；8 流水作业调度；9 背包问题；10 最优二叉搜索树。34找出最优解的性质，并刻划其构造特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息

2、，构造最优解。13是动态规划算法最根本的步骤,假设需要最优解, 那么必须执行步骤445完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；矩阵连乘积A是完全加括号的，那么A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=BC 设有四个矩阵A, B, C, D，总共有五种完全加括号的方式:ABCDABCDABCDABCDABCD56设有四个矩阵A, B, C, D，它们的维数分别是：A=5010, B=1040, C=4030, D=305矩阵A和B可乘的条件是: 矩阵A的列数等于矩阵B的行数.设A是pq的矩阵, B是qr的矩阵, 那么乘积是pr的矩阵;计算量是pqr.上

3、述5种完全加括号方式的计算工作量为:ABCD, ABCD, ABCD, ABCD, ABCD16000, 10500, 36000, 87500, 34500BC: 104030 = 12000, BCD: 10305 = 1500,ABCD: 50105 = 250067例如78例如89定义：给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2,n-1。考察这n个矩阵的连乘积A1A2An。 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。假设一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，那么可以依此次

4、序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积910给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少？穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：算法复杂度分析：对于对于n个矩阵的连乘积，设其不同的计算次序为个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于可

5、以得到关于P(n)的递推式如下：的递推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk1011穷举法动态规划将矩阵连乘积AiAi+1Aj 简记为Ai:j, 这里ij;考察计算Ai:n的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1kn，那么其相应完全加括号方式为A1A2AkAk+1Ak+2An计算量：A1:k的计算量加上Ak+1:n的计算量，再加上A1:k和Ak+1:n相乘的计算量1112特征：计算A1:n的最优次序所包含的计算矩阵子链 A1:k和Ak+1:n的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最

6、优子构造性质。问题的最优子构造性质是该问题可用动态规划算法求解的显著特征。1213设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，那么原问题的最优值为m1,n 当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n当ij 时，这里这里Ai的维数是的维数是Pi-1Pi可以递归地定义mi,j为：jkipppjkmkimjim1, 1,jipppjkmkimjijimjki, 1,min0,1jki 的位置只有的位置只有 种种可能可能kij 1314mij给出了最优值，最优断开位置为k：假设将对应于mi, j的断开位置k记为si, j, 在计算出最优值mi, j后,可递归的由si,

7、j构造出相应的最优解.jkipppjkmkimjim1, 1,1415对于1ijn不同的有序对i,j对应于不同的子问题。因此，不同子问题的个数最多只有在递归计算时，许多子问题被重复计算屡次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可根据其递归式以自底向上的方式进展计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，在后面需要时只要简单查一下，从而防止大量的重复计算，最终得到多项式时间的算法。)(22nnn1516void MatrixChainint *p，int n，int *m，int *s for int i = 1; i = n; i+ m

8、ii = 0; for int r = 2; r = n; r+/变量i的跨度 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 mij mij = t; sij = k; r1617A1A2A3A4A5A630 3535 1515 55 1010 2020 25113752010350437555427125205351000262554 32130002015

9、35250005322min52541531521pppmmpppmmpppmmmr1718根据其递归式以自底向上的方式进展计算。在计算过程中 , 保存已解决的子问题答案。每个子问题只计算一次 , 而在后面需要时只要简单查一下 ,从而防止大量的重复计算, 最终得到多项式时间的算法。r1819void MatrixChainint *p，int n，int *m，int *s for int i = 1; i = n; i+ mii = 0; for int r = 2; r = n; r+ for int i = 1; i = n - r+1; i+ int j=i+r-1; mij = mi

10、+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 mij mij = t; sij = k; 算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O1。3重循环的总次数为On3。因此算法的计算时间上界为On3。算法所占用的空间显然为On2。1920sij已经存储了构造最优解所需要的足够的信息。每个部分的最优加括号方式可以根据数组s的相应元素得出。照此递推下去，最终可以确定A1:n的最优完全加括号方式，即构造出问

11、题的一个最优解。 void TraceBackint i,int j ifi=j return; TraceBacki,sij; TraceBacksij+1,j; printfMultiply A%d,%d and A%d,%dn,i,sij,sij+1,j; 2021一、最优子构造矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子构造性质。在分析问题的最优子构造性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 2122一、最优子构造利用问题的最优子构造性质，以自底向上

12、的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子构造是问题能用动态规划算法求解的前提。同一个问题可以有多种方式刻划它的最优子构造，有些表示方法的求解速度更快空间占用小，问题的维度低2223jipppjkmkimjijimjki, 1,min0,1jki二、重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算屡次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而

13、获得较高的解题效率。 r2324矩阵连乘积的递归式计算:int RecurChainint i，int j if i = j return 0; int u = RecurChaini，i + RecurChaini+1，j + pi-1*pi*pj; sij = i; for int k = i+1; k j; k+ int t = RecurChaini，k + RecurChaink+1，j + pi-1*pk*pj; if t 0 return mij; if i = j return 0; int u = LookupChaini，i + LookupChaini+1，j + pi-

14、1*pi*pj; sij = i; for int k = i+1; k j; k+ int t = LookupChaini，k + LookupChaink+1，j + pi-1*pk*pj; if t u u = t; sij = k; mij = u; return u;2526假设给定序列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既

15、是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。 2627设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，那么假设xm=yn，那么zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。假设xmyn且zkxm，那么Z是xm-1和Y的最长公共子序列。假设xmyn且zkyn，那么Z是X和yn-1的最长公共子序列。2个序列的最长公共子序列包含了这个序列的最长公共子序列包含了这2个序列的个序列的前缀的最长公共子序列前缀的最长公共子序列。最长公共子序列问题具

16、有最长公共子序列问题具有最优子构造性质最优子构造性质。 2728由最长公共子序列问题的最优子构造性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。 Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子构造性质可建立递归关系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 1102829由于在所考虑的子问题空间中，总共有mn个不同的子问题，用动态规划算法自底向上地计算最优值能进步算法的效率。void LCSLengthint m，int

17、 n，char *x，char *y，int *c，int *b int i，j; for i = 1; i = m; i+ ci0 = 0; for i = 1; i = n; i+ c0i = 0; for i = 1; i = m; i+ for j = 1; j =cij-1 cij=ci-1j; bij=2; else cij=cij-1; bij=3; 01234.n000000 010203040 m 0ij2930void LCSLengthint m，int n，char *x，char *y，int *c，int *b int i，j; for i = 1; i = m;

18、i+ ci0 = 0; for i = 1; i = n; i+ c0i = 0; for i = 1; i = m; i+ for j = 1; j =cij-1 cij=ci-1j; bij=2; else cij=cij-1; bij=3; 0123456yiBDCABA0 xi00000001A00001112B01111223C01122224B01122335D01222336A01223347B0122344ij3031由数组b构造最长公共子序列void LCSint i，int j，char *x，int *b if i =0 | j=0 return; if bij= 1 L

19、CSi-1，j-1，x，b; coutxi; else if bij= 2 LCSi-1，j，x，b; else LCSi，j-1，x，b;0123456yiBDCABA0 xi00000001A00001112B01111223C01122224B01122335D01222336A01223347B0122344ij0123456yiBDCABA0 xi1A 2B 3C 4B 5D 6A 7B ij3132在算法lcsLength和lcs中，可进一步将数组b省去。数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组

20、b而仅借助于c本身在O1时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。假如只需要计算最长公共子序列的长度，那么算法的空间需求可大大减少。在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至Ominm,n。3233最大子段和问题描绘：给定由n个整数包含负整数组成的序列a1,a2,.,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。依此定义，所求的最优值为： 例如，当a1,a2, a3, a4, a5,a6= -2,11,-4,13,-5,-2 时，最大子

21、段和为： jikknjia1max, 0max201341142kka33341. 一个简单算法int MaxSumint n, int *a, int &besti, int &bestjint sum=0;fori=1;i=n;i+forj=i;j=n;j+int thissum=0;fork=i;ksumsum=thissum;besti=i;Bestj=j;return sum;算法有3重循环，复杂性为On3。34351. 一个简单算法一个简单算法：int MaxSumint n, int *a, int &besti, int &bestjint su

22、m=0;fori=1;i=n;i+forj=i;j=n;j+int thissum=0;fork=i;ksumsum=thissum;besti=i;Bestj=j;return sum;算法有3重循环，复杂性为On3。由于有：算法可作如下改进：int MaxSumint n, int *a, int &besti, int &bestjint sum=0;fori=1;i=n;i+int thissum=0;forj=i;jsumsum=thissum;besti=i;bestj=j;改进后的算法复杂性为On2 。1jikkjjikkaaa35362. 分治方法求解从问题的解

23、的构造可以看出，它合适于用分治策略求解：假如将所给的序列a1:n分为长度相等的两段a1:n/1和an/2+1:n，分别求出这两段的最大子段和，那么a1:n的最大子段和有三种情形：a1:n的最大子段和与a1:n/2的最大子段和一样；a1:n的最大子段和与an/2+1:n的最大子段和一样；A.a1:n的最大子段和为下面的形式。inkkninnikknijikkasasnjnniaC121222211maxmax12,21 ,.1nn/2ijs1s236372. 分治方法求解int MaxSubSumint a , int left, int right int sum=0; if left=rig

24、htsum=aleft0?aleft:0; elseint center=left+right/2; int leftsum=MaxSubSuma,left,center; int rightsum=MaxSubSuma,center+1,right; int s1=0;leftsum=0; for int i=center;i=left;i- leftsum+=ai; if leftsums1 s1=leftsum; int s2=0;rightsum=0; for int i=center+1;is2 s2=rightsum; sum=s1+s2; if sumleftsum sum=le

25、ftsum; if sum0时bj=bj-1+aj，否那么bj=aj。那么计算bj的动态规划递归式bj=maxbj-1+aj，aj，1jn。jnjjikkjinjjkknjijikkjijbaanjab111111maxmaxmaxmax1max为，则所求的最大子段和，若记123456ai-211-413-5-2b初值初值=0-2117201513sum0111120202038393. 动态规划方法求解据此，可设计出求最大子段和的动态规划算法如下：int MaxSumint n, int aint sum=0; /sum是bj1jn的最大值int b=0;for int i=1;i0 b+=

26、ai; else b=ai;if bsum sum=b;return sum;显然该算法的计算时间为On。123456ai-211-413-5-2b初值初值=0-2117201513sum0111120202039404. 算法的推广最大矩阵和问题，略最大m子段和问题，略4041n个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开场加工，到最后一个作业在机器M2上加工完成所需的时间最少。123456

27、A2571052B38411344142直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。设全部作业的集合为N=1，2，n。S N是N的作业子集。在一般情况下，机器M1开场加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为TS,t。流水作业调度问题的最优值为TN,0。4243设是所给n个流水作业的一个最优调度，它所需的加工时间为 a1 +T。其中T是在机器M2的等待时间为b1时，安排作业2， n所需的时间。记S=N-1，那么有T=TS, b1 。 1 2 3 n

28、Aa 1a 2a 3a nBb 1b 2b 3b n4344ABa 1b 1 1S=N-1T=TS, b1 T44450 ,maxiiatbt由流水作业调度问题的最优子构造性质可知，推广到一般情形下,有:),(min)0 ,(1iinibiNTaNT)0 ,max,(min),(iiiSiatbiSTatSTM1M24546推广到一般情形下,有:)0 ,max,(min),(iiiSiatbiSTatST4647对递归式的深化分析说明，算法可进一步得到简化。设是作业集S在机器M2的等待时间为t时的任一最优调度。假设1=i, 2=j。那么由动态规划递归式可得:TS,t=ai+TS-i,bi+ma

29、xt-ai,0=ai+aj+TS-i,j,tij,max0 ,max,0 ,maxmax0 ,0 ,maxmaxiijiijijijijijijijijjiijijabaataabbbaatabbbaatabbaatbbt4748对递归式的深化分析说明，算法可进一步得到简化。设是作业集S在机器M2的等待时间为t时的任一最优调度。假设1=i, 2=j。那么由动态规划递归式可得:TS,t=ai+TS-i,bi+maxt-ai,0=ai+aj+TS-i,j,tij,max0 ,max,0 ,maxmax0 ,0 ,maxmaxiijiijijijijijijijijjiijijabaataabbba

30、atabbbaatabbaatbbt4849对递归式的深化分析说明，算法可进一步得到简化。设是作业集S在机器M2的等待时间为t时的任一最优调度。假设1=i, 2=j。那么由动态规划递归式可得:TS,t=ai+TS-i,bi+maxt-ai,0=ai+aj+TS-i,j,tij假如作业i和j满足minbi,ajminbj,ai，那么称作业i和j满足JohnsonJohnson不等式不等式。4950交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为TS,t=ai+aj+TS-i,j,tji其中，当作业i和j满足Johnson不等式时，有,maxjjjiijijjiabaata

31、abbt,maxiijiijijijabaataabbt,max,max,max,max,max,max,max,maxjjjiiijijjjiiijiijjijijiijjiabaatabaatabaaabaaabaaabaaabab假如作业i和j满足minbi,ajminbj,ai，那么称作业i和j满足JohnsonJohnson不等式不等式。5051由此可见当作业i和作业j不满足Johnson不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度 ，使得作业i和i+1满足Johnson不等式。进一步还可以证明，调度满足Johnson法那么当且仅当对任意ij有

32、由此可知，所有满足Johnson法那么的调度均为最优调度。 ,maxjjjiijijjiabaataabbt,maxiijiijijijabaataabbt,max,maxjjjiiijiabaatabaat,min,min)()()()(ijjiabab5152假如作业i和j满足minbi,ajminbj,ai，那么称作业i和j满足Johnson不等式。假设作业i和作业j不满足Johnson不等式，那么交换它们的加工顺序后，满足Johnson不等式。对于流水作业调度问题，必存在最优调度 ，使得作业i和i+1满足Johnson不等式。进一步还可以证明，调度满足Johnson法那么当且仅当对任意

33、ij有:所有满足Johnson法那么的调度均为最优调度。 ,min,min)()()()(ijjiabab5253流水作业调度问题的Johnson算法1 令2 将N1中作业依ai的非减序排序； 将N2中作业依bi的非增序排序；3 N1中作业接N2中作业构成满足Johnson法那么的最优调度。;|,|21iiiibaiNbaiNN1中作业依中作业依ai的非减序排序的非减序排序N2中作业依中作业依bi的非增序排序的非增序排序123456A2571052B38411345354123456A2571052B3841134算法复杂度分析：算法复杂度分析：算法的主要计算时间花在对作业集的排序。算法的主要

34、计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为因此，在最坏情况下算法所需的计算时间为Onlogn。所需的空间为所需的空间为On。5455int FlowShopint n, int *a, int *b, int *c class Jobtype public: int operator= Jobtype a const /排序重载函数 return key=a.key; int key; int index; bool job; ; Jobtype *d=new Jobtypen; forint i=0; ibi?bi:ai; di.job = ai=bi; di.ind

35、ex = i; sortd,n;012345A2571052B3841134key2541032jobTTFTFTindex0123455556int j=0, k=n-1; forint i=0; in; i+ ifdi.job cj+ = di.index; else ck- - = di.index; j = ac0; k = j+bc0; forint i=1; in; i+ j += aci;k = jk ? k+bci : j+bci; delete d; return k; /最优加工时间 012345A2571052B3841134排序之后排序之后:key2234510jobTTFFTTindex054213C051324j249192631k5917303437j jk k5657给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。nixxviniii1,1 , 0 ,max1nixCxwi