第3章_动态规划2016all

1、1动态规划算法的基本要素动态规划算法的基本要素举例举例1 1 矩阵连乘问题矩阵连乘问题举例举例2 2 凸多边形最优三角剖分凸多边形最优三角剖分举例举例3 3 最长公共子序列最长公共子序列举例举例4 4 多段图的最短路径问题多段图的最短路径问题举例举例5 0-15 0-1背包问题背包问题举例举例6 6 资源分配问题资源分配问题多阶段决策问题多阶段决策问题多阶段决策过程：多阶段决策过程：问题的活动过程分为若干相互联问题的活动过程分为若干相互联系的阶段，任一阶段系的阶段，任一阶段i以后的行为仅依赖于以后的行为仅依赖于i阶段阶段的过程状态，而与的过程状态，而与i阶段之前的过程如何达到这种阶段之前的过程

2、如何达到这种状态的方式无关。在每一个阶段都要做出决策，状态的方式无关。在每一个阶段都要做出决策，这一系列的决策称为多阶段决策过程这一系列的决策称为多阶段决策过程(multistep decision process) 。 最优化问题：最优化问题：问题的每一阶段可能有多种可供选择问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。题的结果可能不同。 多阶段决策的最优化问题多阶段决策的最优化问题：求能够获得问题最优解：求能够获得问题最

3、优解的决策序列的决策序列最优决策序列。最优决策序列。22022-3-1731）枚举法）枚举法 穷举穷举可能的决策序列，从中选取可以获得最优解的决策序列可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划）动态规划 20世纪世纪50年代初美国数学家年代初美国数学家R.E.Bellman等人在研究多阶段决策等人在研究多阶段决策过程的优化问题时，提出了著名的过程的优化问题时，提出了著名的最优化原理最优化原理(principle of optimality)，把，把多阶段多阶段过程转化为一系列过程转化为一系列单阶段单阶段问题，创立了解决这问题，创立了解决这类过程优化问题的新方法类过程优化问题的

4、新方法动态规划动态规划。 动态规划动态规划(dynamic programming)是是运筹学运筹学的一个分支，是求解的一个分支，是求解决策过程决策过程(decision process)最优化的数学方法。最优化的数学方法。 应用领域：动态规划问世以来，在经济管理、生产调度、工程技应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。方法

5、求解更为方便。多阶段决策过程的求解策略多阶段决策过程的求解策略2022-3-174多阶段决策问题多阶段决策问题n多阶段决策过程多阶段决策过程 多阶段决策过程是活动过程可按时间或空间顺序分解成若干相互独立、相互联系的阶段，在每个阶段的状态下做出决策，整个过程的决策构成一个决策序列，则称多阶段决策过程为序贯决策过程。称问题为多阶段决策问题。状态1状态2状态3状态4状态5决策2决策3决策4决策1q 多阶段决策问题的特点多阶段决策问题的特点 过程可分为若干个相互联系的阶段；每一阶段都对应着一组可供选择的决策；每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。2022-3-175第第1阶段阶段

6、第第2阶段阶段第第3阶段阶段第第4阶段阶段状状态态1状状态态2状状态态4状状态态5状状态态3决决策策1决决策策2决决策策4决决策策3q 动态规划动态规划 把多阶段过程的问题转化为一系列单阶段的问题，逐个阶段求解的最优化数学方法。6 动态规划算法与分治法类似，其动态规划算法与分治法类似，其基本思想基本思想是将是将待求解问题分解成若干个子问题。待求解问题分解成若干个子问题。n nn/4n/4n/4n/4n/4n/4n/4n/4区别区别：经分解得到的子问题往往不是互相：经分解得到的子问题往往不是互相独立独立的。的。问题问题：用分治法求解，有些子问题被重复计算多次。：用分治法求解，有些子问题被重复计算

7、多次。7 保存已解决的子问题的答案，在需要时找出已保存已解决的子问题的答案，在需要时找出已求得的答案，以避免大量的重复计算，从而得求得的答案，以避免大量的重复计算，从而得到多项式时间算法。这就是到多项式时间算法。这就是动态规划动态规划算法。算法。 在算法中用表格来保存已经求解的子问题的解，在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。即可查表取出其解，避免了重复计算。解决方法解决方法算法设计与分析8动态规划的基本要素动态规划的基本要素n最优子结构：问题的最优解是由其子问题的最优解所构成

8、的。n重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。9n找出最优解的性质，并描述其结构特征。找出最优解的性质，并描述其结构特征。n递归地定义最优值。递归地定义最优值。n以自底向上的方式计算出最优值。以自底向上的方式计算出最优值。n根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。n步骤步骤13是动态规划算法的基本步骤。若需要最优是动态规划算法的基本步骤。若需要最优解，则必须执行第解，则必须执行

