第3章动态规划(1)

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

2、第3 3章章 动态规划动态规划 通过应用范例学习动态规划算法设计策略。通过应用范例学习动态规划算法设计策略。 （1 1）矩阵连乘问题；）矩阵连乘问题； （2 2）最大子段和）最大子段和 （3 3）最长公共子序列；）最长公共子序列； （4 4）凸多边形最优三角剖分；）凸多边形最优三角剖分； （5 5）0-10-1背包问题背包问题 （6 6）图像压缩）图像压缩引言引言 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。个子问题。 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常但是经分解得到的子问题往

3、往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。就可以避免大量重复计算，从而得到多项式时间算法。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=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

4、) T(n/4) T(n/4) T(n/4)n/2T(n/4) T(n/4) T(n/4) T(n/4)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)动态规划基本步骤动态规划基本步骤找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。递归定义最优值。递归定义最优值。以自底向上的方式计算出最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。3.1 3.1 矩阵连乘问题矩阵连乘问题给定给定

5、n n个矩阵个矩阵 A A1 1, ,A A2 2,.,.,A An n ，其中，其中A Ai i与与A Ai+i+1 1是可乘的，是可乘的，i i=1,=1,2 2,.,.,n-n-1 1。考察这。考察这n n个矩阵的连乘积个矩阵的连乘积A A1 1A A2 2.A.An n。由于矩阵乘法满足结合律，所以计算矩阵的连乘可由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可完全确定，也

6、就是说该连乘积已完全加括号，则可以依此次序反复调用以依此次序反复调用2 2个矩阵相乘的标准算法计算个矩阵相乘的标准算法计算出矩阵连乘积。出矩阵连乘积。 矩阵连乘问题矩阵连乘问题完全加括号的矩阵连乘积可递归地定义为：完全加括号的矩阵连乘积可递归地定义为： 单个矩阵是完全加括号的；单个矩阵是完全加括号的； 矩阵连乘积矩阵连乘积A A是完全加括号的，则是完全加括号的，则A A可表示为可表示为2 2个个完全加括号的矩阵连乘积完全加括号的矩阵连乘积B B和和C C的乘积并加括号，的乘积并加括号，即即A=(BC)A=(BC)。设有四个矩阵设有四个矩阵A,B,C,DA,B,C,D，它们的维数分别是：，它们的

7、维数分别是：A=50A=501010，B=10B=104040，C=40C=403030，D=30D=305 5总共有五种完全加括号的方式：总共有五种完全加括号的方式：(A(BC)D) (A(BC)D) (A(B(CD) (AB)(CD) (AB)C)D) (A(BC)D)(A(B(CD) (AB)(CD) (AB)C)D) (A(BC)D)其数乘次数分别为：其数乘次数分别为：16000, 10500, 36000, 87500, 16000, 10500, 36000, 87500, 3450034500穷举搜索法穷举搜索法 问题描述：给定问题描述：给定n n个矩阵个矩阵A A1 1, ,A

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

9、的计算次序为个矩阵的连乘积，设其不同的计算次序为P(n)P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号由于每种加括号方式都可以分解为两个子矩阵的加括号问题：问题：( (A A1 1.A Ak k)()(A Ak+k+1 1A An n) )可以得到关于可以得到关于P(n)P(n)的递推式如的递推式如下：下：穷举搜索法 2/311/42111111nnnnnCnCnPnknPkPnnPnnk，其中，也就是说，也就是说，P P( (n n) )是随是随n n的增长成指数增长的。的增长成指数增长的。 下面我们考虑用动态规划求解。下面我们考虑用动态规划求解。 预处理：预处理：将矩阵连乘积

10、将矩阵连乘积A A1 1A A2 2.A.An n简记为简记为A A i i: :j j ，这里，这里i ij j。考察计算考察计算A A i i: :j j 的最优计算次序。设这个计算次序在矩阵的最优计算次序。设这个计算次序在矩阵A Ak k和和A Ak+k+1 1之间将矩阵链断开，之间将矩阵链断开，i ik k j j，则其相应完全加括号，则其相应完全加括号方式为（方式为（A A1 1A A2 2. A. Ak k）（）（A Ak+k+1 1 A Ak+2k+2. A. An n ）。）。动态规划1.分析最优解的结构 计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+

