动态规划策略教材

1、)(),(cos)()(), 1 (cos) 1 (minmin1jfjitifjfjtfiAjAjF1()F3()F4()F5()F2()用函数用函数fi(x)表示第表示第i层节点到底部（假设是第层节点到底部（假设是第N层）的路层）的路径上数字和的最大值。径上数字和的最大值。显而易见：显而易见：f1(9)=9+maxf2(12)+f2(15)问题变成：问题变成：f1(9)=?f2(12)=12+maxf3(10)+f3(6)f2(15)=15+maxf3(6)+f3(8)fi(x)=x+maxfi+1(x1)+fi+1(x2)+递归公式的终止条件：fN(19)=19fN(7)=7思考：请同学

2、们手工计算一下结果？如何编程？如何编程与数据结构有关：将原始数塔写成下面的形式，用表示这个矩阵用矩阵表示上面的 nxmixgxfyxfygxfiixyi0 ,.,2 , 11110max初始条件： nxmixgxfyxfygxfiixyi0 ,.,2 , 11110max初始条件：n1,2,.,j ,.,2 , 11 1 1max0mijgjfkjifkigjifjk初始条件：1max arg0kjifkigjiajk为了表示方便, 以矩阵加括号表示矩阵相乘的顺序输入：向量输入：向量 P = ，n个矩阵的行数、列数个矩阵的行数、列数实例：实例： P = A1: 10 100, A2: 100

3、5, A3: 5 50, （1）单个矩阵是完全加括号的；）单个矩阵是完全加括号的；（2）矩阵连乘积）矩阵连乘积A是完全加括号的，则是完全加括号的，则A可可 表示为表示为2个完全加括号的矩阵连乘积个完全加括号的矩阵连乘积B和和C 的乘积并加括号，即的乘积并加括号，即 A=(B)(C) 1050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB1600010500360008750034500四种加括号方式四种加括号方式列举出所有可能的计算次序，并计算出每一种计算次序列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少

4、的计相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算次序。)/4()(11)()(1)(2/311nnPnnknPkPnPnnku算法复杂度分析算法复杂度分析：对于对于n个矩阵的连乘积，设其不同的计算次序为个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号由于每种加括号方式都可以分解为两个子矩阵的加括号问题：问题：(A1.Ak)(Ak+1An)可以得到关于可以得到关于P(n)的递推的递推式如下：式如下：将矩阵连乘积将矩阵连乘积 A1A2A3,An简记为简记为Ai:j,这里这里ij考察计算考察计算Ai:j的最优计算次序。设这个计算次序的最优计

5、算次序。设这个计算次序在矩阵在矩阵Ak和和Ak+1之间将矩阵链断开，之间将矩阵链断开，ikj，则其，则其相应完全加括号方式为相应完全加括号方式为).)(.(211jkkkiiAAAAAA计算量：计算量：Ai:k的计算量加上的计算量加上Ak+1:j的计算量，的计算量，再加上再加上Ai:k和和Ak+1:j相乘的计算量相乘的计算量u动态规划动态规划 划分子问题，确定子问题的边界，有划分子问题，确定子问题的边界，有i和和j确定确定子问题的边界子问题的边界jkipppjkmkimjim1, 1,这里 的维数为 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 种

6、可能kij 确定优化函数和递推方程：确定优化函数和递推方程：设立标记函数（决策函数）设立标记函数（决策函数） 为了为了确定加括号的次序确定加括号的次序，定义，定义 si,j,记录记录mi,j最优时最优时k的位置的位置 si,j=k问题：如何编程实现？ 自顶向下递归实现 自底向上迭代（递推）实现int RecurMatrixChain(P,i,j) mi,j= si,j=i for( k=i to j 1 ) q = RecurMatrixChain(P,i,k) + RecurMatrixChain(P,k+1,j) + pi 1 pk pj If (qmi,j) mi,j=q si,j=k

7、/end if /end for return mi,j 这里没有写出算法的全部描述（进入递归调用的初值等）复杂性满足递推关系复杂性满足递推关系 11111111)(2)()()()()(1)1()()(1)1()(nknknknkkTnOknTkTnOnTnOknTkTnOnT 数学归纳法证明数学归纳法证明 T(n) 2n 1 n=2,=2,显然为真显然为真 假设假设对于任何小于对于任何小于n 的的 k 命题为真命题为真, , 则则11111112)12(2)(22)()(2)()( nnnkknknOnOkTnOnT*递归实现的复杂性递归实现的复杂性n=5，计算子问题：，计算子问题：81个

8、个；不同的子问题：；不同的子问题：15个个子子问问题题1-12-23-34-45-51-22-33-44-51-32-43-51-42-51-5数数8121412845542221112复杂性高的原因：子问题重复计算复杂性高的原因：子问题重复计算MatrixChain(P,n) 令令所有的所有的 mi,j初值为初值为0 1 i j n for( r 2 to n) / r为计算的矩阵链长度为计算的矩阵链长度 for( i 1 to n r+1) /n-r+1为最后为最后r链的始位置链的始位置 j i+r 1 / 计算链计算链ij mi,j mi+1,j + pi 1*pi*pj / Ai(Ai

9、+1.Aj) si,j i /记录分割位置记录分割位置 for(k i+1 to j 1) t mi,k+mk+1,j+ pi 1*pk*pj /(Ai.Ak)(Ak+1.Aj) if( tmi,j) mi,jt si,jk /end if / end for(k=) /end for(i=.)113752010350437555427125205351000262554 3213000201535250005322min52541531521pppmmpppmmpppmmm算法复杂度分析：算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算

10、量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。分析：设分析：设 X=“abcbdab” Y=“bdcdb”最长公共子序列是：Z=“bcdb” 子问题划分及依赖关系子问题划分及依赖关系子问题边界：子问题边界： X和和Y 起始位置为起始位置为1，X的终止位置是的终止位置是 i，Y 的的终止位置是终止位置是 j，记作，记作 Xi=，Yj=依赖关系：依赖关系： X=, Y=, Z=， Z 为为 X 和和 Y 的的 LCS，那么，那么(1)若若xi=yj，则，则zk=xi=yj，且且Zk-1是是Xi-1和和Yj-1的最长公共子序列。的

11、最长公共子序列。(2)若若xiyj且且zkxi，则则ZK是是Xi-1和和Yj的最长公共子序列。的最长公共子序列。(3)若若xiyj且且zkyj，则则Zk是是Xi和和Yj-1的最长公共子序列。的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结最优子结构性质构性质。 u由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。u用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。u其他情况下，由最

12、优子结构性质可建立递归关系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110 递推方程、决策函数递推方程、决策函数标记函数：标记函数：Bi, j, 其值为字符其值为字符 、 ，分别表示，分别表示Ci,j取得最大值时的三种情况取得最大值时的三种情况LCS(X,Y,m,n) /求最长公共子序列长度求最长公共子序列长度 for( i=1 to m) Ci,0=0 /边界边界情况情况 for( i=1 to n ) C0,i=0 for( i=1 to m ) for( j=1 to n) if (Xi=Yj) Ci,j=Ci 1,j 1+1 Bi

13、,j= else if(Ci 1,j Ci,j 1) Ci,j=Ci 1,j Bi,j= else Ci,j=Ci,j 1 Bi,j= end for(j=) Construct_Sequence(B, i, j)/输入输入：Bi,j /输出输出：X与与Y的最长公共子序列的最长公共子序列 if( i=0 or j=0 ) then return /一个序列为空一个序列为空 if (Bi,j =“ ”) 输出输出Xi Construct_Sequence (B, i1, j1) else if(Bi,j=“ ”) Construct_Sequence (B, i1, j) else Constr

14、uct_Sequence (B, i, j1) 算法的计算复杂度算法的计算复杂度计算优化函数和标记函数：时间为计算优化函数和标记函数：时间为O(mn)构造解：每一步至少缩小构造解：每一步至少缩小X 或或 Y 的长度，时间的长度，时间 (m+n）空间：空间： (mn) 输入：输入：X=, Y=，标记函数：标记函数：解：解：X2,X3, X4, X6, 即即 B, C, B, A 1234561B1,1= B1,2= B1,3= B1,4= B1,5= B1,6= 2B2,1= B2,2= B2,3= B2,4= B2,5= B2,6= 3B3,1= B3,2= B3,3= B3,4= B3,5=

15、 B3,6= 4B4,1= B4,2= B4,3= B4,4= B4,5= B4,6= 5B5,1= B5,2= B5,3= B5,4= B5,5= B5,6= 6B6,1= B6,2= B6,3= B6,4= B6,5= B6,6= 7B7,1= B7,2= B7,3= B7,4= B7,5= B7,6= kiiiaaa21),(21kiiiaaa分析：1.贪心法 构造两个实例 （5,2,8,6,3,6,9,7） （3,18,7,14,10,12,23,41,16,24） 25368679有什么规律吗？371810141216232441 （3,18,7,14,10,12,23,41,16,24） 3718101412231641242.动态规划方法 构造两个实例 （5,2,8,6,3,6,9,7） （3,18,7,14,10,12,23,41,16,24） for j = 1 to n L(j) = 1+maxL(i) | (i,j)Eend forreturn maxL(j)|j=1,2,nThere is one last issue to be cleared up: the L-values only tell us the length of the optimal subsequence, so how do we recover the sub