动态规划.ppt

《动态规划.ppt》由会员分享，可在线阅读，更多相关《动态规划.ppt（65页珍藏版）》请在三一办公上搜索。

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

2、 or 1F(n-1)+F(n-2)if n 1,Pseudo code for the recursive algorithm:F(n)1if n=0 or n=1 then2return 13else4return F(n-1)+F(n-2),Fibonacci number F(n),5,The execution of F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,6,The e

3、xecution of F(7),Computation of F(2)is repeated 8 times!,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,7,The execution of F(7),Computation of F(3)is also repeated 5 times!,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,

4、F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,8,The execution of F(7),Many computations are repeated!How to avoid this?,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,9,Idea for improvement,Memoriza

5、tion Store F(i)somewhere after we have computed its value Afterward,we dont need to re-compute F(i);we can retrieve its value from our memory.,F(n)1 if(vn 0)then2 vn F(n-1)+F(n-2)3 return vn,Main()1 v0=v1 12 for i 2 to n do3 vi=-14 output F(n),10,Look at the execution of F(7),v0v1v2v3v4v5v6v7,F7,F6,

6、F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,11,Look at the execution of F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,12,Look at

7、 the execution of F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,13,Look at the execution of F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,

8、F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,14,Look at the execution of F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,15,Look at the execution of F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1

9、,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,16,F1,F0,Look at the execution of F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,17,F1,F0,F2,F1,F0,F1,Look at the execution of

10、 F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,18,F1,F0,F2,F1,F0,F1,Look at the execution of F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1

11、,19,F1,F0,F2,F1,F0,F2,F1,F0,F2,F1,F0,F3,F1,F1,Look at the execution of F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F4,F4,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,20,F1,F0,F2,F1,F0,F2,F1,F0,F2,F1,F0,F3,F1,F1,Look at the execution of F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F

12、1,F4,F4,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,21,F1,F0,F2,F1,F0,F2,F1,F0,F2,F1,F0,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,Look at the execution of F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F4,F4,22,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1

13、,F1,Look at the execution of F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F0,F1,F4,23,ObservationThe 2nd version still make many function calls,and each wastes times in parameters passing,dynamic linking,.In general,to compute F(i),we need F(i-1)&F(i-2)onlyIdea to further improveCompute th

14、e values in bottom-up fashion.That is,compute F(2)(we already know F(0)=F(1)=1),then F(3),then F(4),This new implementation saves lots of overhead.,Can we do even better?,F(n)1A0=A1 12for i 2 to n do3Ai Ai-1+Ai-24return An,24,Recursive vs Dynamic programming,Recursive version:F(n)1if n=0 or n=1 then

15、2return 13else4return F(n-1)+F(n-2),Dynamic Programming version:F(n)1A0=A1 12for i 2 to n do3Ai Ai-1+Ai-24return An,TooSlow!,Efficient!Time complexity is O(n),25,Summary of the methodology,Write down a formula that relates a solution of a problem with those of sub-problems.E.g.F(n)=F(n-1)+F(n-2).Ind

16、ex the sub-problems so that they can be stored and retrieved easily in a table(i.e.,array)Fill the table in some bottom-up manner;start filling the solution of the smallest problem.This ensures that when we solve a particular sub-problem,the solutions of all the smaller sub-problems that it depends

17、are available.,For historical reasons,we call such methodologyDynamic Programming.In the late 40s(when computers were rare),programming refers to the tabular method.,26,27,28,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，再从子问题的解得到原问题的解。,算法总体思想,29,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复

18、计算了许多次。,算法总体思想,30,保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。动态规划法用一个表来记录所有已解决的子问题的答案。具体的动态规划算法尽管多种多样，但它们具有相同的填表方式。,算法总体思想,T(n),31,回顾分治法,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随

19、着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,32,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。,步骤是动态规划算法的基本步骤。如果只需要求

20、出最优值的情形，步骤可以省略 若需要求出问题的一个最优解，则必须执行步骤，步骤中记录的信息是构造最优解的基础；,33,矩阵连乘问题,34,矩阵连乘问题,问题描述：给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2,n-1。如何确定矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积所需要的数乘次数最少。,35,矩阵连乘问题,矩阵乘法满足结合律 矩阵连乘可以有不同的计算次序。矩阵连乘的计算次序可以用加括号的方式来确定 若矩阵连乘已完全加括号，则其计算次序完全确定。,36,完全加括号的矩阵连乘积可递归地定义为:（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示

