第3章-动态规划v11

1、第三章第三章 动态规划动态规划 ZZU郑州大学郑州大学 ZZU算法设计与分析算法设计与分析第三章第三章 动态规划动态规划 ZZU 学习要点学习要点 理解动态规划算法的概念。理解动态规划算法的概念。 掌握动态规划算法的基本要素掌握动态规划算法的基本要素 （1）最优子结构性质）最优子结构性质 （2）重叠子问题性质）重叠子问题性质 掌握设计动态规划算法的步骤。掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。递归地定义最优值。 (3)以自底向上的方式计算出最优值。以自底向上的方式计算出最优值。 (4)根据计算最优值时

2、得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。算法设计与分析算法设计与分析2第三章第三章 动态规划动态规划 ZZU通过应用范例学习动态规划算法设计通过应用范例学习动态规划算法设计策略策略 （1）矩阵连乘问题；）矩阵连乘问题； （2）最长公共子序列；）最长公共子序列； （3）最大子段和）最大子段和; （4）凸多边形最优三角剖分；）凸多边形最优三角剖分； （5）多边形游戏；）多边形游戏； （6）图像压缩；）图像压缩； （7）电路布线；）电路布线； （8）流水作业调度；）流水作业调度； （9）背包问题；）背包问题； （10）最优二叉搜索树。）最优二叉搜索树。算法设计与分析算法设计与

3、分析3第三章第三章 动态规划动态规划 ZZU4 2020世纪世纪5050年代初美国数学家年代初美国数学家R.E.BellmanR.E.Bellman等人在研等人在研究多阶段决策过程究多阶段决策过程(multistep decision process)(multistep decision process)的的优化问题时，提出了著名的最优化原理优化问题时，提出了著名的最优化原理(principle of (principle of optimality)optimality)，把多阶段过程转化为一系列单阶段问题，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法，

4、逐个求解，创立了解决这类过程优化问题的新方法动态规划。动态规划。19571957年出版了年出版了Dynamic ProgrammingDynamic Programming，这是该领域的第一本著作。这是该领域的第一本著作。第三章第三章 动态规划动态规划 ZZU5回顾：分治法可解问题的特点回顾：分治法可解问题的特点问题的规模缩小到一定的程度可容易地解决；问题的规模缩小到一定的程度可容易地解决；该问题可分解为若干规模较小的相同问题该问题可分解为若干规模较小的相同问题; ;分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分解出的各个子问

5、题是相互独立的。 第三章第三章 动态规划动态规划 ZZUn动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=算法设计与分析算法设计与分析6第三章第三章 动态规划动态规划 ZZUn但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。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)T(n/4)

6、T(n/4)算法设计与分析算法设计与分析7第三章第三章 动态规划动态规划 ZZUn如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。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)算法设计与分析算法设计与分析8第三章第三章 动态规划动态规划 ZZUn=5时分治法计算斐波那契数的过程。 F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例：计算斐