11、1:j相乘的计算量。分析最优解的结构：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。动态规划 2.2.建立递归关系建立递归关系设计算设计算A A i i: :j j ，11i ij jn n，所需要的最少数乘次，所需要的最少数乘次数数m m i i, ,j j ，则原问题的最优值为，则原问题的最优值为m m1,1,n n 。当当i i= =j j时，时，A A i i: :j j=A Ai i，因此，因此，m m i i, ,i

12、i=0=0，i i=1,=1,2 2, , ,n n。当当i i j j时，时，m m i i, ,j j=m m i i, ,k k+m m k k+1,+1,j j+p pi-1i-1p pk kp pj j可以递归地定义可以递归地定义m m i i, ,j j 为：为： k k的位置只有的位置只有j j-i-i种可能种可能(k=i,i+1,(k=i,i+1,j-1)j-1)。jipppjkmkimjijimjkijki1, 1,min0,动态规划 3. 3.计算最优值计算最优值对于对于11i ij jn n不同的有序对不同的有序对( (i i, ,j j) )对应于不同的对应于不同的子问

13、题。因此，不同子问题的个数最多只有子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，由此可见，在递归计算时，。这也是该问题可用动态规划算法求解的又一。这也是该问题可用动态规划算法求解的又一显著特征。显著特征。用动态规划算法解此问题，可依据其递归式以自底用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法

14、最终得到多项式时间的算法。 22nnn示例示例A1A2A3A4A5A630 3535 1515 55 1010 2020 25113752010350437555427125205351000262554 3213000201535250005322min52541531521pppmmpppmmpppmmm算法描述算法描述 算法描述：void 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+

15、1; i+) int j=i+r-1; /,k=i时的最优值mij = mii+mi+1j+ pi-1*pi*pj; /mik+mk+1j+.k=i时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; 动态规划 4.4.构造最构造最优解优解 void Traceback(int i, int j, int s10) if (i=j) return; Traceback(i, sij, s); Traceback(sij+1, j, s); cout Mu

16、ltiply A i , sij; cout and A (sij +1) , j endl; 4.4.构造构造最优解最优解复杂性分析：复杂性分析： 算法算法MatrixChainMatrixChain的主要计算量取决于算法中对的主要计算量取决于算法中对r r，i i和和k k的的3 3重循环。循环体内的计算量为重循环。循环体内的计算量为O(1)O(1)，而，而3 3重循环的总次数为重循环的总次数为O(nO(n3 3) )。因此算法的计算时间。因此算法的计算时间上界为上界为O(nO(n3 3) )。算法所占用的空间显然为。算法所占用的空间显然为O(nO(n2 2) )。3.2 3.2 动态规划

17、算法的基本要素动态规划算法的基本要素从计算矩阵连乘积最优计算次序的动态规划从计算矩阵连乘积最优计算次序的动态规划算法可以看出，该算法的有效性依赖于问题算法可以看出，该算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。从一般意义上讲，问质和子问题重叠性质。从一般意义上讲，问题的这两个重要性质是该问题可以用动态规题的这两个重要性质是该问题可以用动态规划算法求解的基本要素。本节着重介绍：划算法求解的基本要素。本节着重介绍： 最优子结构最优子结构 重叠子问题重叠子问题 备忘录方法备忘录方法此外，本节最后对动态规划算法与备忘录方此外，本

18、节最后对动态规划算法与备忘录方法的适用条件作了简单介绍法的适用条件作了简单介绍。一、最优子结构一、最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为这种性质称为。 在分析问题的最优子结构性质时，所用的方法具有普遍性：在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。解，从而导致矛盾。 利用问题

19、的最优子结构性质，以自底向上的方式递归地从子利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。问题能用动态规划算法求解的前提。 注意：同一个问题可以有多种方式刻划它的最优子结构，有注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）些表示方法的求解速度更快（空间占用小，问题的维度低）二、重叠子问题二、重叠子问题 递归算法求解问题时，每次产生的子问题并不总是新问题，递归算法求解问题时，每次产生的子问题并不总是

20、新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性有些子问题被反复计算多次。这种性质称为子问题的重叠性质。质。int RecurMatrixChain(int i，int j) if (i = j) return 0; int u = RecurMatrixChain(i，i) + RecurMatrixChain(i+1， j) + pi-1*pi*pj;sij = i;for (int k = i+1; k j; k+) int t = RecurMatrixChain(i，k) + RecurMatrixChain(k+1，j) + pi-1*pk*pj;if (t 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 = u;return u;