《计算机算法设计与分析》PPT第三章 动态规划.ppt

《《计算机算法设计与分析》PPT第三章 动态规划.ppt》由会员分享，可在线阅读，更多相关《《计算机算法设计与分析》PPT第三章 动态规划.ppt（111页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机算法设计与分析PPT第三章动态规划 学习要点学习要点:n理解动态规划算法概念。理解动态规划算法概念。n掌握动态规划算法基本要素掌握动态规划算法基本要素(1)最优子结构性质最优子结构性质(2)重叠子问题性质重叠子问题性质n掌握设计动态规划算法的步骤。掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。递归地定义最优值。(3)以自底向上的方式计算出最优值。以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。2n基本概念基本概念状态状态：表示每个阶段开始

2、时，问题或系统所处的客观：表示每个阶段开始时，问题或系统所处的客观状况。状态既是该阶段的某个起点，又是前一个阶段状况。状态既是该阶段的某个起点，又是前一个阶段的某个终点。通常一个阶段有若干个状态。的某个终点。通常一个阶段有若干个状态。q状态无后效性状态无后效性：如果某个阶段状态给定后，则该阶段以后过：如果某个阶段状态给定后，则该阶段以后过程的发展不受该阶段以前各阶段状态的影响，也就是说状态程的发展不受该阶段以前各阶段状态的影响，也就是说状态具有马尔科夫性。具有马尔科夫性。q适于动态规划法求解的问题具有状态的无后效性适于动态规划法求解的问题具有状态的无后效性策略策略：各个阶段决策确定后，就组成了

3、一个决策序列，：各个阶段决策确定后，就组成了一个决策序列，该序列称之为一个策略。由某个阶段开始到终止阶段该序列称之为一个策略。由某个阶段开始到终止阶段的过程称为的过程称为子过程子过程，其对应的某个策略称为，其对应的某个策略称为子策略子策略。6最优性原理最优性原理nBellman最优性原理最优性原理q求解问题的一个最优策略序列的子策略序列总是最求解问题的一个最优策略序列的子策略序列总是最优的，则称该问题满足最优性原理。优的，则称该问题满足最优性原理。q注：对具有最优性原理性质的问题而言，如果有一注：对具有最优性原理性质的问题而言，如果有一决策序列包含有非最优的决策子序列，则该决策序决策序列包含有

4、非最优的决策子序列，则该决策序列一定不是最优的。列一定不是最优的。7n动态规划的思想实质是分治思想和解决冗余动态规划的思想实质是分治思想和解决冗余n动态规划算法与分治法类似，其基本思想也是将待求动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)=算法总体思想算法总体思想8n但是经分解得到的子问题往往不是互相独立的。不同子问题的但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被数目常常只有多

5、项式量级。在用分治法求解时，有些子问题被重复计算了许多次。重复计算了许多次。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)算法总体思想算法总体思想9n如果能够保存已解决的子问题的答案，而在需要时再如果能够保存已解决的子问题的答

6、案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。得到多项式时间算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2n/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)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)算法总体思想算法总体思想10动态规划基本步骤动态规划基本步骤找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。递归地划分子问题，递

7、归地划分子问题，递归地定义最优值，给出递归地定义最优值，给出最优解的递归式。最优解的递归式。以自底向上的方式计算出最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。注：注：步骤步骤是动态规划算法的基本步骤。如果只需要求出是动态规划算法的基本步骤。如果只需要求出最优值的情形，步骤最优值的情形，步骤可以省略；可以省略；若需要求出问题的一个最优解，则必须执行步骤若需要求出问题的一个最优解，则必须执行步骤，步，步骤骤中记录的信息是构造最优解的基础；中记录的信息是构造最优解的基础；11n给定给定n个矩阵个矩阵 ，其中，其中 与与 是是可

