*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,递归、分治、动态规划与回溯,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许屡次。,动态规划思想,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),如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以防止大量重复计算，从而得到多项式时间算法。,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),动态规划思想,动态规划根本步骤,找出最优解的性质，并刻划其结构特征。,递归地定义最优值。,以自底向上的方式计算出最优值。,根据计算最优值时得到的信息，构造最优解。,动态规划算法的根本要素,一、最优子结构,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为,最优子结构性质,。,在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。,利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。,注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快空间占用小，问题的维度低,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算屡次。这种性质称为子问题的重叠性质。,动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。,通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,三、备忘录方法,备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，防止了相同子问题的重复求解。,m,0,private static int,lookupChain,(int i,int j),if,(mij 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;,最长公共子序列,假设给定序列X=x1,x2,xm，那么另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列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=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。,最长公共子序列的结构,设序列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个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有,最优子结构性质,。,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用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。其他情况下，由最优子结构性质可建立递归关系如下：,计算最优值,由于在所考虑的子问题空间中，总共有(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);,算法的改进,在算法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)。,0-1背包问题,给定n种物品和一背包。物品i的重量是w,i,，其价值为v,i,，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?,0-1背包问题是一个特殊的整数规划问题。,0-1背包问题,设所给0-1背包问题的子问题,的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。,算法复杂度分析：,从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c2,n,时，算法需要,(n2,n,)计算时间。,完全加括号的矩阵连乘积,（1）单个矩阵是完全加括号的；,（2）矩阵连乘积 是完全加括号的，则 可,表示为2个完全加括号的矩阵连乘积 和,的乘积并加括号，即,16000,10500,36000,87500,34500,完全加括号的矩阵连乘积可递归地定义为：,设有四个矩阵 ，它们的维数分别是：,总共有五中完全加括号的方式,矩阵连乘问题,给定n个矩阵 ，其中 与 是可乘的，。考察这n个矩阵的连乘积,由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。,假设一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，那么可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,矩阵连乘问题,给定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)的递推式如下：,矩阵连乘问题,穷举法,动态规划,将矩阵连乘积 简记为Ai:j，这里i,j,考察计算Ai:j的最优计算次序。设这个计算次序在矩阵,Ak和Ak+1之间将矩阵链断开，ikj，那么其相应完全,加括号方式为,计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上,Ai:k和Ak+1:j相乘的计算量,建立递归关系,设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，那么原问题的最优值为m1,n,当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n,当ij时，,可以递归地定义mi,j为：,这里 的维数为,的位置只有,种,可能,计算最优值,对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有,由此可见，在递归计算时，许多子问题被重复计算屡次。这也是该问题可用动态规划算法求解的又一显著特征。,用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而防止大量的重复计算，最终得到多项式时间的算法,用动态规划法求最优解,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 mij),mij=t;,sij=k;,A1,A2,A3,A4,A5,A6,30,35,35,15,15,5,5,10,10,20,20,25,算法复杂度分析：,算法,matrixChain,的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n,3,)。因此算法的计算时间上界为O(n,3,)。算法所占用的空间显然为O(n,2,)。,分析最优解的结构,特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为,最优子结构性质,。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,凸多边形最优三角剖分,用多边形顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1表示具有n条边的凸多边形。,假设vi与vj是多边形上不相邻的2个顶点，那么线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。,多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。,给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。,三角剖分的结构及其相关问题,一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积,(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),边形中的