21、为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即 A=(BC)。,矩阵连乘问题,37,例，有四个矩阵A,B,C,D，它们的维数分别是：A=5010，B=1040,C=4030,D=305 连乘积ABCD共有五种完全加括号的方式(A(BC)D)16000(A(B(CD)10500(AB)(CD)36000(AB)C)D)87500(A(BC)D)34500,矩阵连乘问题,38,矩阵连乘问题,39,矩阵连乘问题,动态规划,将矩阵连乘积AiAi+1Aj简记为Ai:j，这里ij。,考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为(

22、AiAi+1Ak)(Ak+1Ak+2Aj)。,Ai:j的计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量,40,特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。（证明？）矩阵连乘计算次序问题的最优解包含着其子问题的最优解最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,1.分析最优解的结构,41,2.建立递归关系,设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n 又设 Ai的维数为pi-1pi 当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,

23、2,n 当ij时，mi,j=mi,k+mk+1,j+pi-1pkpj即可以递归地定义mi,j为：,42,43,3.计算最优值,void MatrixChain(int*p，int n，int*m，int*s)for(int r=2;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 mij)mij=t;sij=k;,*p 存放Ai的维数*m 存放最优值*s 存放断开位置,44,3.计算最优值,例 计算矩阵

24、连乘积A1A2A3A4A5A6,45,3.计算最优值,算法matrixChain复杂度分析：算法的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此，算法的计算时间上界为O(n3)。算法所占用的空间为O(n2)。,46,4.构造最优解,按算法计算出的断点矩阵s指示的加括号方式输出计算Ai:j的最优先次序。void Traceback(int i,int j,int*s)if(i=j)return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout“Multiplay A”i“,”sij;cout“

25、and A”sij+1“,”jendl;,47,动态规划算法的基本要素,1.最优子结构,如果问题的最优解是由其子问题的最优解来构造的，则称该问题具有最优子结构性质。在分析问题的最优子结构性质时，通常是先假设由问题的最优解导出子问题的解不是最优的，然后再设法说明，在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是使用动态规划算法求解的前提。,48,动态规划算法的基本要素,2.重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重

26、叠性质。动态规划算法，对每一个子问题只计算一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,49,动态规划算法的基本要素,3.备忘录方法,备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。一般的讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法比用备忘录方法好。此时，动态规划算法没有任何多余的计算。同时，对于许多问题，常可利用其规则的表格存取方式，

27、减少动态规划算法的时间和空间需求。当子问题空间中的部分子问题可以不必求解时，用备忘录的方法则较有利，因为从其控制结构可以看出，改方法只解那些确实需要求解的子问题。,int LookupChain(int i，int j)if(mij 0)return mij;if(i=j)return 0;int u=LookupChain(i，i)+LookupChain(i+1，j)+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t=LookupChain(i，k)+LookupChain(k+1，j)+pi-1*pk*pj;if(t u)u=t;sij=k;mij=

28、u;return u;,50,51,52,53,最长公共子序列问题,54,最长公共子序列问题,55,最长公共子序列问题,对于给定序列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。,56,最长公共子序列问题,给定2个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。问题描述：给定2个序列X=x1,x2,xm和Y=y1,y2,yn,找出X和

29、Y的最长公共子序列。,57,1.最长公共子序列的结构,设序列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个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,58,59,60,2.最优公共子序列的递归结构,用cij记录序列和的最长公共子序列的长度。其中，Xi=x1,x2,xi

30、；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故此时Cij=0。其它情况可由最优子结构性质可建立递归关系:,61,3.计算最优值,/cmn记录X和Y的最长公共子序列的长度/bij记录cij的值属于哪类子问题LCSLength(int m,int n,char*x,char*y,int*c,int*b)for(int i=1;i=cij-1)cij=ci-1j;bij=2;else cij=cij-1;bij=3;,62,63,4.构造最长公共子序列,void 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);coutxi;else if(bij=2)LCS(i-1，j，x，b);else LCS(i，j-1，x，b);,64,65,本周任务,习题3-14对维数为序列5,10,3,12,5,50,6的各距阵，找出其矩阵链乘积的一个最优加全部括号。说明如何在不用表b的情况下，通过已计算出的表c和原始序列Xm=和 Yn=，在O(m+n)时间内重构一个LCS.使用替换法证明P63递归公式的解为(2n),