动态规划new讲稿.ppt

《动态规划new讲稿.ppt》由会员分享，可在线阅读，更多相关《动态规划new讲稿.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划new第一页，讲稿共六十五页哦推荐书籍推荐书籍 第二页，讲稿共六十五页哦动态规划的历史（动态规划的历史（1/51/5）有有许许多多问问题题，用用穷穷举举法法才才能能得得到到最最佳佳解解。苦苦输输入入量量n n稍稍大大一一些些，计计算算量量太太大大，特特别别对对渐渐近近时时间间复复杂杂性性为为输输入入量量的的指指数数函函数数的的问问题题，计计算算机机无无法法完完成成。采采用用动动态态规规划划（Dynamic Dynamic programmingprogramming）能能得得到到比比穷穷举举法法更更有有效效的的算算法法。动动态态规规划划的的指指导导思思想想是是，在在每每种种情情况况下下

2、，列列出出各各种种可可能能的的局局部部解解，从从局局部部解解中中挑挑出出那那些些有有可可能能产产生生最最佳佳的的结结果果而而扬扬弃弃其其余余，从而大大缩减了计算量。从而大大缩减了计算量。第三页，讲稿共六十五页哦动态规划的历史动态规划的历史（2/52/5）动态规划遵循的动态规划遵循的“最佳原理最佳原理”简而言之，简而言之，“一一个最优策略的子策略总是最优的个最优策略的子策略总是最优的”。动态规划是运。动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化筹学的一个分支，它是解决多阶段决策过程最优化的一种方法，大约产生于的一种方法，大约产生于5050年代，由美国数学家年代，由美国数学家贝尔曼贝尔

3、曼（RBellmanRBellman）等人，根据一类多阶段决策）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相问题的特点，把多阶段决策问题变换为一系列互相联系单阶段问题，然后逐个加以解决。联系单阶段问题，然后逐个加以解决。第四页，讲稿共六十五页哦动态规划的历史动态规划的历史（3/53/5）动态规划开始只是应用于动态规划开始只是应用于多阶段决策性多阶段决策性问题，问题，后来渐渐被发展为解决后来渐渐被发展为解决离散最优化问题离散最优化问题的有效手段，的有效手段，进一步应用于一些连续性问题上。然而，动态规划进一步应用于一些连续性问题上。然而，动态规划更像是一种思想而非算法，它没

4、有固定的更像是一种思想而非算法，它没有固定的数学模型数学模型，没有固定的实现方法，其正确性也缺乏严格的理论没有固定的实现方法，其正确性也缺乏严格的理论证明。因此，一直以来动态规划的数学理论模型是证明。因此，一直以来动态规划的数学理论模型是一个研究的热点。一个研究的热点。第五页，讲稿共六十五页哦动态规划的历史（动态规划的历史（4/54/5）贝尔曼，贝尔曼，R Richard Bellman(1920R Richard Bellman(19201984)1984)美国美国数学家数学家，美国科学院院士美国科学院院士，动态规划的创始人动态规划的创始人。19201920年年8 8月月2626日生于美国纽

5、约。日生于美国纽约。19841984年年3 3月月1919日逝世。日逝世。19411941年在布鲁克年在布鲁克林学院毕业，获理学士学位，林学院毕业，获理学士学位，19431943年在威斯康星大学获理学硕士学年在威斯康星大学获理学硕士学位，位，19461946年在普林斯顿大学获博士学位。年在普林斯顿大学获博士学位。1946194619481948年在普林斯顿年在普林斯顿大学任助理教授大学任助理教授,1948,194819521952年在斯坦福大学任副教授年在斯坦福大学任副教授,1953,195319561956年年在美国兰德公司任研究员，在美国兰德公司任研究员，19561956年后在南加利福尼亚

6、大学任数年后在南加利福尼亚大学任数学教授、电气工程教授和医学教授。学教授、电气工程教授和医学教授。贝尔曼因提出动态规划而获美国数学会和美国工程数贝尔曼因提出动态规划而获美国数学会和美国工程数学与应用数学会联合颁发的第一届维纳奖金（学与应用数学会联合颁发的第一届维纳奖金（19701970），卡内基），卡内基梅隆大学颁发的第一届迪克森奖金梅隆大学颁发的第一届迪克森奖金(1970)(1970)，美国管理科学研究会，美国管理科学研究会和美国运筹学会联合颁发的诺伊曼理论奖金和美国运筹学会联合颁发的诺伊曼理论奖金(1976)(1976)。19771977年贝尔年贝尔曼当选为曼当选为美国艺术与科学研究院院士