7、波那契数：2)2() 1(1100)(nnFnFnnnF算法设计与分析算法设计与分析9第三章第三章 动态规划动态规划 ZZU01234567890112358132134动态规划法求解斐波那契数F(9)的填表过程 ： 注意到，计算F(n)是以计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。 算法设计与分析算法设计与分析10第三章第三章 动态规划动态规划 ZZU动态规划基本步骤动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。算法设计与

8、分析算法设计与分析11其中13为基本步骤。动态规划算法常用于求解具有某种最优性质的问题.可能有许多可行解, 希望找到具有最优值的那个解.第三章第三章 动态规划动态规划 ZZU算法设计与分析算法设计与分析12第三章第三章 动态规划动态规划 ZZU矩阵矩阵 由由m X n个数个数aij（i=1,2m;j=1,2,n）排列成）排列成m行行n列的数表列的数表 a11 a12 a1n a21 a22 a2n . . am1 am2 amnA= 叫做m行n列的矩阵算法设计与分析算法设计与分析13第三章第三章 动态规划动态规划 ZZU矩阵的乘矩阵的乘矩阵相乘只有在第一个矩阵的列数和第二个矩阵的矩阵相乘只有在

9、第一个矩阵的列数和第二个矩阵的行数行数相同相同时时才有才有定义定义。假如假如A 为为mn 矩阵矩阵，B为为np 矩阵矩阵，则则AB (有时有时记做记做A B)会是一个会是一个mp 矩阵。矩阵。算法设计与分析算法设计与分析14第三章第三章 动态规划动态规划 ZZU例子例子 1 0 2 3 1 -1 3 1 2 1 1 0 5 1 4 2例如例如一个一个2x3的矩阵的矩阵 与一个与一个 3x2的矩阵的乘会是一的矩阵的乘会是一个个2x2的矩阵的矩阵 。x=算法设计与分析算法设计与分析15第三章第三章 动态规划动态规划 ZZU矩阵的连乘矩阵的连乘 设有设有矩阵矩阵M1,M2,M3,M4，其，其维数分别

10、是维数分别是1020, 2050, 501 和和1100，现，现要求出这要求出这4个矩阵相个矩阵相乘的结果乘的结果。 我们我们知道，若矩阵知道，若矩阵A的维数是的维数是pq，矩阵，矩阵B的维数是的维数是qr，则，则A与与B相乘后所得矩阵相乘后所得矩阵AB的维数是的维数是pr。按照矩阵相乘的定义按照矩阵相乘的定义，求求出矩阵出矩阵AB中的一个元素需要中的一个元素需要做做q次乘法（及次乘法（及q-1次加法）次加法）。 这样这样，要计算出，要计算出AB就需要做就需要做pqr次乘法次乘法。 为为简单起见，且由于加法比同样数量的乘法所用时间简单起见，且由于加法比同样数量的乘法所用时间要少得多要少得多，故

11、，故这里我们暂这里我们暂不考虑加法的计算量不考虑加法的计算量。 由于由于矩阵连乘满足结合律，故计算矩阵连乘的方式可矩阵连乘满足结合律，故计算矩阵连乘的方式可以有多种。以有多种。 算法设计与分析算法设计与分析16第三章第三章 动态规划动态规划 ZZUu看一个例子，计算三个矩阵连乘A1，A2，A3；u维数分别为10*100 , 100*5 , 5*50 u按此顺序计算需要的次数u（A1*A2）*A3）:10*100*5+10*5*50= 7500次 u按此顺序计算需要的次数u（A1*（A2*A3）:10*5*50+10*100*50= 75000次 算法设计与分析算法设计与分析17第三章第三章 动

12、态规划动态规划 ZZUDCBA , , ,1050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB16000, 10500, 36000, 87500, 34500u设有四个矩阵 ，它们的维数分别是：u总共有五种完全加括号的方式乘法次数算法设计与分析算法设计与分析18u所以问题是：如何确定运算顺序，可以使计算量达到最小化。 枚举显然不可，如果枚举的话，相当于一个“完全加括号问题”，复杂度为指数增长，故不可行。 第三章第三章 动态规划动态规划 ZZU矩阵连矩阵连乘问题的子问题分析乘问题的子问题分析算法设计与分析算法设计与分析19 单个矩阵单个矩阵 A，2

13、个矩阵个矩阵 AB 3个矩阵的情况个矩阵的情况 ABC A(BC),(AB)C 4个矩阵的情况个矩阵的情况 ABCD,假设假设3个矩阵的情况已经计算了个矩阵的情况已经计算了 ABCD, ABCD, ABCD 5个矩阵的情况个矩阵的情况 ABCDE，假设，假设4个矩阵的情况已经计算了个矩阵的情况已经计算了 ABCDE, ABCDE, ABCDE, ABCDE N个矩阵，假设个矩阵，假设N-1个矩阵的情况已经计算了个矩阵的情况已经计算了 A1A2AkAk+1AN, 1=kN第三章第三章 动态规划动态规划 ZZU矩阵连乘问题的最优子结构证明矩阵连乘问题的最优子结构证明算法设计与分析算法设计与分析20

14、 原问题的最优解包含了其子问题的最优解原问题的最优解包含了其子问题的最优解 即如果即如果A1A2AN的最优连乘方案的最优连乘方案是是A1AkAk+1AN，那么，那么由此确定由此确定的子矩阵链的子矩阵链A1Ak和和Ak+1AN的连乘方案分别也是最的连乘方案分别也是最优的。优的。 证明：证明：(反证法反证法) 假设原问题最优次序确定的子矩阵链A1Ak有一个计算量更少的计算次序，则用此计算次序代替原来计算A1Ak的次序，得到的A1A2AN原问题的计算量将比最优次序所需的计算量更少，与假设产生矛盾。因此， A1A2AN原问题的最优次序包含了子问题A1Ak的最优次序。 同理可知A1A2AN原问题的最优次

15、序包含了子矩阵链Ak+1AN的最优次序。第三章第三章 动态规划动态规划 ZZUn给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。n若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,.,21nAAAiA1iA1,.,2 , 1ninAAA.21算法设计与分析算法设计与分析21第三章第三章 动态规划动态规划 ZZU给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确

16、定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。u穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 算法复杂度分析：算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：13/2111( )( )( ) ()1(4 /)knnnP nP nP k P nknn算法设计与分析算法设计与分析22第三章第三章 动态规划动态规划 ZZUu穷举法穷举法u动态规划动态规划将矩阵连乘

17、积 简记为Ai:j ，这里ij jiiAAA.1考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为112(.)(.)iikkkjA AAAAA计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量算法设计与分析算法设计与分析231(.)iikA AA12(.)kkjAAA第三章第三章 动态规划动态规划 ZZUn特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。n矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优最优子结构性质子结构性质。

18、问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。算法设计与分析算法设计与分析24第三章第三章 动态规划动态规划 ZZUn设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n n当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,nn当ij时，如果是从k处断开的话，n可以递归地定义mi,j为：jkipppjkmkimjim1, 1,这里 的维数为 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 种可能kij 算法设计与分析算法设计与分析25第三章第三章 动态规划动态规划 ZZUn对于1ijn不同的有序对

19、(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有n由此可见，在递归计算时，许多子问题被重复计算多许多子问题被重复计算多次次。这也是该问题可用动态规划算法求解的又一显著特征。n用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法)(22nnn算法设计与分析算法设计与分析26二维数组二维数组mi,j第三章第三章 动态规划动态规划 ZZU二维数组二维数组m的计算次序问题的计算次序问题算法设计与分析算法设计与分析276 5 4 3 2 165

20、4321ij第三章第三章 动态规划动态规划 ZZUvoid MatrixChain(int *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+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

21、 = 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 = u; return u;算法设计与分析算法设计与分析33共有共有O O（n n2 2）记录，）记录，每个计算每个计算O(nO(n),), 复杂度复杂度O(nO(n3 3) )，与动态规划不同：只

22、求必须计算的子问题，而动与动态规划不同：只求必须计算的子问题，而动态规划全部求解。态规划全部求解。第三章第三章 动态规划动态规划 ZZU34小结：小结： 动态规划算法动态规划算法的基本思想的基本思想将原问题将原问题分解为若干个子问题分解为若干个子问题，先求子问题先求子问题的解，的解，然后从这些子问题的解然后从这些子问题的解得到原问题得到原问题的解。的解。这些子问题的解往往这些子问题的解往往不是相互独立的不是相互独立的。在求解的过。在求解的过程中，许多子问题的解被反复地使用。为了避免重程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了复计算，动态规划算法采用了填表填表来保存子

23、问题的来保存子问题的解。解。在算法中用表格来保存已经求解的子问题的解，无在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查论它是否会被用到。当以后遇到该子问题时即可查表取出其解，表取出其解，避免了重复计算避免了重复计算。第三章第三章 动态规划动态规划 ZZU35对动态规划算法对动态规划算法的基本的基本要素如何理解？要素如何理解？最优子结构性质最优子结构性质：问题的最优解是由其子问题的：问题的最优解是由其子问题的最优解所构成的。最优解所构成的。最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问题重叠，所以存在着重复计算

24、。这样就可以用填表保存子问题解的方法来提高效率。 子问题重叠子问题重叠：子问题之间并非相互独立的，：子问题之间并非相互独立的，而是彼此有重叠的。而是彼此有重叠的。第三章第三章 动态规划动态规划 ZZU36动态规划算法的基本方法动态规划算法的基本方法动态规划算法通常可以按以下几个步骤进行：动态规划算法通常可以按以下几个步骤进行：(1)(1)找出最优解的性质，并刻画其结构特征；找出最优解的性质，并刻画其结构特征；(2)(2)递归地定义最优值；递归地定义最优值；(3)(3)以自底向上的方式计算出各子结构的最优值并添入以自底向上的方式计算出各子结构的最优值并添入表格中保存；表格中保存；(4)(4)根据

25、计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。若需要最优解，则必须执行第若需要最优解，则必须执行第4 4步，为此还需要在第步，为此还需要在第3 3步中记录构造最优解所必需的信息。步中记录构造最优解所必需的信息。第三章第三章 动态规划动态规划 ZZU动态规划算法的无后效动态规划算法的无后效性性即某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。算法设计与分析算法设计与分析376 5 4 3 2 1654321ij第三章第三章 动态规划

26、动态规划 ZZU算法模式图算法模式图当前阶段i多个规划规划(决策)当前最优决策当前非最优决策i向着目标阶段不断改变(动态动态)规划方向目标阶段初始阶段求得的一个最优解求得的一个最优解当前阶段的决策仅受前一阶段决策的影响,并决定下一个阶段的决策动态规划动态规划算法设计与分析算法设计与分析38第三章第三章 动态规划动态规划 ZZU动态规划和一般递推的相同点？无后效性和有边界条件。动态规划和一般递推的不同点？动态规划和一般递推的不同点？ 1、递推的边界条件一般很明显，而动态规划的边界条件比较、递推的边界条件一般很明显，而动态规划的边界条件比较隐蔽，容易被忽视；隐蔽，容易被忽视； 2、递推的数学性一般

27、较强，而动态规划的数学性相对较弱；、递推的数学性一般较强，而动态规划的数学性相对较弱； 3、递推一般不划分阶段，而动态规划一般有较为明显的阶段；、递推一般不划分阶段，而动态规划一般有较为明显的阶段； 4、动态规划往往是用来求一个最优值，而一般的递推往往是、动态规划往往是用来求一个最优值，而一般的递推往往是用来计数或是求一个值。用来计数或是求一个值。 算法设计与分析算法设计与分析39第三章第三章 动态规划动态规划 ZZU矩阵连矩阵连乘问题的子问题分析乘问题的子问题分析算法设计与分析算法设计与分析40 单个矩阵单个矩阵 A，2个矩阵个矩阵 AB 3个矩阵的情况个矩阵的情况 ABC，假设，假设2个矩

28、阵的情况已经计算了个矩阵的情况已经计算了 A(BC),(AB)C 4个矩阵的情况个矩阵的情况 ABCD,假设假设3个以下矩阵的情况已经计算了个以下矩阵的情况已经计算了 ABCD, ABCD, ABCD 5个矩阵的情况个矩阵的情况 ABCDE，假设，假设4个以下矩阵情况已经计算了个以下矩阵情况已经计算了 ABCDE, ABCDE, ABCDE, ABCDE N个矩阵，假设个矩阵，假设N-1个及以下矩阵的情况已经计算了个及以下矩阵的情况已经计算了 A1A2AkAk+1AN, 1=kNNN第三章第三章 动态规划动态规划 ZZU矩阵连乘问题的最优子结构证明矩阵连乘问题的最优子结构证明算法设计与分析算法

29、设计与分析41 原问题的最优解包含了其子问题的最优解原问题的最优解包含了其子问题的最优解 即如果即如果A1A2AN的最优连乘方案的最优连乘方案是是A1AkAk+1AN，那么，那么由此确定由此确定的子矩阵链的子矩阵链A1Ak和和Ak+1AN的连乘方案分别也是最的连乘方案分别也是最优的。优的。 证明：证明：(反证法反证法) 假设原问题最优次序确定的子矩阵链A1Ak有一个计算量更少的计算次序，则用此计算次序代替原来计算A1Ak的次序，得到的A1A2AN原问题的计算量将比最优次序所需的计算量更少，与假设产生矛盾。因此， A1A2AN原问题的最优次序包含了子问题A1Ak的最优次序。 同理可知A1A2AN

30、原问题的最优次序包含了子矩阵链Ak+1AN的最优次序。第三章第三章 动态规划动态规划 ZZU矩阵连乘的重叠子问题矩阵连乘的重叠子问题4个矩阵连乘问题的重叠子问题计算个矩阵连乘问题的重叠子问题计算第三章第三章 动态规划动态规划 ZZU43最最长公共子序列长公共子序列 若给定序列若给定序列X=xX=x1 1,x,x2 2, ,x,xm m ，则另一序，则另一序列列Z=zZ=z1 1,z,z2 2, ,z,zk k 是是X X的的子序列子序列是指存在一是指存在一个严格递增下标序列个严格递增下标序列ii1 1,i,i2 2, ,i,ik k 使得对于使得对于所有所有j=1,2,j=1,2,k,k有：有

31、：z zj j=x=xi ij j。例如，序列例如，序列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。第三章第三章 动态规划动态规划 ZZU44 给定给定2 2个序列个序列X X和和Y Y，当另一序列，当另一序列Z Z既是既是X X的子的子序列又是序列又是Y Y的子序列时，称的子序列时，称Z Z是序列是序列X X和和Y Y的的公共公共子序列子序列。最长公共子序列最长公共子序列：例，例，序列序列 X=A X=A，B B，C C，B B，D D，A A，BB， Y

32、=B Y=B，D D，C C，A A，B B，A A 的子序列的子序列 B B，C C，AA是是X X与与Y Y的公共子序列，但不是最长公共的公共子序列，但不是最长公共子序列；子序列； B B，C C，B B，AA也是也是X X与与Y Y的公共子序列，它是的公共子序列，它是X X与与Y Y的最长公共子序列，因为的最长公共子序列，因为X X与与Y Y没有长度大于没有长度大于4 4的公共的公共子序列子序列。应用场合：论文相似度检测、用户模型挖掘应用场合：论文相似度检测、用户模型挖掘第三章第三章 动态规划动态规划 ZZU最长公共子序列在最长公共子序列在DNA序列比对中的应用序列比对中的应用 In b

33、iological applications, we often want to compare the DNA(脱氧核糖核酸) of two (or more) different organisms. A strand of DNA consists of a string of molecules called bases(碱基序列), where the possible bases are adenine, guanine, cytosine, and thymine (A, G, C, T).四种不同碱基： A 腺嘌呤 G 鸟嘌呤 C 胞嘧啶 T 胸腺嘧啶 Comparison o

34、f two DNA stringsS1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAAS2 = GTCGTTCGGAATGCCGTTGCTCTGTAAAS3 = GTCGTCGGAAGCCGCCGAA Comparison of two DNA stringsS1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAAS2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA第三章第三章 动态规划动态规划 ZZU46最长公共子序列的最长公共子序列的问题问题 给定给定2 2个序列个序列X=xX=x1 1,x,x2 2, ,x,xm m 和和 Y=yY=y1 1,

35、, y y2 2, ,y,yn n ，找出，找出X X和和Y Y的最长公共子序列。的最长公共子序列。u解法一：穷举法，列举出解法一：穷举法，列举出X X所有可能的子序列，并所有可能的子序列，并检查它是否也是检查它是否也是Y Y的子序列，从而确定它是否为公共的子序列，从而确定它是否为公共子序列，在此过程中记录最长的公共子序列子序列，在此过程中记录最长的公共子序列 。 算法复杂度分析：算法复杂度分析： 从从X X中任意取中任意取l l个元素构成子序列，共有个元素构成子序列，共有2 2m m种不种不同子集。同子集。 解法二：解法二：尝试用动态规划求解。尝试用动态规划求解。第三章第三章 动态规划动态规

36、划 ZZU设序列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个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结最优子结构性质构性质。 算法设计与分析算法设计与分析47x1,x2,xm-1,xmy1,y2, ,yn-1,yn设Xi=x1,x2,xi； Yj=y1,y2,yj第三章第三

37、章 动态规划动态规划 ZZU由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列Xi和Yj的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110i-1,j-1i-1,ji,j-1i,j算法设计与分析算法设计与分析48Xi和Yj-1的最长公共子序列Xi-1和Yj的最长公共子序列Xi-1和Yj-1的最长公共子序列第三章第三章 动

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

39、公共子序列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);i-1,j-1i-1,ji,j-1i,j 算法设计与分析算法设计与分析49直接利用递归式的算法是指数时间的，直接利用递归式的算法是指数时间的，213b的方向jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110第三章第三章 动态规划动态规划

40、ZZU50(a) 长度矩阵长度矩阵c (b) 状态矩阵状态矩阵b0 1 2 3 4 5 6 7 8 90 1 23 4 5 6 7 8 90 0 0 0 0 0 0 0 0 0 00 0 0 00 0 0 0 0 0 01 0 1 1 1 1 1 1 1 1 11 0 1 33 3 1 3 3 3 32 0 12 0 23 0 13 0 24 0 14 0 25 0 15 0 26 0 16 0 2 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 例例 序列序列X=(a, b, c, b, d, b)X=(a, b, c, b, d, b)， Y=(a, c, b, b

41、, a, b, d, b, b) Y=(a, c, b, b, a, b, d, b, b)， 建立两个建立两个(m+1)(m+1)(n+1)(n+1)的二维表分别存放搜索过程中得到的子序列的长度和的二维表分别存放搜索过程中得到的子序列的长度和状态。状态。 imj njijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110213b的方向第三章第三章 动态规划动态规划 ZZU51(a) 长度矩阵长度矩阵c (b) 状态矩阵状态矩阵b0 1 2 3 4 5 6 7 8 90 1 23 4 5 6 7 8 90 0 0 0 0 0 0 0 0 0 00 0

42、0 00 0 0 0 0 0 01 0 1 1 1 1 1 1 1 1 11 0 1 33 3 1 3 3 3 32 0 1 1 2 2 2 2 2 2 22 0 2 21 1 3 1 3 1 13 0 1 2 2 2 2 2 2 2 23 0 2 12 2 2 2 2 2 24 0 1 2 3 3 3 3 3 3 34 0 2 21 1 3 1 3 1 15 0 1 2 3 3 3 3 4 4 45 0 2 22 2 2 2 1 3 36 0 1 2 3 4 4 4 4 5 56 0 2 21 1 3 1 2 1 1例例 ：序列序列X=(X=(a a, , b b, c, , c, b b,

43、 , d d, , b b) )， Y=( Y=(a a, c, b, , c, b, b b, a, , a, b b, , d d, b, , b, b b) )， 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 建立两个建立两个(m+1)(m+1)(n+1)(n+1)的二维表分别存放搜索过程中得到的子序列的长度和的二维表分别存放搜索过程中得到的子序列的长度和状态。状态。 imj n213b的方向第三章第三章 动态规划动态规划 ZZU The sequences are X= and Y= Compute ci,j row by row for i=1.m, j=1

44、.n. Time=(mn) Reconstruct LCS by tracing backwards.Space = (mn).j0123456iyiB D CABA0 xi1A2B3C4B5D6A7B00 000000000000443221433221332221332211222211221111111000LCS计算最优解例子计算最优解例子第三章第三章 动态规划动态规划 ZZU53教材上算法的代码如何用完整的程序实现？教材上算法的代码如何用完整的程序实现？#include #include #include #includeofstream out(output.txt);ifstre

45、am in(input.txt, ios:in); int *c,*b;void LCSLength(int m, int n, char * x, char * y, int *c, int *b)void LCS(int i, int j, char *x, int *b)C标准输入和输出文件流实用函数库，例如malloc,qsortC+输入和输出重定向输出到文件重定向输入到文件声明两个二维数组动态规划法计算最长公共子序列构造并输出最长公共子序列第三章第三章 动态规划动态规划 ZZU54int main() int i, j, m, n; char *x, *y; if (!in) cer

46、rmn; /从文件中读入从文件中读入x与与y的长度的长度x=new charm; /x字符串字符串y=new charn; /y字符串字符串int *c=new int *m; /定义定义c数组数组for (i=0;i=m; i+) ci=new intn; int *b=new int *m; /定义定义b数组数组for (i=0;i=m; i+) bi=new intn; for(i=1;ixi; /从文件中读入从文件中读入x字符字符 for(j=1;jyj; /从文件中读入从文件中读入y字符串字符串LCSLength(m,n,x,y,c,b);LCS(m,n,x,b);in.close(

47、); out.close(); return 0; /mainjijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110213b第三章第三章 动态规划动态规划 ZZU在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在常数时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到

48、数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110i-1,j-1i-1,ji,j-1i,j算法设计与分析算法设计与分析55第三章第三章 动态规划动态规划 ZZU56最大最大子段和子段和 问题描述：问题描述：给定由给定由n n个整数（包含负整数）组成的序列个整数（包含负整数）组成的序列a a1 1,a,a2 2,.,a,.,an n，求该序列子段和的最大值。当所有整数均为负值时定义其求该序列子段和的最大值。当所有整

49、数均为负值时定义其最大子段和为最大子段和为0 0。依此定义，所求的最优值为：依此定义，所求的最优值为： 例如，当例如，当(a(a1 1,a,a2 2 , a, a3 3 , a, a4 4 , a, a5 5 ,a,a6 6)=(-2,11,-4,13,-5,-2)=(-2,11,-4,13,-5,-2)时，时，最大子段和为：最大子段和为： jikknjia1max,0max201341142kka第三章第三章 动态规划动态规划 ZZU57int MaxSum(int n, a, &besti, &bestj) /besti, bestj 元素编号；元素编号； int sum=0;for(i=

50、1;i=n;i+)for(j=i;j=n;j+)int thissum=0;for(k=i;ksum)sum=thissum;besti=i;Bestj=k; return sum;算法有算法有3重循环，复杂性为重循环，复杂性为O(n3)。一个一个简单枚举算法：简单枚举算法：a a1 1,a,a2 2,a,ai i a ak k a aj ja an n第三章第三章 动态规划动态规划 ZZU58算法可作如下改进：算法可作如下改进：int MaxSum(int n, a, &besti, &bestj)int sum=0; 由于有：由于有：for(i=1;i=n;i+)int thissum=0

51、;for(j=i;jsum)sum=thissum;besti=i;bestj=j; / if /for/for /MaxSum 改进后的算法复杂性为改进后的算法复杂性为O(n2) 。jjikkjikkaaa1第三章第三章 动态规划动态规划 ZZU59用用分治法求解分治法求解从问题的解的结构可以看出，它适合于用分治策略求解：从问题的解的结构可以看出，它适合于用分治策略求解：如果将所给的序列如果将所给的序列a1:na1:n分为长度相等的两段分为长度相等的两段a1:n/2a1:n/2和和an/2+1:nan/2+1:n，分别求出这两段的最大子段和，则，分别求出这两段的最大子段和，则a1:na1:n

52、的最大子段和有三种情形：的最大子段和有三种情形：A.A. a1:na1:n的最大子段和与的最大子段和与a1:n/2a1:n/2的最大子段的最大子段和相同；和相同；B.B. a1:na1:n的最大子段和与的最大子段和与an/2+1:nan/2+1:n的最大子的最大子段和相同；段和相同；A A、B B这两种情形可递归求得。这两种情形可递归求得。a a1 1,a,a2 2,a,an/2n/2| | a an/2+1n/2+1 a an n第三章第三章 动态规划动态规划 ZZU60C. a1:nC. a1:n的最大子段和为下面形式。的最大子段和为下面形式。情形情形C C，an/2an/2与与an/2+

53、1an/2+1在最优子序列中。因此，在最优子序列中。因此，我们可以在我们可以在a1:n/2a1:n/2和和an/2+1:nan/2+1:n中分别计算出中分别计算出s1s1和和s2s2。则。则s1+s2s1+s2即为最优值即为最优值。从而设计出下面所示的分治算法从而设计出下面所示的分治算法 。njnniajikk1221,212122211nikjnkknjnkniasasmax,maxa a1 1,a,a2 2,a,an/2n/2| | a an/2+1n/2+1 a an n第三章第三章 动态规划动态规划 ZZU61int MaxSubSum(int int MaxSubSum(int *

54、*a, int left, int right)a, int left, int right) int sum=0; int sum=0; if (left=right) if (left=right) sum=aleft0? aleft:0; sum=aleft0? aleft:0; elseelse int center=(left+right)/2; int center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int leftsum=MaxSubSum(a,left,center); int rightsum=MaxS

55、ubSum int rightsum=MaxSubSum (a,center+1,right); (a,center+1,right); int s1=0; lefts=0; int s1=0; lefts=0; 第三章第三章 动态规划动态规划 ZZU62forfor (int i=center;i=left;i-) (int i=center;i=left;i-) lefts+=ai; lefts+=ai; if (leftss1) s1=lefts; if (leftss1) s1=lefts; /for/forint s2=0;rights=0;int s2=0;rights=0;for

56、 for (int i=center+1;i=right;i+) (int i=center+1;is2) if (rightss2) s2=rights; s2=rights; /for/forsum=s1+s2;sum=s1+s2;if (sumleftsum) sum=leftsum;if (sumleftsum) sum=leftsum;if (sumsightsum)if (sum00时时 b bj j=b=bj-1j-1+a+aj j，否则，否则b bj j=a=aj j。 由此可得计算由此可得计算bjbj的的动态规划递归式动态规划递归式： b bj j=maxb=maxbj-1j

57、-1+a+aj j，a aj j ，1jn1jn。11111max1maxmaxmaxmaxjjkijk ijjjjkkij nj njnik ik ibabjnaa 记，则最大子段和记为a1, a2, ai, aj, an bja1, a2, ai,aj-1, aj, an bj-1第三章第三章 动态规划动态规划 ZZU65 据此，可设计出动态规划算法如下：据此，可设计出动态规划算法如下：int MaxSum(int n, int a)int MaxSum(int n, int a) int sum=0; b=0;int sum=0; b=0;for (i=1;i=n;i+)for (i=1

58、;i0) b+=ai; if (b0) b+=ai; else b=ai;else b=ai;if (bsum) sum=b;if (bsum) sum=b; return sum;return sum; 显然该算法的计算时间为显然该算法的计算时间为O O(n)(n)。bj=maxbj-1+aj，aj，1jn。第三章第三章 动态规划动态规划 ZZU66算法算法的推广的推广最大子矩阵最大子矩阵和问题，和问题，略略最大最大m m子段和问题，子段和问题，略略第三章第三章 动态规划动态规划 ZZUu凸多边形凸多边形当一个简单多边形当一个简单多边形(边除了顶点不相交边除了顶点不相交)及其内部及其内部构成

59、闭凸集时，该多边形为一凸多边形。构成闭凸集时，该多边形为一凸多边形。u用多边形顶点的逆时针序列表示凸多边形，即用多边形顶点的逆时针序列表示凸多边形，即P=vP=v0 0,v,v1 1, ,v,vn-1n-1 表示具有表示具有n n条边条边v v0 0v v1 1, v, v1 1v v2 2, ,v,vn-1n-1v vn n的凸多边形。的凸多边形。约定约定v v0 0=v=vn n内部内部外部外部v v0 0v v1 1v v2 2v v3 3v v4 4(v(vn n) )第三章第三章 动态规划动态规划 ZZU若若v vi i与与v vj j是不相邻的是不相邻的2 2个顶点，则线段个顶点，

60、则线段v vi iv vj j称为弦。弦称为弦。弦将凸多边形将凸多边形分割成分割成2 2个凸多边形个凸多边形vvi i,v,vi+1i+1,v,vj j(2)(2)和和vvj j,v,vj+1j+1,v,vi i(1)(1)。多边形的三角剖分多边形的三角剖分是将多边形分割成互不相交的三角是将多边形分割成互不相交的三角形的形的弦的集合弦的集合T T。v v0 0v v1 1v v2 2v v3 3v v4 4(v(vn n) )12第三章第三章 动态规划动态规划 ZZU69n结论一：在凸多边形的一个三角剖分结论一：在凸多边形的一个三角剖分T T中，各弦互不相交，中，各弦互不相交，且且T T已达到