8、乘的可乘的，。考察这。考察这n个矩阵的连乘积个矩阵的连乘积n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。的方式来确定。n若一个矩阵连乘积的计算次序完全确定，也就是说该若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用连乘积已完全加括号，则可以依此次序反复调用2个个矩阵相乘的标准算法计算出矩阵连乘积矩阵相乘的标准算法计算出矩阵连乘积3.2矩阵连乘问题矩阵连乘问题12完全加括号的矩阵连乘积完全加括号的矩阵连乘

9、积n完全加括号的矩阵连乘积的递归定义：完全加括号的矩阵连乘积的递归定义：（1）单个矩阵是完全加括号的；）单个矩阵是完全加括号的；（2）矩阵连乘积）矩阵连乘积A是完全加括号的，则是完全加括号的，则A可表示可表示为为2个完全加括号的矩阵连乘积个完全加括号的矩阵连乘积B和和C的乘积并的乘积并加括号，即加括号，即1314矩阵连乘问题矩阵连乘问题n问题描述问题描述q给定给定n个矩阵个矩阵A1,A2,An，其中，其中Ai与与Ai+1是可乘的，矩阵是可乘的，矩阵Ai的维数为的维数为pi-1pi，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连

10、乘积需要的数乘次数最少。得依此次序计算矩阵连乘积需要的数乘次数最少。n注意注意设设Apq,Aqr两矩阵相乘，普通乘法次数为两矩阵相乘，普通乘法次数为pqr；加括号对乘法次数的影响加括号对乘法次数的影响1516n穷举法穷举法q列举出所有可能的计算次序，并计算出每一种计算次序列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算次序。算法复杂度分析：算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)

11、可以得到关于P(n)的递推式如下：因此，穷举法不是一个有效算法。因此，穷举法不是一个有效算法。呈指数增长呈指数增长17n计算量小的优先计算计算量小的优先计算qn个矩阵的连乘积共有个矩阵的连乘积共有n-1次乘法计算。首先在次乘法计算。首先在n-1次乘法计算中选择乘法计算量最小的两个矩阵优先次乘法计算中选择乘法计算量最小的两个矩阵优先计算，然后再在剩下的计算，然后再在剩下的n-2次乘法计算中选择计算次乘法计算中选择计算量最小的两个矩阵进行计算，依此往下。量最小的两个矩阵进行计算，依此往下。q该解决策略在某些情况下可得到最优解，但在很多该解决策略在某些情况下可得到最优解，但在很多情况下得不到最优解。

12、如上例的第情况下得不到最优解。如上例的第(5)种完全加括种完全加括号方式即采用该策略，但得到的显然不是最优解。号方式即采用该策略，但得到的显然不是最优解。18n矩阵维数大的优先计算矩阵维数大的优先计算q在在n个矩阵的个矩阵的n+1个维数序列个维数序列p0,p1,p2,pn中选择维数的中选择维数的最大值（设为最大值（设为pi），并把相邻两个含有维数），并把相邻两个含有维数pi的矩阵优先进的矩阵优先进行计算，然后在剩下的行计算，然后在剩下的n个维数序列中再次选择维数的最大个维数序列中再次选择维数的最大值，进行相应矩阵的乘法运算，依此往下。值，进行相应矩阵的乘法运算，依此往下。q该策略与上一种策略相

13、似，在某些情况下可得到最优解，但该策略与上一种策略相似，在某些情况下可得到最优解，但在有些情况下得不到最优解。如上例的第在有些情况下得不到最优解。如上例的第(3)种完全加括号种完全加括号方式就是采用该策略，显然它得到的是最优解。方式就是采用该策略，显然它得到的是最优解。q当个矩阵的维数改为当个矩阵的维数改为5010,1040,4030和和305时，时，可验证采用该策略得到的不是最优解。可验证采用该策略得到的不是最优解。以上两种策略实质都是基于某种贪心选择的贪心算法，这种算法不以上两种策略实质都是基于某种贪心选择的贪心算法，这种算法不一定能得到问题的全局最优解。在下一章我们将详细讨论此种策略。一