7、美国艺术与科学研究院院士和和美国工程科学院院士美国工程科学院院士。第六页，讲稿共六十五页哦动态规划的历史（动态规划的历史（5/55/5）贝尔曼因在研究贝尔曼因在研究多段决策过程多段决策过程中提出动态规划而闻名于世。中提出动态规划而闻名于世。19571957年他的专著年他的专著动态规划动态规划出版后，被迅速译成俄文、日出版后，被迅速译成俄文、日文、德文和法文，对文、德文和法文，对控制理论界控制理论界和和数学界数学界有深远影响。贝有深远影响。贝尔曼还把不变嵌入原理应用于理论物理和数学分析方面，尔曼还把不变嵌入原理应用于理论物理和数学分析方面，把两点边值问题化为初值问题，简化了问题的分析和求解把两点

8、边值问题化为初值问题，简化了问题的分析和求解过程。过程。19551955年后贝尔曼开始研究年后贝尔曼开始研究算法算法、计算机仿真计算机仿真和和人工智人工智能能，把建模与仿真等数学方法应用到工程、经济、社会和医，把建模与仿真等数学方法应用到工程、经济、社会和医学等方面，取得许多成就。贝尔曼对稳定性的矩阵理论、时学等方面，取得许多成就。贝尔曼对稳定性的矩阵理论、时滞系统、自适应控制过程、分岔理论、微分和积分不等式等滞系统、自适应控制过程、分岔理论、微分和积分不等式等方面都有过贡献。方面都有过贡献。贝尔曼曾是贝尔曼曾是数学分析与应用杂志数学分析与应用杂志及及数学生物科数学生物科学杂志学杂志的主编，的

9、主编，科学与工程中的数学科学与工程中的数学丛书的主编。已丛书的主编。已出版出版3030本著作和本著作和7 7本专著，发表了本专著，发表了600600多篇研究论文。多篇研究论文。第七页，讲稿共六十五页哦动态规划的基本思想动态规划的基本思想 动态规划算法与分治法类似动态规划算法与分治法类似,其基本思想也是将待求解其基本思想也是将待求解问题分解成若干个子问题问题分解成若干个子问题,先求解子问题先求解子问题,然后从这些子问题然后从这些子问题的解得到原问题的解。的解得到原问题的解。动态规划算法与分治法不同的是，经分解得到的子动态规划算法与分治法不同的是，经分解得到的子问题往往不是相互独立的，有大量子问题

10、会重复出现。问题往往不是相互独立的，有大量子问题会重复出现。为了避免重复计算，动态规划法是用一个表来存放一计为了避免重复计算，动态规划法是用一个表来存放一计算过的子问题。算过的子问题。第八页，讲稿共六十五页哦动态规划算法适用于求解最优化问题动态规划算法适用于求解最优化问题 通常按如何四步骤设计动态规划算法：通常按如何四步骤设计动态规划算法：（1）找出最优解的性质，并刻画其结构特征；找出最优解的性质，并刻画其结构特征；（2）递归定义求最优值的公式递归定义求最优值的公式（3）以自底向上方式计算最优值以自底向上方式计算最优值（4）根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构

11、造最优解。第九页，讲稿共六十五页哦引导例子（引导例子（1/101/10）最短路径问题描述：最短路径问题描述：输入：输入：起点集合起点集合 S S1 1,S S2 2,.,.,S Sn n ，终点集合终点集合 T T1 1,T T2 2,.,.,T Tm m，中间结点集，中间结点集，边集边集E E，对于任意边，对于任意边e e有长度有长度输出：输出：一条从起点到终点的最短路一条从起点到终点的最短路第十页，讲稿共六十五页哦引导例子引导例子(2/10)(2/10)一个实例一个实例第十一页，讲稿共六十五页哦引导例子引导例子(3/10)(3/10)蛮力算法蛮力算法：考察每一条从某个起点到某个终点的路径，

12、计算长度，：考察每一条从某个起点到某个终点的路径，计算长度，从其中找出最短路径。从其中找出最短路径。在上述实例中，如果网络的层数为在上述实例中，如果网络的层数为k k，那么路径条数将接近于，那么路径条数将接近于2 2K K。动态规划算法动态规划算法：多阶段决策过程：多阶段决策过程.每步求解的问题是后面阶每步求解的问题是后面阶段求解问题的子问题段求解问题的子问题.每步决策将依赖于以前步骤的决策结每步决策将依赖于以前步骤的决策结果果.第十二页，讲稿共六十五页哦引导例子引导例子(4/10)(4/10)第十三页，讲稿共六十五页哦引导例子引导例子(5/10)(5/10)蛮力算法蛮力算法：考察每一条从某个