9、第4步，步，为此还需要在第为此还需要在第3步中记录步中记录构造最优解所必需的信息。构造最优解所必需的信息。动态规划算法的基本步骤动态规划算法的基本步骤算法设计与分析10动态规划的备忘录方法动态规划的备忘录方法n动态规划中采用自底向上的方式。但是在递归动态规划中采用自底向上的方式。但是在递归定义中往往是自上而下的描述。备忘录方法就定义中往往是自上而下的描述。备忘录方法就采用与递归定义一致的自上而下的方式。采用与递归定义一致的自上而下的方式。n备忘录方法同样用表格来保存已解子问题的信备忘录方法同样用表格来保存已解子问题的信息。每个子问题初始化时都标记为尚未求解。息。每个子问题初始化时都标记为尚未求

10、解。在递归求解过程中，对每个待解子问题，先查在递归求解过程中，对每个待解子问题，先查看它是否已求解。若未求解，则计算其解并填看它是否已求解。若未求解，则计算其解并填表保存。若已求解，则查表取出相应的结果。表保存。若已求解，则查表取出相应的结果。n备忘录方法同样避免了子问题的重复计算，因备忘录方法同样避免了子问题的重复计算，因而和动态规划算法具有同样效率。而和动态规划算法具有同样效率。11动态规划算法举例动态规划算法举例1 1：矩阵连乘问题：矩阵连乘问题1050 A4010 B3040 C530 D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB给定给定n n个矩阵个矩阵AA1 1,

11、A,A2 2,.,A,.,An n ，其中，其中A Ai i与与A Ai+1i+1是可乘的。是可乘的。由于乘法满足结合律，故计算矩阵的连乘可以有不同由于乘法满足结合律，故计算矩阵的连乘可以有不同的计算次序。其计算次序可以用加括号的方式确定。的计算次序。其计算次序可以用加括号的方式确定。假设有假设有4 4个矩阵：个矩阵：A,B,C,DA,B,C,D乘法：乘法：1600016000乘法：乘法：1050010500乘法：乘法：3600036000乘法：乘法：8750087500乘法：乘法：3450034500算法设计与分析12不同计算顺序的差别不同计算顺序的差别n设矩阵设矩阵A1, A2和和A3分别

