第3章 动态规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,3,章 动态规划,1,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,2,算法总体思想,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,3,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,算法总体思想,n,T(n),=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),4,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,算法总体思想,n,=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,n/2,T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),T(n/4),T(n),Those who cannot remember the past are doomed to repeat it.,-George,Santayana,The life of Reason,Book I:Introduction and,Reason in Common,Sense(1905),5,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。,递归地定义最优值。,以自底向上的方式计算出最优值。,根据计算最优值时得到的信息，构造最优解。,6,完全加括号的矩阵连乘积,（,1,）单个矩阵是完全加括号的；,（,2,）矩阵连乘积 是完全加括号的，则 可,表示为,2,个完全加括号的矩阵连乘积 和,的乘积并加括号，即,16000,10500,36000,87500,34500,完全加括号的矩阵连乘积可递归地定义为：,设有四个矩阵 ，它们的维数分别是：,总共有五中完全加括号的方式,7,矩阵连乘问题,给定,n,个矩阵 ，其中 与 是可乘的，。考察这,n,个矩阵的连乘积,由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。,若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用,2,个矩阵相乘的标准算法计算出矩阵连乘积,8,矩阵连乘问题,给定,n,个矩阵,A,1,A,2,A,n,，其中,A,i,与,A,i,+1,是可乘的，,i=1,2,n-1,。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。,穷举法,：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：,对于,n,个矩阵的连乘积，设其不同的计算次序为,P(n),。,由于每种加括号方式都可以分解为两个子矩阵的加括号问题：,(A,1,.,A,k,)(,A,k,+1A,n,),可以得到关于,P(n),的递推式如下：,9,矩阵连乘问题,穷举法,动态规划,将矩阵连乘积 简记为,Ai:j,，这里,i,j,考察计算,Ai:j,的最优计算次序。设这个计算次序在矩阵,Ak,和,Ak,+1,之间将矩阵链断开，,i,kj,，则其相应完全,加括号方式为,计算量：,Ai:k,的计算量加上,Ak+1:j,的计算量，再加上,Ai:k,和,Ak+1:j,相乘的计算量,10,分析最优解的结构,特征：计算,Ai:j,的最优次序所包含的计算矩阵子链,Ai:k,和,Ak+1:j,的次序也是最优的。,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为,最优子结构性质,。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,11,建立递归关系,设计算,Ai:j,，,1ijn,，所需要的最少数乘次数,mi,j,，则原问题的最优值为,m1,n,当,i=j,时，,Ai:j=Ai,，因此，,mi,i=0,，,i=1,2,n,当,ij,时，,可以递归地定义,mi,j,为：,这里 的维数为,的位置只有,种,可能,12,计算最优值,对于,1ijn,不同的有序对,(i,j),对应于不同的子问题。因此，不同子问题的个数最多只有,由此可见，在递归计算时，,许多子问题被重复计算多次,。这也是该问题可用动态规划算法求解的又一显著特征。,用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法,13,用动态规划法求最优解,public static void,matrixChain,(,int,p,int,m,int,s),int,n=p.length-1;,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=j),return,0;,int,u=,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;,17,最长公共子序列,若给定序列,X=x,1,x,2,x,m,，则另一序列,Z=z,1,z,2,z,k,，是,X,的子序列是指存在一个严格递增下标序列,i,1,i,2,i,k,使得对于所有,j=1,2,k,有：,z,j,=,x,i,j,。例如，序列,Z=B,，,C,，,D,，,B,是序列,X=A,，,B,，,C,，,B,，,D,，,A,，,B,的子序列，相应的递增下标序列为,2,，,3,，,5,，,7,。,给定,2,个序列,X,和,Y,，当另一序列,Z,既是,X,的子序列又是,Y,的子序列时，称,Z,是序列,X,和,Y,的,公共子序列,。,给定,2,个序列,X=x,1,x,2,x,m,和,Y=y,1,y,2,y,n,，找出,X,和,Y,的最长公共子序列。,18,最长公共子序列的结构,设序列,X=x,1,x,2,x,m,和,Y=y,1,y,2,y,n,的最长公共子序列为,Z=z,1,z,2,z,k,，则,(1),若,x,m,=,y,n,，则,z,k,=,x,m,=,y,n,，且,z,k,-1,是,x,m,-1,和,y,n,-1,的最长公共子序列。,(2),若,x,m,y,n,且,z,k,x,m,，则,Z,是,x,m,-1,和,Y,的最长公共子序列。,(3),若,x,m,y,n,且,z,k,y,n,，则,Z,是,X,和,y,n,-1,的最长公共子序列。,由此可见，,2,个序列的最长公共子序列包含了这,2,个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有,最优子结构性质,。,19,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用,cij,记录序列和的最长公共子序列的长度。其中，,X,i,=x,1,x,2,x,i,；,Yj,=y,1,y,2,y,j,。当,i=0,或,j=0,时，空序列是,X,i,和,Y,j,的最长公共子序列。故此时,Cij=0,。其他情况下，由最优子结构性质可建立递归关系如下：,20,计算最优值,由于在所考虑的子问题空间中，总共有,(,mn,),个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,Algorithm,lcsLength,(x,y,b),1:m,x.length-1;,2:n,y.length-1;,3:ci0=0;c0i=0;,4:,for,(,int,i=1;i=m;i+),5:,for,(,int,j=1;j=cij-1),10:cij=ci-1j;,11:bij=2;,12:,else,13:cij=cij-1;,14:bij=3;,构造最长公共子序列,Algorithm,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);,System.out.,print,(xi);,else if,(bij=2),lcs,(i-1,j,x,b);,else,lcs,(i,j-1,x,b);,21,算法的改进,在算法,lcsLength,和,lcs,中，可进一步将数组,b,省去。事实上，数组元素,cij,的值仅由,ci-1j-1,，,ci-1j,和,cij-1,这,3,个数组元素的值所确定。对于给定的数组元素,cij,，可以不借助于数组,b,而仅借助于,c,本身在时间内确定,cij,的值是由,ci-1j-1,，,ci-1j,和,cij-1,中哪一个值所确定的。,如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算,cij,时，只用到数组,c,的第,i,行和第,i-1,行。因此，用,2,行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至,O(min(m,n),。,22,凸多边形最优三角剖分,用多边形顶点的逆时针序列表示凸多边形，即,P=v,0,v,1,v,n,-1,表示具有,n,条边的凸多边形。,若,v,i,与,v,j,是多边形上不相邻的,2,个顶点，则线段,v,i,v,j,称为多边形的一条弦。弦将多边形分割成,2,个多边形,v,i,v,i+1,v,j,和,v,j,v,j,+1,v,i,。,多边形的三角剖分,是将多边形分割成互不相交的三角形的弦的集合,T,。,给定凸多边形,P,，以及定义在由多边形的边和弦组成的三角形上的权函数,w,。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。,23,三角剖分的结构及其相关问题,一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积,(A,1,(A,2,A,3,)(A,4,(A,5,A,6,),所相应的语法树如图,(a),所示。,凸多边形,v,0,v,1,v,n,-1,的三角剖分也可以用语法树表示。例如，图,(b),中凸多边形的三角剖分可用图,(a),所示的语法树表示。,矩阵连乘积中的每个矩阵,A,i,对应于凸,(n+1),边形中的一条边,v,i-1,v,i,。三角剖分中的一条弦,v,i,v,j,，,ij,，对应于矩阵连乘积,Ai+1:j,。,24,最优子结构性质,凸多边形的最优三角剖分问题有最优子结构性质。,事实上，若凸,(n+1),边形,P=v,0,v,1,v,n,-1,的最优三角剖分,T,包含三角形,v,0,v,k,v,n,，,1kn-1,，则,T,的权为,3,个部分权的和：三角形,v0vkvn,的权，子多边形,v,0,v,1,v,k,和,v,k,v,k,+1,v,n,的权之和。可以断言，由,T,所确定的这,2,个子多边形的三角剖分也是最优的。因为若有,v,0,v,1,v,k,或,v,k,v,k,+1,v,n,的更小权的三角剖分将导致,T,不是最优三角剖分的矛盾。,25,最优三角剖分的递归结构,定义,tij,，,1ijn,为凸子多边形,vi-1,vi,vj,的最优三角