13、起点到某个终点的路径，计算：考察每一条从某个起点到某个终点的路径，计算长度，从其中找出最短路径。长度，从其中找出最短路径。在上述实例中，如果网络的层数为在上述实例中，如果网络的层数为k k，那么路径条数将接近于，那么路径条数将接近于2 2K K。动态规划算法动态规划算法：多阶段决策过程：多阶段决策过程.每步求解的问题是后面阶段求每步求解的问题是后面阶段求解问题的子问题解问题的子问题.每步决策将依赖于以前步骤的决策结果每步决策将依赖于以前步骤的决策结果.第十四页，讲稿共六十五页哦引导例子引导例子(6/10)(6/10)前边界不变，后边界前移前边界不变，后边界前移第十五页，讲稿共六十五页哦引导例子

14、引导例子(7/10)(7/10)第十六页，讲稿共六十五页哦引导例子引导例子(8/10)(8/10)第十七页，讲稿共六十五页哦引导例子引导例子(9/10)(9/10)求总长模求总长模1010的最小路径的最小路径第十八页，讲稿共六十五页哦引导例子引导例子(10/10)(10/10)第十九页，讲稿共六十五页哦3.1 3.1 矩阵连乘问题矩阵连乘问题 给定给定n n个矩阵个矩阵AA1 1，A A2 2，,A,An n,其中其中A Ai i与与A Ai+1 i+1 是可乘的。考察这是可乘的。考察这N N个矩个矩阵的连乘积阵的连乘积 A A1 1A A2 2A An n分析：分析：由于矩阵乘法满足结合律，