14、定能得到问题的全局最优解。在下一章我们将详细讨论此种策略。19n分治法分治法q将矩阵连乘积将矩阵连乘积AiAi+1Aj简记为简记为Ai:j。q设设n个矩阵的连乘积个矩阵的连乘积A1A2An的计算次序在矩阵的计算次序在矩阵Ak和和Ak+1之间将矩阵链断开，之间将矩阵链断开，1k1时，时，n该算法的计算时间该算法的计算时间T(n)有指数下界。有指数下界。n分治法是该问题的一个可行方法，但不是一个分治法是该问题的一个可行方法，但不是一个有效算法。有效算法。22n为何分治法的效率如此低下？为何分治法的效率如此低下？nrecurmatrixChain(1,4)计算计算A1：4的递归树。的递归树。n从图中

15、可看出，许多从图中可看出，许多子问题被重复计算子问题被重复计算。n这是分治法效率低下的根本原因。这是分治法效率低下的根本原因。23n该问题可用分治思想解决，并存在大量冗余，该问题可用分治思想解决，并存在大量冗余，可用动态规划求解。可用动态规划求解。24n动态规划动态规划矩阵连乘问题矩阵连乘问题将矩阵连乘积将矩阵连乘积 简记为简记为Ai:j Ai:j，i i j j。考察计算考察计算Ai:jAi:j的最优计算次序。设这个计算次序在矩阵的最优计算次序。设这个计算次序在矩阵A Ak k和和A Ak+1k+1之间将矩阵链断开，之间将矩阵链断开，i i kjkj，则其相应完全，则其相应完全加括号方式为加

16、括号方式为计算量为计算量为Ai:kAi:k的计算量加上的计算量加上Ak+1:jAk+1:j的计算量，再加上的计算量，再加上Ai:kAi:k和和Ak+1:jAk+1:j相乘的计算量相乘的计算量251、分析最优解的结构、分析最优解的结构n特征特征q计算计算Ai:j的最优次序所包含的计算矩阵子链的最优次序所包含的计算矩阵子链 Ai:k和和Ak+1:j的次序也是最优的。（反证可的次序也是最优的。（反证可得）得）n矩阵连乘计算次序问题的最优解包含着其子问题的矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优解。这种性质称为最优子结构性质最优子结构性质。n问题的最优子结构性质是该问题可用

17、动态规划算法问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。求解的显著特征。2627n假设计算假设计算Ai:j(1ijn)Ai:j(1ijn)所需要的最少数乘所需要的最少数乘次数为次数为mi,jmi,j，则原问题的最优值为，则原问题的最优值为m1,n m1,n qi=ji=j时，时，Ai:j=AAi:j=Ai i，mi,i=0mi,i=0，i=1,2,ni=1,2,nqijij时，时，的维数为 2、建立递归关系、建立递归关系28n递归地定义递归地定义mi,jk的位置只有的位置只有j-i种种可能可能取得的k为Ai:j最优次序中的断开位置，并记录到表sij中，即sijk。注：mij实际

18、是子问题最优解的解值，保存下来避免重复计算。29n对于对于1ijn不同的有序对不同的有序对(i，j)对应于不同的对应于不同的子问题。不同子问题的个数最多只有子问题。不同子问题的个数最多只有n由此可见，在递归计算时，由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的。这也是该问题可用动态规划算法求解的又一显著特征。又一显著特征。3、计算最优值计算最优值30n用动态规划算法解此问题，可依据其递归式以用动态规划算法解此问题，可依据其递归式以自自底向上底向上的方式进行计算。的方式进行计算。n在计算过程中，保存已解决的子问题答案。在计算过程中，保存已解决的子问题答案。n

19、每个子问题只计算一次，而在后面需要时只要简每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。多项式时间的算法。31svoid MatrixChain(int*p，int n，int*m，int*s)/n是连乘矩阵数目，A1A2An；p是矩阵维数，Ai的维数为pi-1pi(1in)；/m是n个矩阵连乘的数乘次数最小值；s存储矩阵连乘的最优计算次序 for(int i=1;i=n;i+)mii=0;/对角线置0,计算Ai.Ai的乘法次数,链长为1 for(int r=2;r=n;r+)/分别计算r个矩阵连