12、为分别为10100, 1005和和550的矩阵，现要计算的矩阵，现要计算A1A2A3 。n若按若按(A1A2)A3)来计算，则需要的数乘次数为来计算，则需要的数乘次数为101005 + 10550 = 7500n若按若按(A1(A2 A3)来计算，则需要的数乘次数为来计算，则需要的数乘次数为100 5 50+ 1010050 = 75000n后一种计算顺序的计算量竟是前者的后一种计算顺序的计算量竟是前者的10倍！倍！n所以，求多个矩阵的连乘积时，计算的结合所以，求多个矩阵的连乘积时，计算的结合顺序是十分重要的。顺序是十分重要的。13给定给定n n个矩阵个矩阵A A1 1,A,A2 2, ,A,

13、An n，其中，其中A Ai i与与A Ai+1i+1是可乘的，是可乘的，i=1i=1, ,2 ,2 , ,n-1n-1。如何确定计算矩。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积所需要的阵连乘积所需要的乘法次数最少乘法次数最少。14列举出所有可能的计算次序，并计算出每一列举出所有可能的计算次序，并计算出每一种计算次序所需要的乘法次数，从中找出一种计算次序所需要的乘法次数，从中找出一种乘法次数最少的计算次序。种乘法次数最少的计算次序。 时间复杂度分析：对于时间复杂度分析：对于n n个矩阵的连乘，设其不同的个矩阵的连乘，设其不同的计算次序为

14、计算次序为P(n)P(n)。由于每种加括号方式都可以分解为。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：两个子矩阵的加括号问题：(A(A1 1.A.Ak k)(A)(Ak+1k+1A An n) )可以可以得到关于得到关于P(n)P(n)的递推式如下：的递推式如下：结论：结论：P(n)P(n)随随n n的增长呈指数增长，不是高效算法。的增长呈指数增长，不是高效算法。( )( )()nknP nP k P nkn11111 115消除重复的计算消除重复的计算n要消除重复计算，可在在计算过程中保存已解要消除重复计算，可在在计算过程中保存已解决的子问题的答案。这样，每个子问题只计算决的子问

15、题的答案。这样，每个子问题只计算一次，而在后面需要时只要简单查一下，从而一次，而在后面需要时只要简单查一下，从而避免重复计算。避免重复计算。n计算方式可依据递归式自底向上地进行。计算方式可依据递归式自底向上地进行。n注意到在此问题中，注意到在此问题中，不同的有序对不同的有序对 (i, j)就对应就对应不同的子问题，因此不同的子问题，因此不同的子问题个数个数最不同的子问题个数个数最多只有多只有Cn2+ n = (n2)个。个。n这样便可以得到多项式时间的算法。这样便可以得到多项式时间的算法。16自底向上的计算自底向上的计算n例如对于例如对于A1A2A3A4，依据递归式以自底向上的依据递归式以自底

16、向上的方式计算出各个子问题，其过程如下：方式计算出各个子问题，其过程如下：m11m22m33m44m12m23m34m13m24m24其中mii = 0mii+1 = pi1pipi+1mij = minikj mik+mk+1j+pi1pkpj例如： m13 = min m11+m23+p0p1p3m12+m33+p0p2p317将矩阵连乘积将矩阵连乘积A Ai iA Ai+1i+1.A.Aj j 简记为简记为Ai:jAi:j，ijij。考察计算考察计算Ai:jAi:j的最优计算次序。设这个计算次序在矩阵的最优计算次序。设这个计算次序在矩阵A Ak k和和A Ak+1k+1之间将矩阵链断开，

17、之间将矩阵链断开，ikjikj，则其相应完全，则其相应完全加括号方式为：加括号方式为： ( ( A Ai iA Ai+1i+1.A.Ak k）( (A Ak+1k+1A Ak+2k+2.A.Aj j ) )计算量计算量：Ai:kAi:k的计算量加上的计算量加上Ak+1:jAk+1:j的计算量，再加上的计算量，再加上Ai:kAi:k和和Ak+1:jAk+1:j相乘的计算量。相乘的计算量。 18n关键特征关键特征：计算：计算A1:nA1:n的最优次序所包含的计的最优次序所包含的计算矩阵子链算矩阵子链 A1:kA1:k和和Ak+1:nAk+1:n的次序也是最的次序也是最优的。优的。n矩阵连乘计算次序

18、问题的最优解包含着其子问矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为题的最优解。这种性质称为最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态规划问题的最优子结构性质是该问题可用动态规划算法求最优解的算法求最优解的显著特征。显著特征。19 假设计算假设计算Ai:jAi:j（1ijn1ijn）所需要的最少乘法次数）所需要的最少乘法次数为为mi,jmi,j，则原问题的最优值为，则原问题的最优值为m1,nm1,n。 当当i=ji=j时，时，Ai:j=AAi:j=Ai i，因此，因此mi,i=0mi,i=0，i=1,2,i=1,2,n,n 当当ijij时，时，mij

19、=mik+mk+1j+mij=mik+mk+1j+p pi-1i-1p pk kp pj j ki,i+1,.,j-1ki,i+1,.,j-1 可以递归地定义可以递归地定义mi,jmi,j为：为：jipppjkmkimjijimjki, 1,min0,1jki20n对于对于1ijn1ijn不同的有序对不同的有序对(i,j)(i,j)对应不对应不同的子问题，因此不同子问题的个数最多同的子问题，因此不同子问题的个数最多只有：只有： 可以看出，在递归计算时，有许多子问题可以看出，在递归计算时，有许多子问题被重复计算。被重复计算。)(22nnn21int recurMatrixChain(int p

20、, int i, int j) if (i=j) return 0; int u =; for (int k=i; kj; k+) int t= recurMatrixChain(p,i,k) + recurMatrixChain(p,k+1,j)+pi-1*pk*pj; if (tu) u=t; sij=k; return u;22n出现重复计算是该问题用动态规划算法求解的出现重复计算是该问题用动态规划算法求解的又一个显著特征。又一个显著特征。n用动态规划算法解此问题，可依据其递归式以用动态规划算法解此问题，可依据其递归式以自底向上自底向上的方式进行计算。在计算过程中，保的方式进行计算。在计

21、算过程中，保存已解决的子问题答案。每个子问题只计算一存已解决的子问题答案。每个子问题只计算一次，在后面需要时只要简单查找一下，从而可次，在后面需要时只要简单查找一下，从而可以避免大量地重复计算，最终得到多项式时间以避免大量地重复计算，最终得到多项式时间的算法。的算法。23假设假设Ai的维数为的维数为pi-1pi，则输入序列为则输入序列为 p0, p1, p2, . ,pn pn+1 记录每个矩阵的维数记录每个矩阵的维数;mi,j记录记录AiAi+1.Aj相乘的代价（乘法次数）相乘的代价（乘法次数）;si,j记录取得最优代价所断开的点记录取得最优代价所断开的点k 。24具有自底向上的计算特征：具

22、有自底向上的计算特征：如果计算如果计算mi,jmi,j，仅需要计算，仅需要计算 小于小于j-i+1j-i+1个的矩阵乘积。个的矩阵乘积。即计算长度为即计算长度为L L的矩阵相乘代价仅依赖于小的矩阵相乘代价仅依赖于小于于L L长度的矩阵相乘代价。长度的矩阵相乘代价。算法思路：按照长度递增算法思路：按照长度递增(1,2, . n) (1,2, . n) 计计算算mi,jmi,j代价代价。25算法算法matrixChainmatrixChain，首先计算出，首先计算出mi,i=0,i=1,2,nmi,i=0,i=1,2,n。然后，根据递归式，。然后，根据递归式，按矩阵链长递增的方式依次计算：按矩阵链

23、长递增的方式依次计算：mimi，i+1,i=1,2,n-1,(i+1,i=1,2,n-1,(矩阵链长度为矩阵链长度为2 2）；）；mimi，i+2,i=1,2,n-2, (i+2,i=1,2,n-2, (矩阵链矩阵链长度为长度为3 3）；在计算在计算mimi，jj时，只用到已计算的时，只用到已计算的mimi，kk和和mk+1mk+1，j.j.261234567812345671234561234512341231211 2 3 4 5 6 7 812345678m长度（个数）长度（个数）m3,6 :m3,3+m4,6m3,4+m5,6m3,5+m6,6r27void matrixChain(i

24、nt p , int mNUM+1, int sNUM+1,int n) / n是当前矩阵个数，是当前矩阵个数，NUM是最大矩阵个数是最大矩阵个数 处理矩阵长度为处理矩阵长度为1的代价（的代价（mi,i = 0）；）； for (int r = 2; r = n; r+) /长度从长度从2n for (int i = 1; i mij, k-sij; ( ikj) 28void matrixChain(int p, int mNUM+1, int sNUM+1) / p数组包含数组包含n+1元素元素 for (int i = 1; i = n; i+) mii = 0; /将长度为将长度为1的

25、代价赋为的代价赋为0 for (int r = 2; r = n; r+) / 长度从长度从2n for (int i = 1; i = n - r+1; i+) / 从第从第1行开始行开始n-r+1行为止行为止 int j=i+r-1; mij = mii + mi+1j+ pi-1*pi*pj; / k=i, mii=0可以省略可以省略 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; 算法描述了矩阵填充的过程：r为当前斜线起始列号（长度）i控

26、制当前斜线元素行号J控制当前斜线元素列号29A1A2A3A4A5A630353515155510102020251137520103504375554271252053510002625543213000201535250005322min52541531521pppmmpppmmpppmmm算法复杂度分析算法复杂度分析：算法：算法matrixChainmatrixChain的主要计算量取决于算法中对的主要计算量取决于算法中对r r，i i和和k k的三重循环。循环体内的计算量为的三重循环。循环体内的计算量为O(1)O(1)，三重循环的总次数为，三重循环的总次数为O(nO(n3 3) )。因此

27、算法计算时间上界为。因此算法计算时间上界为O(nO(n3 3) )。算法占用的空间为。算法占用的空间为O(nO(n2 2) )。p0p1p2p3p4p5p63035155102025举例：给定一个举例：给定一个6 6个矩阵的矩阵链：个矩阵的矩阵链：30继续分析继续分析Void MatrixChain(int p, int n, int *m, int *s) for (int i = 1; i = n; i+) mii = 0; /将对角线元素赋值为零，即单个矩阵计算量为0 for (int r = 2; r = n; r+) for (int i = 1; i = n r +1; i+) i

28、nt j = i + r 1;(5) mij = mi+1j + pi1*pi*pj; /计算Ai, j = Ai: i Ai+1: j sij = i; /记下断点i(7) for (int k = i + 1; k j; k+) int t = mik + mk+1j + pi1*pk*pj; /对ikj, 逐个计算Ai, j = Ai: k Ak+1: j if (t mij) mij = t; sij = k; /记下较小的mij及相应的断点k 第(5)步与第(7)步能否合在一起?能。此处分开是为了给mij赋初值。算法设计与分析31 设要计算矩阵连乘积A1A2A3A4A5A6，其维数分

29、别为3535, 3515, 155, 510, 1020, 2025, 即p0=35, p1=35, p2=15, p3=5, p4=10, p5=20, p6=25。 MatrixChain用矩阵mij, sij存放子问题Ai: j的最小计算量以及相应的断点。123456 1 2 3 4 5 6mij1234561 2 3 4 5 6sijMatrixChain将如下面红色箭头所示的过程逐个计算子问题Ai: j：执行for (int i = 1; i = n; i+) mii = 0后将对角线元素全部置零，即子问题Aii = 0。000000当r=2，执行第(5)句完成了相邻矩阵Aii+1=

30、pi1*pi*pj 的计算，并在sij中添入了相应的断点。其中的第(7)句因为j = i+1(k=i+1)而被跳过去了，实际并没有执行。1575026257501000500012345当r=3，i=1时，执行第(5)句计算A1:12:3， m13 = m23 + p0*p1*p3 = 2625 +30*35*5 = 787578751执行第(7)句计算A1:23:3， t = m12 + m33 + p0*p2*p3 = 15750+0+35*15*5 = 183757875，所以m13不变，断点仍为1。当r=3，i=2时，执行第(5)句计算A2:23:4，m24 = m34 + p1*p2

31、*p4 = 750 +35*15*10 = 600060002执行第(7)句计算A2:34:4， t = m23+m44+ p1*p3*p4 = 2625+0+35*5*10 = 43756000，所以m24改为4375，断点改为3。43753当r=3，i=3时，执行第(5)句计算A3:34:5，m35 = m45 + p2*p3*p5 = 1000 +15*5*20 = 250025003执行第(7)句计算A3:45:5， t = m34+m55+ p2*p4*p5 = 750+0+15*10*20 = 37502500，所以m35仍为2500，断点仍为3。当r=3，i=4时，执行第(5)句

32、计算A4:45:6，m46 = m56 + p3*p4*p6 = 5000 +5*10*25 = 625062504执行第(7)句计算A4:56:6， t = m45+m66+ p3*p5*p6 = 1000+0+5*20*25 = 35006250，所以m46改为3500，断点改为5。35005类似的，当r=4、5、6时，可以计算出相应的mij及其相应的断点sij，如下图中所示：937537125353753118753105003151253由由m16=15125可知这可知这6个矩阵连乘积的最小运算次数为个矩阵连乘积的最小运算次数为15125。由。由s16 = 3可知可知A1: 6的最优计

33、算次序为的最优计算次序为A1: 3 A4: 6；由；由s13=1可知可知A1: 3的最优计算次序为的最优计算次序为A1: 1 A2: 3；由；由s46=5可知可知A4: 6的最优计算次序为的最优计算次序为A4: 5 A6: 6；因此最优计算次序为：；因此最优计算次序为：(A1(A2A3)(A4A5)A6)。32打印矩阵的运算次序打印矩阵的运算次序void printOptimalParens(int sNUM+1, int i, int j) if (i = j) coutA i ; else cout(; printOptimalParens(s,i,sij); printOptimalPa

34、rens(s,sij+1,j); cout)”; 输出结果：输出结果：(A1(A2A3)(A4A5)A6)(A1(A2A3)(A4A5)A6)2022-3-1733举例：给定一个举例：给定一个6 6个矩阵的矩阵链：个矩阵的矩阵链：q 举例举例 计算5 个矩阵乘积最少数乘次数。设：M1：510M2：104M3：46M4：610M5：102C6,6C1,6C1,5C1,4C1,3C1,2C1,1C2,6C2,5C2,4C2,3C2,2C3,6C3,5C3,4C3,3C4,6C4,5C4,4C5,6C5,5d=0d=2d=1d=3d=4d=5(M1 ( M2 ( M3 ( M4 M5 )例如：例如：

35、n=6的计算形式348 2620 4320 3200 20 248 3640 3240 30 168 4240 40 120 50 0 34矩阵连乘计算次序问题的最优解包含着其子问题的矩阵连乘计算次序问题的最优解包含着其子问题的最优解最优解。这种性质称为最优子结构性质。这种性质称为最优子结构性质。在利用递归算法求解问题时，每次产生的子问题并不总是在利用递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。题的重叠性质。35n用多边形顶点的逆时针序列表示凸多边形，即用多边形顶点的逆时针序列表示

36、凸多边形，即P=vP=v0 0,v,v1 1, ,v,vn-1n-1 表示具有表示具有n n条边的凸多边形。条边的凸多边形。n若若v vi i与与v vj j是多边形上不相邻的是多边形上不相邻的2 2个顶点，则线段个顶点，则线段v vi iv vj j称为称为多边形的一条多边形的一条弦弦。弦将多边形分割成。弦将多边形分割成2 2个多边形个多边形vvi i,v,vi+1i+1, ,v,vj j 和和vvj j,v,vj+1j+1, ,v vi i 。36n多边形的三角剖分就是将多边形分割成互不相交的三多边形的三角剖分就是将多边形分割成互不相交的三角形的弦的集合角形的弦的集合T T。n在凸多边形在

37、凸多边形P P的三角剖分的三角剖分T T中中, ,各弦互不相交各弦互不相交, ,且集合且集合T T已达到最大。已达到最大。n在有在有n n个顶点的凸多边形的三角剖分中，恰有个顶点的凸多边形的三角剖分中，恰有n-3n-3条弦条弦和和n-2n-2个三角形。个三角形。 37n给定凸多边形给定凸多边形P P，以及定义在由多边形的边和弦组成，以及定义在由多边形的边和弦组成的三角形上的的三角形上的权函数权函数w w。要求确定该凸多边形的三角剖。要求确定该凸多边形的三角剖分，使得三角剖分中各个三角形的分，使得三角剖分中各个三角形的权值之和最小权值之和最小。 38n一个带括号的表达式可以用一棵二叉树表示其一个

38、带括号的表达式可以用一棵二叉树表示其计算顺序，称为表达式的语法树。计算顺序，称为表达式的语法树。例如，例如，(A(A1 1(A(A2 2A A3 3)(A)(A4 4(A(A5 5A A6 6)对应的语法树是对应的语法树是语法树语法树39n凸多边形凸多边形vv0 0,v,v1 1, ,v vn-1n-1 的三角剖分也可以用语法树表示。的三角剖分也可以用语法树表示。除（除（v0,v6v0,v6）外，其余）外，其余边边构成构成叶子叶子结点，结点，弦弦构成构成内部结点内部结点。40n矩阵连乘积中的每个矩阵矩阵连乘积中的每个矩阵A Ai i对应凸对应凸(n+1)(n+1)边形中的一条边形中的一条边边v

39、 vi-1i-1v vi i。三角剖分中的一条弦。三角剖分中的一条弦v vi iv vj j，ijij，对应矩阵连，对应矩阵连乘积乘积Ai+1:jAi+1:j。41凸多边形最优三角凸多边形最优三角 给定凸边形给定凸边形p=vp=v0 0,v,v1 1,.v,.vn-1n-1 ，以及定义，以及定义在由多边形的边和弦组成的三角形上的权在由多边形的边和弦组成的三角形上的权函数函数w w，要求确定该凸多边形的三角，要求确定该凸多边形的三角42凸多边形的最优三角剖分凸多边形的最优三角剖分问题有最优子结构性质。问题有最优子结构性质。证明（反证法）：证明（反证法）：如果凸如果凸(n+1)(n+1)边形边形P

40、=vP=v0 0,v,v1 1, ,v,vn n 的的最最优三角剖分优三角剖分T T包含三角形包含三角形v v0 0v vk kv vn n，1kn-11kn-1，则，则T T的权为的权为3 3个部分权的和：个部分权的和：v v0 0v vk kv vn n +v+v0 0,v,v1 1, ,v,vk k+v+vk k,v,vk+1k+1, ,v,vn n 可以断言，由可以断言，由T T确定的两个子多边形的三角剖分也是最优确定的两个子多边形的三角剖分也是最优的。因为若有的。因为若有vv0 0,v,v1 1, ,v,vk k 或或vvk k,v,vk+1k+1, ,v,vn n 的更小权的的更小

41、权的三角剖分将导致三角剖分将导致T T不是最优三角剖分的矛盾。不是最优三角剖分的矛盾。 43n定义定义tijtij，1ijn1ijn为凸子多边形为凸子多边形vvi-1i-1,v,vi i, ,v,vj j 的最优三角剖分所对应的权函的最优三角剖分所对应的权函数值，即其最优值。假设将退化的多边形数值，即其最优值。假设将退化的多边形vvi-1i-1,v,vi i 的权值定义为的权值定义为0 0。最终需要计算的凸。最终需要计算的凸(n+1)(n+1)边形边形P P的最优权值为的最优权值为t1nt1n。44n利用最优子结构性质利用最优子结构性质递归地计算递归地计算tijtij 。当当j-ij-i1 1

42、时，凸子多边时，凸子多边形至少有形至少有3 3个顶点。个顶点。由最优子结构性质，由最优子结构性质，tijtij的值应为的值应为tiktik的值加上的值加上tk+1jtk+1j的值，再加上三角形的值，再加上三角形v vi-1i-1v vk kv vj j的权值，其中的权值，其中ikj-1ikj-1。需要在。需要在j-ij-i个个位置中选出使位置中选出使tijtij达到最小的达到最小的k k。45tijtij可递归地定义为：可递归地定义为：jijivvvwjktkitjitjkijki)(1min01（3）计算最优值）计算最优值n创建数组创建数组sij，用于存放与，用于存放与vi-1和和vj一起构

43、成三角形的第一起构成三角形的第3个顶点位置。个顶点位置。n与矩阵连乘相仿，最优值可以通过与矩阵连乘相仿，最优值可以通过数组数组s得到。得到。4647void minWeightTriangulation(int n, int tNUM, int sNUM) / tij存放存放vi-1 vj之间凸多边形最优剖分权值之间凸多边形最优剖分权值 / sij 存放最优剖分令一个顶点的位置存放最优剖分令一个顶点的位置 初始化初始化t=0； for (int r = 2; r = n; r+) / 计算计算r凸边形的最优剖分凸边形的最优剖分 2. n for (int i = 1; i j之间边数为之间边数

44、为r的最优剖分权值及位置的最优剖分权值及位置k / 并分别将结果存放在并分别将结果存放在tij和和sij中中 48void minWeightTriangulation(int n, int tNUM, int sNUM) for (int i = 1; i = n; i+) tii = 0; / 初始化初始化t for (int r = 2; r = n; r+) / 计算计算r凸边形的最优剖分凸边形的最优剖分 for (int i = 1; i j之间的最优值及位置之间的最优值及位置k tij = ti+1j+ w(i-1, i, j); sij = i; for (int k = i+1

45、; k i+r-1; k+) int u= tik + tk+1j + w(i-1, k, j); if (u tij) tij = u; sij = k; 消耗空间：消耗空间：O(n2)消耗时间：消耗时间：O(n3)49在生物工程应用中，我们经常要比较两个在生物工程应用中，我们经常要比较两个DNADNA序列的相序列的相似性，在软件工程领域也经常比较两个软件版本，以似性，在软件工程领域也经常比较两个软件版本，以便确定版本的变化，所有这些相似性比较问题，都涉便确定版本的变化，所有这些相似性比较问题，都涉及最长公共子序列问题。及最长公共子序列问题。若给定序列若给定序列X=xX=x1 1,x,x2

46、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有：有：z zj j=x=xi ij j。 例如，例如，Z=BZ=B，C C，D D，BB 是是X=AX=A，B B，C C，B B，D D，A A，B B 的子序列，的子序列， 相应的递增下标序列为相应的递增下标序列为22，3 3，5 5，77。50给定给定2 2个序列个序列X X和和Y Y，当另一序列，当另一序列

47、Z Z既是既是X X的子序列的子序列又是又是Y Y的子序列时，称的子序列时，称Z Z是是X X和和Y Y的的公共子序列公共子序列。最长公共子序列问题最长公共子序列问题：给定：给定2 2个序列个序列 X=xX=x1 1,x,x2 2, ,x,xm m 和和 Y=yY=y1 1,y,y2 2, ,y,yn n ， 找出找出X X和和Y Y的最长公共子序列。的最长公共子序列。51假设序列假设序列X=xX=x1 1,x,x2 2, ,x,xm m 和和Y=yY=y1 1,y,y2 2, ,y,yn n 的最长公共的最长公共子序列为子序列为Z=zZ=z1 1,z,z2 2, ,z,zk k ，则，则(1

48、)(1)若若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-1的最长公共子的最长公共子序列。序列。(2)(2)若若x xm myyn n且且z zk kxxm m，则，则Z Z是是X Xm-1m-1和和Y Y的最长公共子序列。的最长公共子序列。(3)(3)若若x xm myyn n且且z zk kyyn n，则，则Z Z是是X X和和y yn-1n-1的最长公共子序列。的最长公共子序列。2 2个序列的最长公共子序列包含了这个序列的最长公共子序列包含了这2 2个序列的前缀的个序列的前缀的最长公共子序列。

49、因此，最长公共子序列。因此，最长公共子序列问题具有最最长公共子序列问题具有最优子结构性质优子结构性质。 52证明证明 (1) 若若xm= yn，则，则zk = xm = yn， 且且Zk-1是是Xm-1和和Yn-1的最长公共子序列。的最长公共子序列。 反证法：反证法： 假设假设zkxm,则则 z1, z2, ., zk, xm是是X和和Y的长度的长度为为k+1的公共子序列。与假设的公共子序列。与假设Z是是X和和Y的最的最长公共子序列矛盾。长公共子序列矛盾。 （2）（）（3）类似。）类似。n由最长公共子序列问题的最优子结构性质由最长公共子序列问题的最优子结构性质可知可知: :要找出要找出X=xX

50、=x1 1,x,x2 2,x,x3 3,x,xm m 和和Y=yY=y1 1,y,y2 2,y,y3 3,y,yn n 的最长公共子序列，可按的最长公共子序列，可按以下方式递归计算：以下方式递归计算：n当当x xm m=y=yn n时时，找出，找出x xm-1m-1和和y yn-1n-1的最长公共子序列的最长公共子序列，然后在其尾部加上，然后在其尾部加上x xm m( (或者或者y yn n) )即可得即可得X X和和Y Y的的最长公共子序列。最长公共子序列。n当当x xm m y yn n时时，必须解两个子问题：即找出，必须解两个子问题：即找出x xm-1m-1和和y y的一个最长公共子序列

51、及的一个最长公共子序列及x x和和y yn-1n-1的一个最长的一个最长公共子序列。这两个公共子序列中较长者即为公共子序列。这两个公共子序列中较长者即为x x和和y y的最长公共子序列。的最长公共子序列。5354由最长公共子序列问题的最优子结构性质建立子问题最由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用优值的递归关系。用cijcij记录序列记录序列X Xi和和Y Yj的最长公共的最长公共子序列的长度。其中，子序列的长度。其中， X Xi i=x=x1 1,x,x2 2, ,x,xi i ；Y Yj j=y=y1 1,y,y2 2, ,y,yj j 。当。当i=0i=0或或

52、j=0j=0时，时，X Xi i和和Y Yj j的最长公共子的最长公共子序列是空序列。故此时序列是空序列。故此时cij=0cij=0。其他情况下，由最。其他情况下，由最优子结构性质可建立递归关系如下：优子结构性质可建立递归关系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110c0.m0.n55由于在所考虑的子问题中，总共有由于在所考虑的子问题中，总共有(mn)(mn)个不个不同的子问题，采用递归算法会随着序列长度的同的子问题，采用递归算法会随着序列长度的增长，时间复杂性成指数递增，而采用动态规增长，时间复杂性成指数递增，而采用动态规划算法自

53、底向上计算最优值可提高算法的效率。划算法自底向上计算最优值可提高算法的效率。 bij记录计算子序列的方式。记录计算子序列的方式。cij记录记录Xi和和Yj的最长公共子序列的长度。的最长公共子序列的长度。56int lcsLength(char x , char y , int bNUM,int m,int n ) int* c = 创建C数组; 初始化ci0，c0i 为0; for (int i = 1; i = m; i+) for (int j = 1; j =cij-1) / 第2,3种情况 cij=ci-1j; bij=2; else cij=cij-1; bij=3; return

54、cmn; 时间复杂度时间复杂度O(mn)O(mn)57int lcsLength(char x, char y, int bNUM,int m,int n) int cm+1n+1; for (int i = 0; i=m; i+) ci0=0; for (int i = 0; i=n; i+ ) c0i=0; for (int i = 1; i = m; i+) for (int j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; return cmn; 时间复杂度时间复杂度O(mn)O(mn)58构造最长公共子序列构造最长公共

55、子序列(打印最长公共子序列）打印最长公共子序列）void lcs(int i,int j, char x, int bNUM) if (i =0 | j=0) return; if (bij= 1) lcs(i-1, j-1, x, b); coutxi- 1; else if (bij = 2) lcs(i-1, j, x, b); else lcs(i, j-1, x, b); 每次运行都使每次运行都使i 或或 j 减减1，所以时间复杂度为，所以时间复杂度为O(m+n)。59 #include int main() char* x = ABCBDAB; char* y =BDCABA; i

56、nt xlen = strlen(x); int ylen = strlen(y); int bNUM1 + 1NUM2 + 1; int len = lcsLength(x, y, b, xlen,ylen); lcs(xlen,ylen, x, b); return 0;运行结果：运行结果：BCBA60运行结果：运行结果：BCBA61运行结果：运行结果：BCBA6200000000000yj:xmy1y2ynx1x2xii012nm120firstsecond填表的顺序：沿着箭头先填充最上面一行，填表的顺序：沿着箭头先填充最上面一行，然后填充接下来的行然后填充接下来的行6300000000

57、000yj:DACFABxiji012nm120矩阵 cStepi, j:l它告诉我们要获得最优结果应该如何选择l如果 xi = yjcStepi, j = “ ”（1）l如果 nZi - 1, j nZi, j-1cStepi, j = “” （2）否则cStepi, j = “” （3）33CDci,j-1ci-1,jnLCS(sX, sY, nA, nB)1 for i 1 to nA do nZi, 0 02 for j 0 to nB do nZ0, j 03 for i 1 to nA do4 for j 1 to nB do5 if xi = yj6 then nZi, j ci

58、 - 1, j - 1 + 17 cStep i, j “ ”8 else if nZi - 1, j nZi, j - 19 then nZi, j nZi - 1, j10 cStep i, j “”11 else nZi, j nZi, j - 112 cStep i, j “”13 return nZ and cStep64运行时间: (nA*nB) 举例X = (B, D, C, A, B, A)Y = (A, B, C, B, D, A,B)650126345yjBDACAB51203467DABxiCBAB00000000000000000 11 1 1111 2211 2222

59、 1122 331 222331232 3 4 1223 44如果 xi = yj cStepi, j = “ ”如果 nZi - 1, jnZi, j-1cStepi, j = “ ”否则cStepi, j = “ ”找出最长共同子序列sLCS(cStep, sX, i, j)1 if i = 0 or j = 02 then return3 if cStepi, j = 4 then sLCS(cStep, X, i - 1, j - 1)+ xi5 elseif cStepi, j = 6 then sLCS(cStep, X, i - 1, j)7 else sLCS(cStep, X

60、, i, j - 1)6667多段图定义：多段图定义：给定有向连通带权图给定有向连通带权图G=(V,E,W)G=(V,E,W)，如果将顶，如果将顶点集合点集合 V V 划分成划分成 k k 个互不相交的子集个互不相交的子集V Vi i，1 1iik k，k k2,2,使得使得E E中的任何一条边中的任何一条边(u,v)(u,v)，必有，必有u uV Vi i,v,v V Vi+mi+m，m m 1 1，则称，则称这样的图为这样的图为多段图多段图。68多段图令令|V|V1 1| =|V| =|Vk k|=1,|=1,称称s s V V1 1为为源点源点，t tV Vk k为为汇点汇点。st69首