15、故计算矩连乘积由于矩阵乘法满足结合律，故计算矩连乘积 A A1 1A A2 2A An n可可以有多个计算次序。以有多个计算次序。例如：例如：(A(A1 1(A(A2 2(A(A3 3A A4 4)等等等等 (A(A1 1(A(A2 2A A3 3)A)A4 4)(A (A1 1A A2 2)(A)(A3 3A A4 4)第二十页，讲稿共六十五页哦先考虑两个矩阵乘积的计算量先考虑两个矩阵乘积的计算量设设A A为为rara caca矩阵矩阵 B B为为rbrb cbcb矩阵，矩阵，void matrixMultiply(int*a,int*b,int*c,int ra,int ca,int rb

16、,int cb)if(ca!=rb)error(“Cant multiply”);for(i=0;ira;+i)for(j=0;jcb;+j)cij=0;for(k=0;kca;+k)cij+=aik*bkj;第二十一页，讲稿共六十五页哦矩连连乘的不同计算次序会导致不同的计算量矩连连乘的不同计算次序会导致不同的计算量例如例如 AA1 1，A A2 2，A A3 3 A A1 1 10*100 10*100 A A2 2 100*5 100*5 A A3 3 5*50 5*50第第1 1种加括号种加括号 （A A1 1A A2 2）A A3 3）10*100*5 10*100*5 +10*5*5

17、0 =7500 +10*5*50 =7500第第2 2种加括号种加括号 （A A1 1（A A2 2A A3 3）100*5*50 100*5*50 +10*100*50 =75000 +10*100*50 =75000第二十二页，讲稿共六十五页哦所谓矩阵连乘问题：所谓矩阵连乘问题：对于给定对于给定n n个矩阵个矩阵AA1 1，A A2 2，,A,An n，其中其中A Ai i的维数是的维数是p pi-1 i-1 p pi i 如何确定计算矩阵连乘积如何确定计算矩阵连乘积A A1 1A A2 2A An n的计算次序，使得计的计算次序，使得计算矩阵连乘积的数乘次数最少。算矩阵连乘积的数乘次数最

18、少。方法一：方法一：枚举所有可能的计算次序。枚举所有可能的计算次序。(2n/n3/2)方法二：方法二：动态规划。动态规划。O(n3)第二十三页，讲稿共六十五页哦第一种：矩阵连乘的递归求解方法第一种：矩阵连乘的递归求解方法 记记 Ai:jAi:j为为 A Ai iA Ai+1i+1A Aj j 考察计算考察计算A1:nA1:n的最优计算次序的最优计算次序不妨设不妨设 计算计算A1:nA1:n最优次序的最后一次乘积位置在最优次序的最后一次乘积位置在 K K 处处 （A A1 1A A2 2A Ak k)（A Ak+1k+1A An n)k=1,2,k=1,2,n-1n-1其计算量为其计算量为 (1

19、)(1)计算计算 A1:kA1:k (2)(2)计算计算 Ak+1:nAk+1:n (3)(3)最后一次矩阵乘积最后一次矩阵乘积p p0 0 p pk k p pn n 第二十四页，讲稿共六十五页哦1.1.分析最优解的结构分析最优解的结构 计算计算A1:nA1:n的最优次序所包含的子链计算的最优次序所包含的子链计算 A1:k A1:k 和和 Ak+1:nAk+1:n也一定是最优次序的。也一定是最优次序的。事实上事实上 若有一个计算若有一个计算A1:kA1:k的次序所需的计算量更少，则取代之。的次序所需的计算量更少，则取代之。类似，计算类似，计算Ak+1:nAk+1:n的次序也一定是最优的。的次

20、序也一定是最优的。因此，矩阵连乘计算次序问题的最优解，包含了其子问题的因此，矩阵连乘计算次序问题的最优解，包含了其子问题的最优解。最优解。第二十五页，讲稿共六十五页哦2.2.建立递归关系，定义最优值建立递归关系，定义最优值 设计算设计算Ai:jAi:j所需的最少数乘次数为所需的最少数乘次数为mij mij 则原问题的最优值为则原问题的最优值为m1n m1n 不妨设不妨设 计算计算Ai:jAi:j最优次序的最后一次乘积位置在最优次序的最后一次乘积位置在 K K 处处 (（A Ai iA A2 2A Ak k)（A Ak+1k+1A Aj j)k=i,2,k=i,2,j-1j-1则则 mij=0

21、i=jmij=0 i=j MINMINmik+mk+1j+pmik+mk+1j+pi-1i-1p pk kp pj j ijij i=kj i=kj第二十六页，讲稿共六十五页哦3.3.伪码分析伪码分析算法算法1 RecurMatrixChain(P,i,j)1 RecurMatrixChain(P,i,j)1.mi,j1.mi,j2.si,ji2.si,ji3.for ki to j3.for ki to j 1 do1 do4.qRecurMatrixChain(P,i,k)4.qRecurMatrixChain(P,i,k)+RecurMatrixChain(P,k+1,j)+p +Rec

22、urMatrixChain(P,k+1,j)+pi i 1 1p pk kp pj j5.if q mi,j5.if q mi,j6.then mi,jq6.then mi,jq7.si,jk7.si,jk8.return mi,j8.return mi,j这里没有写出算法的全部描述（递归边界）这里没有写出算法的全部描述（递归边界）第二十七页，讲稿共六十五页哦4.4.子问题的产生子问题的产生 n=5n=5第二十八页，讲稿共六十五页哦5.5.子问题的计数子问题的计数边界不同的子问题：边界不同的子问题：1515个个递归计算的子问题：递归计算的子问题：8181个个边界次数边界次数边界次数1-181-

23、242-422-2122-353-523-3143-451-414-4124-542-515-581-321-51第二十九页，讲稿共六十五页哦6.6.结论结论与蛮力算法相比较，动态规划算法利用了子问题优化函数与蛮力算法相比较，动态规划算法利用了子问题优化函数间的依赖关系，时间复杂度有所降低。间的依赖关系，时间复杂度有所降低。动态规划算法的递归实现效率不高，原因在于同一子问题动态规划算法的递归实现效率不高，原因在于同一子问题多次重复出现，每次出现都需要重新计算一遍。多次重复出现，每次出现都需要重新计算一遍。采用空间换时间策略，记录每个子问题首次计算结果，后采用空间换时间策略，记录每个子问题首次计

24、算结果，后面再用时就直接取值，每个子问题只算一次。面再用时就直接取值，每个子问题只算一次。第三十页，讲稿共六十五页哦第二种矩阵连乘的迭代求解方法第二种矩阵连乘的迭代求解方法(1/10)(1/10)迭代求解的关键：迭代求解的关键：l每个子问题只计算一次每个子问题只计算一次l迭代过程迭代过程 从最小的子问题算起从最小的子问题算起 考虑计算顺序，以保证后面用到的值前面已经计考虑计算顺序，以保证后面用到的值前面已经计 算好算好 存储结构保存计算结果存储结构保存计算结果备忘录备忘录l解的追踪解的追踪 设计标记函数标记每步的决策设计标记函数标记每步的决策 考虑根据标记函数追踪解的算法考虑根据标记函数追踪解

25、的算法第三十一页，讲稿共六十五页哦第二种矩阵连乘的迭代求解方法第二种矩阵连乘的迭代求解方法(2/10)(2/10)矩阵连乘的不同子问题：矩阵连乘的不同子问题：长度长度1 1：只含只含1 1个矩阵，有个矩阵，有n n个子问题个子问题(不需要计算不需要计算)长度长度2 2：含含2 2个矩阵，个矩阵，n n-1-1个子问题个子问题长度长度3 3：含含3 3个矩阵，个矩阵，n n-2-2个子问题个子问题 .长度长度n n-1-1：含含n n-1-1个矩阵，个矩阵，2 2个子问题个子问题长度长度n n：原始问题，只有原始问题，只有1 1个个第三十二页，讲稿共六十五页哦第二种矩阵连乘的迭代求解方法第二种矩

26、阵连乘的迭代求解方法(3/10)(3/10)矩阵链乘法迭代顺序矩阵链乘法迭代顺序：长度为长度为1 1：初值，初值，m m i,ii,i=0=0长度为长度为2 2：1.2,2.3,3.4,.,1.2,2.3,3.4,.,n n-1.-1.n n长度为长度为3 3：1.3,2.4,3.5,.,1.3,2.4,3.5,.,n n-2.-2.n n .长度为长度为n n-1-1：1.1.n n-1,2.-1,2.n n长度为长度为n n：1.1.n n第三十三页，讲稿共六十五页哦第二种矩阵连乘的迭代求解方法第二种矩阵连乘的迭代求解方法(4/10)(4/10)n=8的子问题计算顺序：的子问题计算顺序：第

27、三十四页，讲稿共六十五页哦第二种矩阵连乘的迭代求解方法第二种矩阵连乘的迭代求解方法(5/10)(5/10)void MatricChain(int*p,int n,int*m,int*s)for(i=1;i=n;+i)mii=0;/单个矩阵无计算单个矩阵无计算 for(r=2;r=n;+r)/连乘矩阵的个数连乘矩阵的个数 for(i=1;in-r;+i)j=i+r-1;mij=mii+mi+1j+pi-1*pi*pj;sij=i;for(k=i+1;kj;+k)t=mik+mk+1j+pi-1*pk*pj;if(tmij)mij=t;sij=k;第三十五页，讲稿共六十五页哦第二种矩阵连乘的迭代

28、求解方法第二种矩阵连乘的迭代求解方法(6/10)(6/10)void Traceback(int i,int j,int*s)if(i=j)return;k=sij;Traceback(i,k,s);Traceback(k+1,j,s);printf(“A%d:%d*A%d:%d n”,i,k,k+1,j);第三十六页，讲稿共六十五页哦第二种矩阵连乘的迭代求解方法第二种矩阵连乘的迭代求解方法(7/10)(7/10)实实例分析：例分析：输入：输入：P P=,=,n n=5=5矩阵链：矩阵链：A A1 1 A A2 2 A A3 3 A A4 4 A A5 5，其中，其中 A A1:30351:3

29、035，A A2:35152:3515，A A3:1553:155，A A4:5104:510，A A5:10205:1020备忘录：备忘录：存储所有子问题的最小乘法次数及得到这个值存储所有子问题的最小乘法次数及得到这个值 的划分位置。的划分位置。第三十七页，讲稿共六十五页哦第二种矩阵连乘的迭代求解方法第二种矩阵连乘的迭代求解方法(8/10)(8/10)备备忘忘录录mi,j,P=P=m2,5=min m2,5=min 0+2500+3515200+2500+351520,2625+1000+355202625+1000+35520,4375+0+3510204375+0+351020=7125

30、7125r=1m1,1=0m2,2=0m3,3=0m4,4=0m5,5=0r=2m1,2=15750m2,3=2625m3,4=750m4,5=1000r=3m1,3=7875m2,4=4375m3,5=2500r=4m1,4=9375m2,5=7125r=5m1,5=11875第三十八页，讲稿共六十五页哦第二种矩阵连乘的迭代求解方法第二种矩阵连乘的迭代求解方法(9/10)(9/10)标记函数标记函数si,jsi,j：解的追踪：解的追踪：s s1,5=3 1,5=3 (A A1 1A A2 2A A3)(3)(A A4 4A A5)5)s s1,3=1 1,3=1 A A1(1(A A2 2A

31、 A3)3)输出输出计算顺序：计算顺序：(A A1(1(A A2 2A A3)(3)(A A4 4A A5)5)最少的乘法次数：最少的乘法次数：m m1,5=118751,5=11875r=2s1,2=1s2,3=2s3,4=3s4,5=4r=3s1,3=1s2,4=3s3,5=3r=4s1,4=3s2,5=3r=5s1,5=3第三十九页，讲稿共六十五页哦第二种矩阵连乘的迭代求解方法第二种矩阵连乘的迭代求解方法(10/10)(10/10)两种实现的比较两种实现的比较：递归实现：时间复杂性高，空间较小递归实现：时间复杂性高，空间较小迭代实现：迭代实现：时间复杂性低，空间消耗多时间复杂性低，空间消

32、耗多原因：递归实现子问题多次重复计算，子问题计算次数呈指数增原因：递归实现子问题多次重复计算，子问题计算次数呈指数增长长.迭代实现每个子问题只计算一次。迭代实现每个子问题只计算一次。动态规划时间复杂度：动态规划时间复杂度：备忘录各项计算量之和备忘录各项计算量之和 +追踪解工作量追踪解工作量通常追踪工作量不超过计算工作量通常追踪工作量不超过计算工作量 ，是问题规模的多项式函，是问题规模的多项式函数。数。第四十页，讲稿共六十五页哦3.2 3.2 动态规划算法的基本要素动态规划算法的基本要素1.1.最优子结构性质最优子结构性质 当问题的最优解包含了其子问题的最优解时，称为该问题具有最优子当问题的最优

33、解包含了其子问题的最优解时，称为该问题具有最优子结构性质。结构性质。2.2.重叠子问题性质重叠子问题性质 在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题。在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题。有些子问题被反复计算多次。有些子问题被反复计算多次。动态规划正是利用子问题的重叠性质，对每一个子问题只解一次，动态规划正是利用子问题的重叠性质，对每一个子问题只解一次，而后保留起来，下次再用只需查看结果。而后保留起来，下次再用只需查看结果。见见P54P54第四十一页，讲稿共六十五页哦例如例如：合并果子：合并果子-1-1在一个果园里，果农已经将所有的果子打了下来，而

34、且按在一个果园里，果农已经将所有的果子打了下来，而且按圆形圆形区域堆区域堆放了若干堆。最后果农要把所有的果子合并成一堆。放了若干堆。最后果农要把所有的果子合并成一堆。每一次合并，果农总是把两堆每一次合并，果农总是把两堆相邻相邻果子合并到一起，消耗的果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1n-1次次合并之后，就只剩下一堆了。果农在合并果子时总共消耗的体力等合并之后，就只剩下一堆了。果农在合并果子时总共消耗的体力等于每次合并所耗体力之和。于每次合并所耗体力之和。假定每个果子重量都为假定每个果子重量都为1 1

35、，并且已知果子堆数和每堆的数目，你的任，并且已知果子堆数和每堆的数目，你的任务是设计出合并的次序方案，使得果农耗费的体力最少，并输出这个最务是设计出合并的次序方案，使得果农耗费的体力最少，并输出这个最小的体力耗费值。小的体力耗费值。第四十二页，讲稿共六十五页哦例如例如：N=6 N=6 3 4 6 5 4 23 4 6 5 4 2一、考虑每次选相邻的最小两堆合并一、考虑每次选相邻的最小两堆合并3 3 4 6 5 4 4 6 5 4 2 2 5 55 45 4 6 5 4 6 5 4 9 99 6 9 6 5 45 4 9 99 6 9 6 9 9 15 1515 9 15 9 24 242424

36、6262第四十三页，讲稿共六十五页哦例如：例如：N=6 N=6 3 4 6 5 4 23 4 6 5 4 2二、更好方案二、更好方案3 43 4 6 5 4 2 6 5 4 2 7 77 6 7 6 5 4 2 5 4 2 13 1313 5 13 5 4 2 4 2 6 613 13 5 6 5 6 11 1113 11 13 11 24 2424246161第四十四页，讲稿共六十五页哦利用动态规划求解利用动态规划求解1 1相邻堆进行合并有多个子序列：相邻堆进行合并有多个子序列：aa1 1 a a2 2 a a2 2 a a3 3 a an n a a1 1 aa1 1 a a2 2 a a

37、3 3 a a2 2 a a3 3 a a4 4 a an n a a1 1 a a2 2 aa1 1 a a2 2.a an-1 n-1 .a.an n a a1 1.a an-2 n-2 第四十五页，讲稿共六十五页哦利用动态规划求解利用动态规划求解2 2为了便于运算，用为了便于运算，用ii，jj表示从第表示从第i i堆起堆起,顺时针的顺时针的j j堆堆组成的子序列。组成的子序列。DataijDataij=ai+ai+1+=ai+ai+1+ai+j-1+ai+j-1Fmij Fmij 表示从第表示从第i i堆起堆起,顺时针的顺时针的j j堆合并成一堆的最小值堆合并成一堆的最小值显然显然 Fm

38、i1=0;Fmi1=0;Fmij=Fmij=MINMIN Fmik+Fmi+kj-k Fmik+Fmi+kj-k +dataij+dataij k=2,3,k=2,3,j-1,j-1求求Fm1nFm1n注意下标越界问题第四十六页，讲稿共六十五页哦3.3 3.3 最长公共子序列最长公共子序列定义定义 一个给定序列的子序列是在该序列中删除若干元素后得一个给定序列的子序列是在该序列中删除若干元素后得到的序列到的序列。即。即 若给定序列若给定序列 X=x1,x2,X=x1,x2,xm,xm，则另一序，则另一序Z=z1,Z=z1,zk,zk是是X X的子序列是指的子序列是指:存在一个严格递增下标序列存在

39、一个严格递增下标序列i1,i2,i1,i2,ik,ik使得对于所有使得对于所有j=1,2,j=1,2,k,k有：有：Z Zj j=X=Xijij例如例如 序列序列 X=AX=A，B B，C C，B B，D D，A A，BB 子序列子序列 Z=BZ=B，C C，D D，BB 相应的递增下标序列为相应的递增下标序列为22，3 3，5 5，77。第四十七页，讲稿共六十五页哦公共子序列公共子序列 给定给定2 2个序列个序列 X X 和和 Y Y，当另一序列，当另一序列 Z Z 既是既是X X的子序列又是的子序列又是Y Y的子序列时，称的子序列时，称Z Z是序列是序列X X和和Y Y的公共子序列。的公共

40、子序列。最长公共子序列问题最长公共子序列问题 给定给定2 2个序列个序列 X=x1,x2,X=x1,x2,xm,xm和和 Y=y1,y2,Y=y1,y2,yn,yn，找，找出出 X X 和和 Y Y 的最长公共子序列。的最长公共子序列。例如：字符串例如：字符串1313455455和和2 24554557676的最长公共子序列为的最长公共子序列为455455 字符串字符串a ac cdfdfg g和和adfadfc c的最长公共子序列为的最长公共子序列为adfadf 第四十八页，讲稿共六十五页哦LCSLCS（Longest Common SubsequenceLongest Common Sub

41、sequence）的应用）的应用求两个序列中最长的公共子序列算法，广泛的应用在图形相似出路、媒体流的相似比求两个序列中最长的公共子序列算法，广泛的应用在图形相似出路、媒体流的相似比较、计算生物学方面。生物学家常常利用该算法进行基因序列比对，由此推测序列的较、计算生物学方面。生物学家常常利用该算法进行基因序列比对，由此推测序列的结构、功能和演化过程。结构、功能和演化过程。LCSLCS可以描述两段文字之间的可以描述两段文字之间的“相似度相似度”，即它们的雷同程度，从而能够用来辨别抄袭。，即它们的雷同程度，从而能够用来辨别抄袭。另一方面，对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除

42、此另一方面，对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道，百度百科都用得上。度知道，百度百科都用得上。第四十九页，讲稿共六十五页哦求最长公共子序列问题，最容易想到的算法求最长公共子序列问题，最容易想到的算法-枚举法枚举法即，对即，对X X的所有子序列，检查它是否也是的所有子序列，检查它是否也是Y Y的子序列，从中找出最的子序列，从中找出最长的子序列。长的子序列。但但 X X 共有共有2 2M M个不同的子序列。枚举法个不同

43、的子序列。枚举法 O(2m)事实上事实上，最长公共子序列问题，具有最优子结构性质。最长公共子序列问题，具有最优子结构性质。最长最长公共子序列的结构公共子序列的结构第五十页，讲稿共六十五页哦最优子结构性质。最优子结构性质。设序列设序列X Xm m=x=x1 1,x,x2 2,x,xm m 和和Y Yn n=y=y1 1,y,y2 2,y,yn n 的最长公共的最长公共子序列为子序列为Z Zk k=z=z1 1,z,z2 2,z,zk k ，则，则 l若若x xm m=y=yn n 则则 z zk k=x=xm m=y=yn n 且且 Z Zk-1k-1是是X Xm-1m-1和和 Y Yn-1n-

44、1的最长公共子序列。的最长公共子序列。l若若x xm myyn n 且且 z zk kxxm m 则则 Z Z是是X Xm-1m-1和和 Y Y 的最长公共子序列的最长公共子序列l若若x xm myyn n 且且 z zk kyyn n 则则 Z Z是是X Xm m和和 Y Yn-1n-1 的最长公共子序列的最长公共子序列 由此可见，由此可见，2 2个序列的最长公共子序列包含了这个序列的最长公共子序列包含了这2 2个序列的前缀的最个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质长公共子序列。因此，最长公共子序列问题具有最优子结构性质。第五十一页，讲稿共六十五页哦子问题的

45、递归结构子问题的递归结构 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。系。cij:记录序列记录序列 X Xi i和和Y Yj j的最长公共子序列的长度。其中，的最长公共子序列的长度。其中，X Xi i=x=x1 1,x,x2 2,x,xi i Y Yj j=y=y1 1,y,y2 2,y,yj j 由最优子结构性质可建立递归关系如下由最优子结构性质可建立递归关系如下：第五十二页，讲稿共六十五页哦计算最优值计算最优值 由于在所考虑的子问题空间中，总共有由于在所考虑的子问题空间中，总共有(mn)(mn)个不同的子问题，

46、因此，用动态规划个不同的子问题，因此，用动态规划算法自底向上的计算最优值能提高算法的效率算法自底向上的计算最优值能提高算法的效率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=“”;else cij=cij-1;bij=“”;O(mn)第五十三页，讲稿共六十五页哦构造最长公共子序列构造最长公共子序列能提高算法的效率。算法描述：void LCS(int

47、 i，int j，char*x，int*b)if(i=0|j=0)return;if (bij=“”)LCS(i-1，j-1，x，b);coutxi;else if(bij=“”)LCS(i-1，j，x，b);else LCS(i，j-1，x，b);O(m+n)第五十四页，讲稿共六十五页哦结果结果能提高算法的效率。算法描述：第五十五页，讲稿共六十五页哦算法的改进算法的改进能提高算法的效率。算法描述：在算法在算法LCSLengthLCSLength和和LCSLCS中，可进一步将数组中，可进一步将数组b b省去。省去。事实上，数组元素事实上，数组元素cijcij的值仅由的值仅由ci-1j-1ci-

48、1j-1，ci-1jci-1j和和cij-1cij-1这这3 3个数组元素的值所确定。个数组元素的值所确定。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算减少。事实上，在计算cijcij时，只用到数组时，只用到数组c c的第的第i i行和第行和第i-1i-1行。行。因此，用因此，用2 2行的数组空间就可以计算出最长公共子序列的长度。进行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至一步的分析还可将空间需求减至O(min(m,n)(min(m,n)。第五十六页，讲稿共六十五页哦Q

49、uestion?题目：题目：给定一个长度为给定一个长度为N N的数组，找出一个的数组，找出一个最长的单调递增子序列。例如：给定数组最长的单调递增子序列。例如：给定数组5 5，6 6，7 7，1 1，2 2，8 8则其最长的单调递增自则其最长的单调递增自序列为序列为5 5，6 6，7 7，8 8，长度为，长度为4 4。求解：求解：怎么用怎么用LCSLCS解决这个问题？解决这个问题？分析：分析：原数组原数组=5 5，6 6，7 7，1 1，2 2，8 8 排序后排序后=1 1，2 2，5 5，6 6，7 7，8 857第五十七页，讲稿共六十五页哦3.4 3.4 最大子段和最大子段和 给定由给定由N

50、 N个整数（个整数（可能有负整数可能有负整数）组成的序列）组成的序列a a1 1,a,a2 2,a,an n,求该序列求该序列形如形如 a ai i+a+ai+1i+1+a+aj j的子段和的最大值。的子段和的最大值。当所有整数均为负整数时，定义其最大子段和为当所有整数均为负整数时，定义其最大子段和为0 0例如例如：当当aa1 1,a,a2 2,a,a6 6=-1=-1，1111，-4-4，1313，-5-5，-2-2时时其最大子段和为其最大子段和为 2020第五十八页，讲稿共六十五页哦算法算法算法算法1 1：对所有的对所有的(i,j)(i,j)对，顺序求和对，顺序求和a ai i+.+.+a