20、乘的最小数乘次数 for(int i=1;i=n-r+1;i+)int j=i+r-1;mij=mi+1j+pi-1*pi*pj;/Ai.Aj在矩阵i处断开时的数乘次数 sij=i;/记录取得Ai.Aj当前数乘次数的断开位置 for(int k=i+1;k j;k+)/计算Ai.Aj的最小数乘次数 int t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;3233A1A2A3A4A5A630 3535 1515 55 1010 2020 25算法复杂度分析：算法复杂度分析：算法MatrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的

21、计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。设要计算矩阵连乘积中各矩阵的维数分别为：344、用动态规划法求最优解用动态规划法求最优解nMatrixChain已记录了构造最优解所需要的全部信息。已记录了构造最优解所需要的全部信息。qSij 表明计算矩阵表明计算矩阵Ai,j的最佳方式应在矩阵的最佳方式应在矩阵Ak和和Ak+1之间断开，即之间断开，即最优的加括号方式应为最优的加括号方式应为(Ai:k)(Ak+1:j)。n从从s1n记录的信息可知记录的信息可知A1:n的最优加括号方式为的最优加括号方式为(Ai:s1n)(As1

22、n+1:n)。qAi:s1n的最优加括号方式为的最优加括号方式为(Ai:s1s1n)(As1s1n+1:s1s1n)qAs1n+1:n的最优加括号方式在的最优加括号方式在ss1n+1n处断开。处断开。n照此递推，最终可确定照此递推，最终可确定A1:n的最优完全加括号方式，即构的最优完全加括号方式，即构造出问题的一个最优解。造出问题的一个最优解。35n算法算法traceback：按照：按照MatrixChain计算出的计算出的断点断点s指示加括号方式输出计算指示加括号方式输出计算Ai:j的最优计的最优计算次序。算次序。Void traceback(int i,int j,int*s)/按算法按算

23、法MatrixChain计算计算出的断点矩阵出的断点矩阵s指示的加括号方式输出计算指示的加括号方式输出计算Ai:j的最优计的最优计算次序算次序 if(i=j)return;traceback(s,i,sij);traceback(s,sij+1,j);cout“Multiply A”i“,”sij;cout“and A”(sij+1)“,”j 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(

24、i，k)+LookupChain(k+1，j)+pi-1*pk*pj;if(t u)u=t;sij=k;mij=u;return u;n备忘录方法的控制结构与备忘录方法的控制结构与直接递归方法直接递归方法的控制结构相同，的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。备需要时查看，避免了相同子问题的重复求解。39n动态规划的设计技巧：动态规划的设计技巧：阶段的划分、状态的表示阶段的划分、状态的表示和和存储表存储表的设计的设计n在动态规划的设计过程中，在动态规划的设计过程中，阶段的划分阶

25、段的划分和和状态的表示状态的表示是其是其中最重要的两步，这两步会直接影响该问题的计算复杂性中最重要的两步，这两步会直接影响该问题的计算复杂性和存储表设计，有时候阶段划分或状态表示的不合理还会和存储表设计，有时候阶段划分或状态表示的不合理还会使得动态规划法不适用。使得动态规划法不适用。n问题的阶段划分和状态表示，需要具体问题具体分析，没问题的阶段划分和状态表示，需要具体问题具体分析，没有一个清晰明朗的方法。有一个清晰明朗的方法。n在实际应用中，许多问题的阶段划分并不明显，这时如果在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以刻意地划分阶段法反

26、而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优性原理），则可以考虑用动子问题的最优解（即满足最优性原理），则可以考虑用动态规划解决。态规划解决。40n如何判断问题满足最优性原理？如何判断问题满足最优性原理？n思路：利用反证法，通过假设每一个子问题的思路：利用反证法，通过假设每一个子问题的解都不是最优解，然后导出矛盾，即可做到这解都不是最优解，然后导出矛盾，即可做到这一点。一点。41例例1：设：设G是一个有向加权图，则是一个有向加权图，则G从顶点从顶点i到顶点到顶点j之间的最之间的最短

27、路径问题满足最优性原理。短路径问题满足最优性原理。证明：（反证法）证明：（反证法）q设设iipiqj是一条最短路径，但其中子路径是一条最短路径，但其中子路径ipiqj不是不是最优的。最优的。q假设最优的子路径为假设最优的子路径为ipiqj，则我们可以重新构造一，则我们可以重新构造一条路径：条路径：iipiqj，显然该路径长度小于，显然该路径长度小于iipiqj，与与iipiqj是顶点是顶点i到顶点到顶点j的最短路径相矛盾。的最短路径相矛盾。q所以，原问题满足最优性原理。所以，原问题满足最优性原理。42例例2：有向图的最长简单路径问题不满足最优性：有向图的最长简单路径问题不满足最优性原理。原理。

28、n证明：证明：q如右图所示，如右图所示，qrt是是q到到t的最长简单路径，而的最长简单路径，而qr的的最长简单路径是最长简单路径是qstr，rt的最长简单路径是的最长简单路径是rqst，但，但qr和和rt的最长简单路径合起来并不是的最长简单路径合起来并不是q 到到t的最长简单路径。的最长简单路径。q所以，原问题并不满足最优性原理。所以，原问题并不满足最优性原理。q注：因为注：因为qr 和和rt的子问题都共享路径的子问题都共享路径qst，组合，组合成原问题解时，有重复的路径对原问题是不允许的。成原问题解时，有重复的路径对原问题是不允许的。43444546474849505152实例二实例二 花束

29、摆放问题花束摆放问题1、问题描述、问题描述n现有现有F束不同品种的花束，同时有至少同样数束不同品种的花束，同时有至少同样数量的花瓶被按顺序摆成一行，其位置固定于架量的花瓶被按顺序摆成一行，其位置固定于架子上，并从子上，并从1至至V按从左到右顺序编号，按从左到右顺序编号，V是花是花瓶的数目瓶的数目(FV)。花束可以移动，并且每束花。花束可以移动，并且每束花用用1至至F的整数唯一标识。标识花束的整数决定的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，如果了花束在花瓶中排列的顺序，如果ij，花束，花束i必须放在花束必须放在花束j左边的花瓶中。每个花瓶只能左边的花瓶中。每个花瓶只能放一束花

30、。如果花瓶的数目大于花束的数目，放一束花。如果花瓶的数目大于花束的数目，则多余的花瓶空置。则多余的花瓶空置。53n每一个花瓶都具有各自的特点。因此，当各个每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学花瓶中放入不同的花束时，会产生不同的美学效果，并以一美学值效果，并以一美学值(一个整数一个整数)来表示，空置来表示，空置花瓶的美学值为零。为取得最佳美学效果，必花瓶的美学值为零。为取得最佳美学效果，必须在保持花束顺序的前提下，使花束的摆放取须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。请求出具有最大美学值的一得最大的美学值。请求出具有最大美学值的一种摆放

31、方式。种摆放方式。542、解题思路、解题思路n状态表示法一：状态表示法一：q设设A(i,j)表示第表示第i种花束摆在第种花束摆在第j个花瓶中获得的美学个花瓶中获得的美学值。值。S(i,k)表示第表示第i种花束摆在第种花束摆在第k个花瓶中时个花瓶中时(ki)，前，前i种花束能够获得的最大美学值种花束能够获得的最大美学值(之和之和)。这样，。这样，原问题的最优值可通过计算原问题的最优值可通过计算maxS(F,k)|FkV获获得。得。q下面分析这种状态表示法描述问题的方式是否具备下面分析这种状态表示法描述问题的方式是否具备了用动态规划求解的基本要素。了用动态规划求解的基本要素。55q最优子结构性质：

32、对满足最优子结构性质：对满足FkV的的k，设，设T(F,k)是达是达到最优值到最优值S(F,k)的一种最佳摆放方式，其中，第的一种最佳摆放方式，其中，第F-1种花束摆在第种花束摆在第j个花瓶中个花瓶中(j1,kin初始条件为：初始条件为：S1,1=A1,1S1,k=maxA(1,k),S1,k-1,k1Si,i=Si-1,i-1+A(i,i),i1593.3最长公共子序列最长公共子序列n子序列定义子序列定义 若给定序列若给定序列X=x1,x2,xm，则另一序列，则另一序列Z=z1,z2,zk是是X的的子序列子序列，是指：，是指：存在一个严格递增下标序列存在一个严格递增下标序列i1,i2,ik使

33、使得对于所有得对于所有j=1,2,k有：有：zj=xij。例：序列例：序列Z=B，C，D，B是序列是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标的子序列，相应的递增下标序列为序列为2，3，5，7。60例：例：n两个两个DNA序列序列S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAAS2=GTCGTTCGGAATGCCGTTGCTCTGTAAALCS=GTCGTCGGAAGCCGGCCGAA61n两个序列的公共子序列定义两个序列的公共子序列定义 给定给定2个序列个序列X和和Y，当另一序列，当另一序列Z既是既是X的子序的子序列又是列又是Y的子序列时，称的子序列时，称Z是

34、序列是序列X和和Y的的公共公共子序列子序列。n问题问题 给定给定2个序列个序列X=x1,x2,xm和和Y=y1,y2,yn，找出，找出X和和Y的最长公共子序的最长公共子序列。列。62定理定理：(一个一个LCS的最优子结构的最优子结构)设序列设序列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，

35、则，则Z是是X和和yn-1的最长公共子序列。的最长公共子序列。2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质最优子结构性质。1、最长公共子序列的结构、最长公共子序列的结构6364652、子问题的递归结构、子问题的递归结构n将将X和和Y的的LCS分解为分解为2种情况：种情况：q如如xm=yn，找，找Xm-1和和Yn-1的的LCS；/解一个子问题解一个子问题q如如xmyn，找，找Xm-1和和Y的的LCS；找找X和和Yn-1的的LCS；/解两个子问题解两个子问题 取两者中的最大的；取两者中的最大的；66用用cij记录序列记录序列Xi和和Yj

36、的最长公共子序列的长度。的最长公共子序列的长度。Xi=x1,x2,xi；Yj=y1,y2,yj。cij的递归方程：的递归方程：当当i=0或或j=0时，空序列是时，空序列是Xi和和Yj的最长公共子序列，的最长公共子序列，Cij=0。67683、计算最优值、计算最优值void LCSLength(int m，int 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

37、=3;069n过程过程LCSLength以两个序列以两个序列x、y为输入，它把为输入，它把ci,j的值填入一个按的值填入一个按行行计算表项的表计算表项的表c0.m,0.n中，并中，并维护表维护表b1.m,1.n以简化最优解的构造。以简化最优解的构造。nc0.m,0.n/存放最优解值，计算时行优先存放最优解值，计算时行优先nb1.m,1.n/解矩阵，存放构造最优解信息解矩阵，存放构造最优解信息nbi,j指向一个表项，对应于在计算指向一个表项，对应于在计算ci,j时所选择的最时所选择的最优子问题的解。优子问题的解。n程序最后返回程序最后返回b和和c。cm,n包含包含X和和Y的一个的一个LCS的的长

38、度。长度。70n由于在所考虑的子问题空间中，总共有由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。向上地计算最优值能提高算法的效率。714、构造最长公共子序列、构造最长公共子序列n构造最长公共子序列构造最长公共子序列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);n说明说

39、明q当当bi,j=1时，即时，即xi=yj是是LCS的一个元素；的一个元素；q时间复杂度：时间复杂度：(m+n)72n构造解时，从构造解时，从bm,n出发，上溯至出发，上溯至i=0或或j=0，上溯过程中，当上溯过程中，当bi,j1时打印出时打印出xi或或yj73例：例：X=，Y=最优解：最优解：BCAB或或BCBA或或BADB745、算法的改进、算法的改进n在算法在算法LCSLength和和LCS中，可进一步将数中，可进一步将数组组b省去。省去。qcij的值仅由的值仅由ci-1j-1，ci-1j和和cij-1这这3个数组元素的值所确定。个数组元素的值所确定。q对于给定的数组元素对于给定的数组元

40、素cij，可以不借助于数组，可以不借助于数组b而仅借助于而仅借助于c本身在本身在O(1)时间内确定时间内确定cij的值的值是由是由ci-1j-1，ci-1j和和cij-1中哪一个值中哪一个值所确定的。所确定的。75n如果只需要计算最长公共子序列的长度，则算法如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。的空间需求可大大减少。q计算计算cij时，只用到数组时，只用到数组c的第的第i行和第行和第i-1行。行。q只用只用2行的数组空间就可计算出最长公共子序列行的数组空间就可计算出最长公共子序列的长度。的长度。n进一步的分析还可将空间需求减至进一步的分析还可将空间需求减至O(min(

41、m,n)。763.4最大子段和最大子段和n问题问题q给定由给定由n个整数个整数(可能为负整数可能为负整数)组成的序列组成的序列a1,a2,an，求该序列形如，求该序列形如 的子段和的最大值。的子段和的最大值。当所有整数均为负数时定义其最大子段和为当所有整数均为负数时定义其最大子段和为0。q依此定义，所求的最优值为依此定义，所求的最优值为77例：整数序列例：整数序列(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)n最大子段和为：最大子段和为：781、最大子段和问题的简单算法、最大子段和问题的简单算法n简单算法简单算法q数组数组a 存储给定的存储给定的n个整数个整数q

42、时间复杂度为时间复杂度为O(n3)79n改进改进q对对k循环可以省略循环可以省略q改进后的算法时间复杂改进后的算法时间复杂度为度为O(n2)802、最大子段和问题的分治算法、最大子段和问题的分治算法n将将a1:n分为长度相等的两段分为长度相等的两段a1:n/2和和an/2+1:n，分，分别对两区段求最大子段和，则别对两区段求最大子段和，则a1:n的最大子段和有三的最大子段和有三种情形：种情形：a1:n的最大子段和与的最大子段和与a1:n/2的最大子段和相同的最大子段和相同a1:n的最大子段和与的最大子段和与an/2:n的最大子段和相同的最大子段和相同a1:n的最大子段和为的最大子段和为q对对可

43、递归求解可递归求解q对对可知可知an/2、an/2+1一定在最大和子段中一定在最大和子段中n在在a1:n/2中计算，中计算，n在在an/2+1:n中计算，中计算，ns1+s2是该情况下的最大值。是该情况下的最大值。81int MaxSubSum(int*a,int left,int right)/返回最大子段和返回最大子段和int sum=0;if(left=right)sum=aleft0?aleft:0;else int center=(left+right)/2;int leftsum=MaxSubSum(a,left,center);int rightsum=MaxSubSum(a,c

44、enter+1,right);int s1=0;int lefts=0;for(int i=center;i=left;i-)lefts+=ai;if(leftss1)s1=lefts;/forint MaxSum(int n,int*a)return MaxSubSum(a,1,n);int s2=0;int rights=0;for(int i=center+1;is2)s2=rights;/for sum=s1+s2;if(sumleftsum)sum=leftsum;if(sumrightsum)sum=rightsum;/ifreturn sum;/endn复杂度分析复杂度分析833

45、、最大子段和问题的动态规划算法、最大子段和问题的动态规划算法描述最优解的结构描述最优解的结构n子问题定义：考虑所有下标以子问题定义：考虑所有下标以j结束的最大子结束的最大子段和段和bj，即，即n原问题与子问题的关系：原问题与子问题的关系：84递归定义最优解的值递归定义最优解的值 bj=maxbj-1+aj,aj,1jn85求最大子段和的动态规划算法求最大子段和的动态规划算法int MaxSum(int n,int*a)int sum=0,b=0;/sum存储当前最大的存储当前最大的bj,b存储当前存储当前bj for(int i=1;i0)b+=ai;else b=ai;/b=0 if(bsu

46、m)sum=b;return sum;864、最大子段和问题与动态规划算法的推广、最大子段和问题与动态规划算法的推广最大子矩阵和问题最大子矩阵和问题n给定一个给定一个m行行n列的整数矩阵列的整数矩阵A，试求矩阵，试求矩阵A的一的一个子矩阵，使其各元素之和为最大。个子矩阵，使其各元素之和为最大。n二维数组二维数组a1:m1:n表示给定表示给定m行行n列的整数矩阵。列的整数矩阵。n子数组子数组ai1:i2j1:j2表示左上角和右下角行列坐标分别表示左上角和右下角行列坐标分别为为(i1,j1)和和(i2,j2)的子矩阵。的子矩阵。n各元素之和各元素之和n最大子矩阵和问题的最优值为最大子矩阵和问题的最

47、优值为87最大最大m子段和问题子段和问题n给定由给定由n个整数（可能为负整数）组成的序列个整数（可能为负整数）组成的序列a1,a2,an，以及一个正整数，以及一个正整数m，要求确定序列，要求确定序列a1,a2,an的的m个不相交子段，使这个不相交子段，使这m个子段的总个子段的总和达到最大。和达到最大。q设设b(i,j)表示数组表示数组a的前的前j项中项中i个子段和的最大值，个子段和的最大值，且第且第i个子段含个子段含aj 。q所求的最优值为所求的最优值为 。88n计算计算b(i,j)的递归式为的递归式为n初始时，初始时，893.5多段图规划多段图规划n问题描述问题描述q多段图多段图G=(V,E

48、)是一个有向图，且具有以下特征：是一个有向图，且具有以下特征：n划分为划分为k2个不相交的集合个不相交的集合Vi,1ik;nV1和和Vk分别只有一个结点分别只有一个结点s(源点源点)和和t(汇点汇点)；n若若E(G)，uVi，则，则vVi+1,边上成边上成本记本记c(u,v)；若；若不属于不属于E(G)，边上成本，边上成本记记c(u,v)=。n求由求由s到到t的最小成本路径。的最小成本路径。90例：一个例：一个5-段图段图n求从求从s到到t的最短路径。的最短路径。91n多段图问题满足最优性原理多段图问题满足最优性原理q设设s,vip,viq,t是一条由是一条由s到到t的最短路径，则的最短路径，

49、则vip,viq,t也是由也是由vip到到t的最短路径。的最短路径。(反证即可反证即可)n递归式推导递归式推导q设设cost(i,j)是是Vi中结点中结点vj到汇点到汇点t的最小成本路径的成本，的最小成本路径的成本，递归式为：递归式为：92n计算过程(以5-段图为例)ncost(4,9)=4,cost(4,10)=2,cost(4,11)=ncost(3,6)=7,cost(3,7)=5,cost(3,8)=7ncost(2,2)=7,cost(2,3)=9,cost(2,4)=18,cost(2,5)=15ncost(1,1)=min9+cost(2,2),7+cost(2,3),3+cos

50、t(2,4),2+cost(2,5)=16n构造解：解1(1,2,7,10,12)，解2(1,3,6,10,12)93943.60-1背包问题背包问题n问题描述问题描述q给定给定n种物品和一个背包。物品种物品和一个背包。物品i的重量是的重量是wi，其价值为，其价值为vi，背包的容量为，背包的容量为C。问应如何选择装入背包的物品，。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大使得装入背包中物品的总价值最大?95n0-1背包问题是一个特殊的整数规划问题。背包问题是一个特殊的整数规划问题。n求求(x1,x2,xn)使目标函数最大，其中使目标函数最大，其中c0,wi 0,vi 0,1in