算法设计与分析(王佳)05动态规划

第七章动态规划,主要内容介绍,7.1一般方法和基本要素7.2最大字段和7.3每对结点间的最短路径7.4矩阵连乘问题7.5最长公共子序列问题7.6最优二叉搜索树,主要内容介绍,7.70-1背包问题7.8流水作业调度,引言,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,Thosewhocannotrememberthepastaredoomedtorepeatit.GeorgeSantayana,ThelifeofReason,BookI:IntroductionandReasoninCommonSense(1905),第七章动态规划,7.1一般方法1.多阶段决策问题多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一阶段i以后的行为仅依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这决策过程称为多阶段决策过程(multistepdecisionprocess)。最优化问题：问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。多阶段决策的最优化问题就是：求能够获得问题最优解的决策序列最优决策序列。,2.多阶段决策过程的求解策略1）枚举法穷举可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问题的新方法动态规划。动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。,3.最优性原理(PrincipleofOptimality)过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。利用动态规划求解问题的前提1)证明问题满足最优性原理如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题2)获得问题状态的递推关系式获得各阶段间的递推关系式是解决问题的关键。,Divide-and-conquer技术的问题子问题是相互独立的如果子问题不是相互独立的，分治方法将重复计算公共子问题，效率很低优化问题给定一组约束条件和一个代价函数，在解空间中搜索具有最小或最大代价的优化解很多优化问题可分为多个子问题，子问题相互关联，子问题的解被重复使用,Why?,DynamicProgramming特点把原始问题划分成一系列子问题求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间自底向上地计算适用范围一类优化问题：可分为多个相关子问题，子问题的解被重复使用,What?,使用DynamicProgramming的条件Optimalsubstructure（优化子结构）当一个问题的优化解包含了子问题的优化解时，我们说这个问题具有优化子结构。缩小子问题集合，只需那些优化问题中包含的子问题，减低实现复杂性优化子结构使得我们能自下而上地完成求解过程Subteties（重叠子问题）在问题的求解过程中，很多子问题的解将被多次使用,How?,DynamicProgramming算法的设计步骤分析优化解的结构递归地定义最优解的代价自底向上地计算优化解的代价保存之，并获取构造最优解的信息根据构造最优解的信息构造优化解,多段图问题多段图G=(V,E)是一个有向图，且具有特性:结点：结点集V被分成k2个不相交的集合Vi，1ik，其中V1和Vk分别只有一个结点：s(源结点)和t(汇点)。段：每一集合Vi定义图中的一段共k段。边：所有的边(u,v)均具有如下性质：若E，则若uVi，则uVi1,即该边将是从某段i指向i+1段，1ik1。成本：每条边(u,v)均附有成本c(u,v)。s到t的路径：是一条从第1段的源点s出发，依次经过第2段的某结点v2,i，经第3段的某结点v3,j、最后在第k段的汇点t结束的路径。该路径的成本是这条路径上边的成本和。多段图问题：求由s到t的最小成本路径。,7.1.2多段图问题,7.1.2多段图问题,1.问题的描述在多段图中求从s到t的一条最小成本的路径，可以看作是在k-2个段作出某种决策的结果。第i次决策决定Vi+1中的哪个结点在这条路径上，这里1ik-2；最优性原理对多段图问题成立,多段图问题的多阶段决策过程：生成从s到t的最小成本路径是在k-2个阶段（除s和t外）进行某种决策的过程：从s开始，第i次决策决定Vi+1(1ik-2)中的哪个结点在从s到t的最短路径上。最优性原理对多段图问题成立假设s,v2,v3,vk-1,t是一条由s到t的最短路径。初始状态：s初始决策：(s,v2)，v2V2初始决策产生的状态：v2则，其余的决策：v3,.,vk-1相对于v2将构成一个最优决策序列最优性原理成立。反证：若不然，设v2,q3,qk-1,t是一条由v2到t的更短的路径，则s,v2,q3,qk-1,t将是比s,v2,v3,vk-1,t更短的从s到t的路径。与假设矛盾。故，最优性原理成立,即，是v2v3,.,vk-1t构成从v2至t的最短路径,4.最优决策序列的表示设S0：问题的初始状态n次决策：问题需要做n次决策xi：i阶段的决策值，1in。设X1=r1,1,r1,2,r1,p1是x1可选决策值的集合，S1,j1是在选择决策值r1,j1之后所产生的状态“初始决策”所产生的状态。设1,j1是相应于状态S1,j1的最优决策序列。则，相应于S0的最优决策序列就是r1,j11,j1|1j1p1中最优的序列，记为,就一个特定的r1,j1而言,若已经做了k-1次决策，1k-1n，设x1,x2,xk-1的最优决策值是r1,r2,rk-1，所产生的状态依次为S1,S2,Sk-1。设Xk=rk,1,rk,2,rk,pk是xk可能的决策值的集合，Sk,jk是在选择决策值rk,jk之后所产生的状态,1jkpk。k,jk是相应于状态Sk,jk的最优决策序列。则，相应于Sk-1的最优决策序列是相应于S0的最优决策序列为r1,rk-1，rk,k,就一个特定的rk,jk而言,2.向前处理策略求解设P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径，COST(i,j)是这条路径的成本。1)向前递推式2)递推过程第k-1段c(j,t)ECOST(k-1,j)=,l1,l2,.,lpi+1,t,j,Vi,Vi+1,各递推结果第4段COST(4,9)=c(9,12)=4COST(4,10)=c(10,12)=2COST(4,11)=c(11,12)=5第3段COST(3,6)=min6+COST(4,9),5+COST(4,10)=7COST(3,7)=min4+COST(4,9),3+COST(4,10)=5COST(3,8)=min5+COST(4,10),6+COST(4,11)=7第2段COST(2,2)=min4+COST(3,6),2+COST(3,7),1+COST(3,8)=7COST(2,3)=9COST(2,4)=18COST(2,5)=15第1段COST(1,1)=min9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)=16S到t的最小成本路径的成本16,最小成本路径的求取记D(i,j)每一COST(i,j)的决策即，使c(j,l)+COST(i+1,l)取得最小值的l值。例：D(3,6)=10,D(3,7)=10D(3,8)=10D(2,2)=7,D(2,3)=6,D(2,4)=8,D(2,5)=8D(1,1)=2根据D(1,1)的决策值向后递推求取最小成本路径：v2=D(1,1)=2v3=D(2,D(1,1)=7v4=D(3,D(2,D(1,1)=D(3,7)=10故由s到t的最小成本路径是：1271012,3)算法描述结点的编号规则源点s编号为1,然后依次对V2、V3Vk-1中的结点编号，汇点t编号为n。目的：使对COST和D的计算仅按n-1,n-2,1的次序计算即可，无需考虑标示结点所在段的第一个下标。算法描述,算法7.1多段图的向前处理算法procedureFGRAPH(E,k,n,P)/输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c(i,j)是边的成本。P(1:k)带出最小成本路径/realCOST(n);integerD(n-1),P(k),r,j,k,nCOST(n)0forjn-1to1by-1do/计算COST(j)/设r是具有性质：E且使c(j,r)+COST(r)取最小值的结点COST(j)c(j,r)+COST(r)D(j)r/记录决策值/repeatP(1)1;P(k)nforj2tok-1do/找路径上的第j个结点/P(j)D(P(j-1)/回溯求出该路径/repeatendFGRAPH,算法的时间复杂度若G采用邻接表表示，总计算时间为：,3.向后处理策略求解设BP(i,j)是一条从源点s到Vi中的结点j的最小成本路径，BCOST(i,j)是这条路径的成本。1)向后递推式2)递推过程第2段c(1,j)ECOST(2,j)=,各递推结果第2段BCOST(2,2)=9BCOST(2,3)=7BCOST(2,4)=3BCOST(2,5)=2第3段BCOST(3,6)=minBCOST(2,2)+4,BCOST(2,3)+2=9BCOST(3,7)=minBCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11=11BCOST(3,8)=minBCOST(2,4)+11,BCOST(2,5)+8=10第4段BCOST(4,9)=minBCOST(3,6)+6,BCOST(3,7)+4=15BCOST(4,10)=minBCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5=14BCOST(4,11)=minBCOST(3,8)+6=16第5段BCOST(5,12)=minBCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5=16S到t的最小成本路径的成本16,最小成本路径的求取记BD(i,j)每一COST(i,j)的决策即，使COST(i-1,l)+c(l,j)取得最小值的l值。例：BD(3,6)=3,BD(3,7)=2,BD(3,8)=5BD(4,9)=6,BD(4,10)=7,BD(4,11)=8BD(5,12)=10根据D(5,12)的决策值向前递推求取最小成本路径：v4=BD(5,12)=10v3=BD(4,BD(5,12)=7v2=BD(3,BD(4,BD(5,12)=BD(3,7)=2故由s到t的最小成本路径是：1271012,算法7.2多段图的向后处理算法procedureBGRAPH(E,k,n,P)/输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c(i,j)是边的成本。P(1:k)带出最小成本路径/realBCOST(n);integerBD(n-1),P(k),r,j,k,nBCOST(1)0forj2tondo/计算BCOST(j)/设r是具有E且使BCOST(r)+c(r,j)取最小值性质的结点BCOST(j)BCOST(r)+c(r,j)BD(j)r/记录决策值/repeatP(1)1;P(k)nforjk-1to2by-1do/找路径上的第j个结点/P(j)D(P(j+1)/回溯求出该路径/repeatendBGRAPH,4.多段图问题的应用实例资源的分配问题将n个资源分配给r个项目的问题：如果把j个资源，0jn，分配给项目i，可以获得N(i,j)的净利。问题：如何将这n个资源分配给r个项目才能使各项目获得的净利之和达到最大。转换成一个多段图问题求解。,用r1段图描述该问题：段：1到r之间的每个段i表示项目i。结点：i=1时，只有一个结点源点s=V(1,0)当2ir时，每段有n+1个结点，每个结点具有形式V(i,j)：表示到项目i之前为止，共把j个资源分配给了前i-1个项目，j=0,1,n。汇点t=V(r+1,n)边的一般形式：,jl,1ir成本：当jl且1ir时，边赋予成本N(i,l-j),表示给项目i分配l-j个资源所可能获得的净利。当jn且i=r时，此时的边为：,该边赋予成本：,指向汇点的边,注，并不是分给的资源越多，得到的净利就越大,实例：将4个资源分配给3个项目。构成一个4段图。问题的解：资源的最优分配方案由一条s到t的最大成本路径给出改变边成本的符号，从而将问题转换成为求取最小成本路径问题。,7.2最大子段和,问题描述：给定由n个整数（包含负整数）组成的序列a1,a2,.,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。依此定义，所求的最优值为：例如，当(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)时，最大子段和为：,1.一个简单算法,一个简单算法：intMaxSum(intn,a,算法有3重循环，复杂性为O(n3)。,由于有：算法可作如下改进：intMaxSum(intn,a,改进后的算法复杂性为O(n2)。,2.分治方法求解,从问题的解的结构可以看出，它适合于用分治策略求解：如果将所给的序列a1:n分为长度相等的两段a1:n/1和an/2+1:n，分别求出这两段的最大子段和，则a1:n的最大子段和有三种情形：a1:n的最大子段和与a1:n/2的最大子段和相同；a1:n的最大子段和与an/2+1:n的最大子段和相同；a1:n的最大子段和为下面的形式。A、B这两种情形可递归求得。对于情形C，容易看出，an/2与an/2+1在最优子序列中。因此，我们可以在a1:n/2和an/2+1:n中分别计算出如下的s1和s2。则s1+s2即为出现情形C使得最优值。从而设计出下面所示的分治算法。,intMaxSubSum(inta,intleft,intright)intsum=0;if(left=right)sum=aleft0?aleft:0;elseintcenter=(left+right)/2;intleftsum=MaxSubSum(a,left,center);intrightsum=MaxSubSum(a,center+1,right);ints1=0;lefts=0;for(inti=center;i=left;i-)lefts+=ai;if(leftss1)s1=lefts;ints2=0;rights=0;for(inti=center+1;is2)s2=rights;sum=s1+s2;if(sumsum)sum=b;returnsum;显然该算法的计算时间为O(n)。,4.算法的推广,最大矩阵和问题，略最大m子段和问题，略,7.3每对结点之间的最短路径,1.问题描述设G=(V,E)是一个有n个结点的有向图，C是G的成本邻接矩阵，C中元素有：0，ijc(i,j)=边的成本，ij且E(G)，ij且其中，1i，jn每对结点之间的最短路径问题：求满足下述条件的矩阵A，A中的任一元素A(i,j)代表结点i到结点j的最短路径长度。,分析：利用单源最短路径算法求解计算n个结点的单源最短路径。时间复杂度：(n3)利用动态规划策略求解将求解G中每对结点之间的最短路径问题转化成一个多阶段决策过程。决策什么？最优性原理对于该问题是否成立？,2.动态规划求解策略1）最优性原理对于每对结点之间的最短路径问题成立对G的一条由i到j的最短路径（假设该路径中不包含环），设k是该路径上的一个中间结点：i,.,k,j由i到k的最短路径k是中间结点由k到i的最短路径则，由i到k和k到j的两条子路径将分别是由i到k和由k到j的最短路径。（反证，否则i,.,k,j也将不是由i到j的最短路径）故，最优性原理对于该问题成立。,2）多阶段决策过程所有n个结点从1到n依次编号。设k是由i到j的最短路径上编号最高的中间结点：i,.,k,jk是编号最高的中间结点则由i到k的子路径上将不会有比编号k-1更大的结点；同理，由k到j的子路径上也将不会有比编号k-1更大的结点。构造多阶段决策过程：对由i到j的最短路径，首先决策哪一个结点是该路径上具有最大编号的中间结点k，然后再去求取由i到k和由k到j的最短路径其中应不包含比k-1还大的中间结点。,3）递推关系式记Ak(i,j)表示从i到j并且不经过比k还大的结点的最短路径长度。则，A(i,j)=An(i,j)即，由i到j的最短路径不通过编号比n还大的结点。注：该路径可以经过结点n，也可以不经过结点n。若该路径经过结点n，则An(i,j)An-1(i,n)+An-1(n,j)若该路径不经过结点n，则An(i,j)An-1(i,j)故可得，An(i,j)=minAn-1(i,j)，An-1(i,n)+An-1(n,j)不经过n结点经过n结点,对任意的k，k1，有，Ak(i,j)=minAk-1(i,j)，Ak-1(i,k)+Ak-1(k,j)不经过结点k刚好经过结点k初值：A0(i,j)=C(i,j)，1in，1jn递推计算：A1(i,j),A2(i,j),An(i,j)=A(i,j),3.算法描述算法7.3每对结点之间的最短路径长度procedureALL-PATHS(COST,A,n)/COST(n,n)是n结点图的成本邻接矩阵；A(i,j)是结点vi到vj的最短路径的成本；COST(i,i)=0,1in/integerI,j,k,n;realCOST(n,n),A(n,n)fori1tondoforj1tondoA(i,j)COST(i,j)/用COST(i,j)对A0赋初值/repeatrepeatfork1tondofori1tondoforj1tondoA(i,j)minA(i,j)，A(i,k)+A(k,j)repeatrepeatrepeatendALL-PATHS,算法的设计说明1）Ak(i,k)=Ak-1(i,k)Ak(k,j)=Ak-1(k,j),ik且kj,则有Ak(i,j)minAk-1(i,j),Ak(i,k)+Ak-1(k,j),在第i-1到第i次的迭代过程中，A的第k行、第k列元素不变,ki且jk,则有Ak(i,j)minAk-1(i,j),Ak-1(i,k)+Ak(k,j),ki且kj,则有Ak(i,j)minAk-1(i,j),Ak(i,k)+Ak(k,j),Ak(i,j)minAk-1(i,j),Ak(i,k)+Ak-1(k,j)Ak(i,j)minAk-1(i,j),Ak-1(i,k)+Ak(k,j)Ak(i,j)minAk-1(i,j),Ak(i,k)+Ak(k,j)Ak(i,j)minAk-1(i,j),Ak-1(i,k)+Ak-1(k,j)在算法的计算过程中取消了A的上标，并保证了每次计算的Ak(i,j)即为minAk-1(i,j),Ak-1(i,k)+Ak-1(k,j)2）如何求每对结点之间的路径？,例7.3有向图如图所示,求图中所有结点间最短路径的成本矩阵,注：A(i,j)=表明G中从i到j没有有向路径,性能分析计算时间注：该时间与A的值无关：fork1tondo迭代n次fori1tondo迭代n次forj1tondo迭代n次A(i,j)minA(i,j)，A(i,k)+A(k,j)repeatrepeatrepeat,7.4矩阵连乘问题,给定n个矩阵A1,A2,.,An，其中Ai与Ai+1是可乘的，i=1,2,.,n-1。考察这n个矩阵的连乘积A1A2.An。由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。,7.4矩阵连乘问题,完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。,7.4矩阵连乘问题,设有四个矩阵A,B,C,D，它们的维数分别是：A=5010，B=1040，C=4030，D=305总共有五种完全加括号的方式：(A(BC)D)(A(B(CD)(AB)(CD)(AB)C)D)(A(BC)D)其数乘次数分别为：16000,10500,36000,87500,34500,7.4.1穷举搜索法,问题描述：给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,7.4.1穷举搜索法,算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：P(n)是随n的增长成指数增长的。,动态规划法1.分析最优解的结构,预处理：将矩阵连乘积A1A2.An简记为Ai:j，这里ij。考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为（A1A2.Ak）（Ak+1Ak+2.An）。计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量。,动态规划法1.分析最优解的结构,分析最优解的结构特征：计算Ai:j的最优次序所包含的计算矩阵子链Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,2.建立递归关系,设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n。当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n。当ij时，mi,j=mi,k+mk+1,j+pi-1pkpj，这里Ai的维数为pi-1pi。可以递归地定义mi,j为：k的位置只有j-1种可能。,3.计算最优值,对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。,7.3.3矩阵连乘算法算法描述,【程序73】矩阵连乘算法classMatrixChainpublic:MatrixChain(intmSize,int*q);intMChain();intLookupChain();voidTraceback();,private:voidTraceback(inti,intj);intLookupChain(inti,intj);int*p,*m,*s,n;,intMatrixChain:MChain()/求A0:n-1的最优解值for(inti=0;in;i+)mii=0;,for(intr=2;r=n;r+)for(inti=0;i=n-r;i+)intj=i+r-1;mij=mi+1j+pi*pi+1*pj+1;sij=i;for(intk=i+1;kj;k+)intt=mik+mk+1j+pi*pk+1*pj+1;if(tmij)mij=t;sij=k;returnm0n-1;,voidMatrixChain:Traceback(inti,intj)if(i=j)coutAi;return;if(isij)cout(;Traceback(i,sij);if(isij)cout);if(sij+1j)cout(;Traceback(sij+1,j);if(sij+1j)cout);voidMatrixChain:Traceback()cout(;Traceback(0,n-1);cout);cout0)returnmij;if(i=j)return0;intu=LookupChain(i，i)+LookupChain(i+1，j)+pi-1*pi*pj;sij=i;for(intk=i+1;kj;k+)intt=LookupChain(i，k)+LookupChain(k+1，j)+pi-1*pk*pj;if(tu)u=t;sij=k;mij=u;returnu;算法复杂性：T(n)=O(n3),关于动态规划算法和备忘录方法的适用条件,矩阵连乘积的最优计算次序问题可用自顶向下的备忘录方法或自底向上的动态规划算法在O(n3)计算时间内求解。这两个算法都利用了子问题重叠性质。总共有(n2)个不同的子问题，对每个子问题两种算法都只解一次并记录答案。当再次遇到该子问题时，简单地取用已得到的答案，节省了计算量，提高了算法的效率。,关于动态规划算法和备忘录方法的适用条件,适用条件：一般来说，当一个问题的所有子问题都至少要解一次时，用动态规划算法比用备忘录方法好。此时，动态规划算法没有任何多余的计算，还可以利用其规则的表格存取方式来减少在动态规划算法中的计算时间和空间需求。当子问题空间中部分子问题可以不必求解时，易用备忘录方法则较为有利，因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题。,7.5LongestCommonSusequence,问题的定义最长公共子序列(LCS)结构分析建立求解LCS长度的递归方程自底向上LCS长度的计算构造优化解,定义：若给定序列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的最长公共子序列。,最长公共子序列（LCS）问题输入：X=(x1,x2,.,xn)，Y=(y1,y2,.ym)输出：Z=X与Y的最长公共子序列,最长公共子序列结构分析,第i前缀设X=(x1,x2,.,xn)是一个序列，X的第i前缀Xi是一个序列，定义为Xi=(x1,.,xi)例.X=(A,B,D,C,A),X1=(A),X2=(A,B),X3=(A,B,D),优化子结构定理1（优化子结构）设X=(x1,.,xm)、Y=(y1,.,yn)是两个序列，Z=(z1,.,zk)是X与Y的LCS，我们有：如果xm=yn,则zk=xm=yn,Zk-1是Xm-1和Yn-1的LCS，即，LCSXY=LCSXm-1Yn-1+.如果xmyn，且zkxm，则Z是Xm-1和Y的LCS，即LCSXY=LCSXm-1Y如果xmyn,且zkyn,则Z是X与Yn-1的LCS，即LCSXY=LCSXYn-1,最长公共子序列的结构,设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，则若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,证明:.X=,Y=，则LCSXY=LCSXm-1Yn-1+.设zkxm，则可加xm=yn到Z，得到一个长为k+1的X与Y的公共序列，与Z是X和Y的LCS矛盾。于是zk=xm=yn。现在证明Zk-1是Xm-1与Yn-1的LCS。显然Zk-1是Xm-1与Yn-1的公共序列。我们需要证明Zk-1是LCS。设不然，则存在Xm-1与Yn-1的公共子序列W，W的长大于k-1。增加xm=yn到W，我们得到一个长大于k的X与Y的公共序列，与Z是LCS矛盾。于是，Zk-1是Xm-1与Yn-1的LCS.,X=,Y=，xmyn，zkxm，则LCSXY=LCSXm-1Y由于zkxm，Z是Xm-1与Y的公共子序列。我们来证Z是Xm-1与Y的LCS。设Xm-1与Y有一个公共子序列W，W的长大于k,则W也是X与Y的公共子序列，与Z是LCS矛盾。同可证。,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中，Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：,计算最优值,由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。voidLCSLength(intm，intn，char*x，char*y，int*c，int*b)inti，j;for(i=1;i=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;,构造最长公共子序列,算法描述：voidLCS(inti，intj，char*x，int*b)if(i=0|j=0)return;if(bij=1)LCS(i-1，j-1，x，b);coutT00(左子树），T11(右子树）T24=3=T22(左子树），T34(右子树）T34=4=T33(左子树），T44(右子树）,j,i,树的形态,3.计算时间当j-i=m时，有n-m+1个C(i,j)要计算C(i,j)的计算：(m)每个C(i,j)要求找出m个量中的最小值。则，n-m+1个C(i,j)的计算时间：(nm-m2)对所有可能的m，总计算时间为：一种改进措施（克努特）：最优的kR(i,j-1),R(i+1,j)DonaldE.KnuthOptimumbinarysearchtreesActaInformation1971,4.算法描述procedureOBST(P,Q,n)/给定n个标识符a1a2an。已知成功检索的概率P(i),不成功检索概率Q(i),0in。算法对于标识符ai+1,aj计算最优二分检索树Tij的成本C(i,j)、根R(i,j)、权W(i,j)/realP(1:n),Q(1:n),C(0:n,0:n),W(0:n,0:n);integerR(0:n,0:n)fori0ton-1do(W(i,i),R(i,i),C(i,i)(Q(i),0,0)/置初值/(W(i,i+1),R(i,i+1),C(i,i+1)(Q(i)+Q(i+1)+P(i+1),i+1,Q(i)+Q(i+1)+P(i+1)repeat/含有一个结点的最优树/(W(n,n),R(n,n),C(n,n)(Q(n),0,0)form2tondofori0ton-mdoji+mW(i,j)W(i,j-1)+P(j)+Q(j)k区间R(i,j-1),R(i+1,j)中使C(i,l-1)+C(l,j)取最小值的l值/Knuth结论/C(i,j)W(i,j)+C(i,k-1)+C(k,j)R(i,j)krepeatrepeatendOBST,OBST算法的计算时间:(n2),对满足动态规划最优性原理的多阶段决策问题有，当问题的一决策序列为最优时，其中任何一段子序列相对于该子序列所对应的子问题构成该子问题的最优解。但对有些多阶段决策问题，尽管存在问题的最优决策序列，但最优性原理并不一定成立（从而也就不能用动态规划策略求解）。试举例说明。,1.问题描述1)KNAP(1,j,X)目标函数：约束条件：0/1背包问题：KNAP(1,n,M)最优性原理对于0/1背包问题成立求解策略：向前递推、向后递推,7.70/1背包问题,2)向后递推关系式记fj(X)是KNAP(1,j,X)的最优解，则fn(M)有fn(M)=maxfn-1(M),fn-1(M-wn)+pn对于任意的fi(X)，i0,有fi(X)=maxfi-1(X),fi-1(X-wi)+pi递推过程：初始值0X0f0=X0求出fi在所有可能的X取值情况下的值。fn(M)=KNAP(1,n,M),例7.11背包问题n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6递推计算过程X0f0(X)=0X0X0f1(X)=max0,+1=00X2max0,0+1=1X2X0max0,+3=00X2f2(X)=max1,+3=12X3max1,0+2=23X5max1,1+2=3X5f3(M)=max3,1+5=6M=6,尽管X0,但还不足以装下w1,解向量的推导f3(M)=6x3=1P=6-p3=1KNAP(1,3,6)=6M=6-w3=2X=(1,0,1)f2(M)=1x2=0f1(M)=1x1=1,f1,f2,f3计算过程的图解,i:fi-1(x-wi)+pi,i=0:函数不存在,注：fi-1(X-wi)+pi曲线的构造：将fi-1(X)的曲线在X轴上右移wi个单位，然后上移pi个单位而得到；fi(X)曲线的构造：由fi-1(X)和fi-1(X-wi)+pi的曲线按X相同时f取大值的规则归并而成,2.序偶表示记fi的序偶集合为Si=(Pj,Wj)|Wj是fi曲线中使得fi产生一次阶跃的X值，0jr即Pj=fi(Wj)，r是阶跃点个数(P0,W0)=(0,0)若共有r个阶跃值，则分别对应r个(Pj,Wj)序偶，1jr若WjWj+1,则PjPj+1，0jr若WjXWj+1，fi(X)=fi(Wj)若XWr，fi(X)=fi(Wr),fi是关于X的阶跃函数,Si的构造记是fi-1(X-wj)+pj的所有序偶的集合，则其中，Si-1是fi-1的所有序偶的集合Si的构造：由Si-1和按照支配规则合并而成。支配规则：如果Si-1和之一有序偶(Pj,Wj),另一有(Pk,Wk)，且有WjWk,PjPk，则序偶(Pj,Wj)将被舍弃。（即取最大值规则）。注：Si中的序偶是背包问题KNAP(1,i,X)在X各种取值下子问题的最优解,例7.12例7.11的序偶计算S0=(0,0)=(1,2)S1=(0,0),(1,2)=(2,3),(3,5)S2=(0,0),(1,2),(2,3),(3,5)=(5,4),(6,6),(7,7),(8,9)S3=(0,0),(1,2),(2,3),(5,4),(6,6),(7,7),(8,9)注：序偶(3,5)被(5,4)“支配”而删除,KNAP(1,n,M)问题的解决策序列的求取Sn是KNAP(1,n,X)在0XM各种取值下的最优解KNAP(1,n,M)的最优解由Sn的最后一对有效序偶给出。xi的推导xn:设Sn的最后一对有效序偶是(P1,W1)，W1M，则(P1,W1)或者是Sn1的最末一对序偶，或者是(Pj+pn,Wj+wn)，其中(Pj,Wj)Sn1且Wj是Sn1中满足Wj+wnM的最大值。若(P1,W1)Sn1，则Xn0；否则，(P1pn,W1-wn)Sn1，Xn1xn-1:若xn=0，则判断(P1,W1)Sn2？，以确定Xn-1的值若xn=1，则依据(P1pn,W1-wn)Sn2？，以判断Xn-1的值xn-2,x1将依次推导得出,例7.13（例7.12)S0=(0,0)S1=(0,0),(1,2)S2=(0,0),(1,2),(2,3),(3,5)S3=(0,0),(1,2),(2,3),(5,4),(6,6),(7,7),(8,9)M=6，f3(6)由S3中的序偶(6,6)给出。1)(6,6)S2x3=12)(6-p3,6-w3)=(1,2)S2且(1,2)S1x2=03)(1,2)S0x1=1,算法7.6非形式的背包算法procedureDKP(p,w,n,M)S0(0,0)fori1ton-1do(P1,W1)|(P1-pi,W1-wi)Si-1andW1M/生成/SiMERGE-PURGE(Si-1,)/将Si-1和归并为Si/repeat(PX,WX)Sn-1的最末一个有效序偶(PY,WY)(P1pn,W1+wn)，其中，W1是Sn-1中使得WwnM的所有序偶中取最大值得W/沿Sn-1,S1回溯确定xn,xn-1,x1的取值/ifPXPYthenxn0/PX将是Sn的最末序偶/elsexn1/PY将是Sn的最末序偶/endif回溯确定xn-1,x1endDKP,3.DKP的实现,1)序偶集Si的存储结构使用两个一维数组P和W存放所有的序偶(P1,W1),其中P存放P1值，W存放W1值序偶集S0,S1,Sn-1顺序、连续地存放于P和W中；用指针F(i)表示Si中第一个元素在数组(P,W)中的下标位置，0in;F(n)Sn-1中最末元素位置11234567P0010123W0020235F(0)F(1)F(2)F(3),2)序偶的生成与合并Si的序偶将按照P和W的递增次序生成中序偶的生成将与和Si-1的合并同时进行设生成的下一序偶是(PQ,WQ)；对所有的(PQ,WQ)，根据支配规则处理如下：将Si-1中所有W值小于WQ的序偶直接计入Si中；根据支配规则，若Si-1中有W值小于WQ的序偶支配(PQ,WQ)，则(PQ,WQ)将被舍弃，否则(PQ,WQ)计入Si中；并清除Si-1中所有可被支配的序偶，这些序偶有WWQ且PPQ对所有的(PQ,WQ)重复上述处理；将最后Si-1中剩余的序偶直接计入Si中；所有计入Si中的新序偶依次存放到由F(i)指示的Si的存放位置上。注：不需要存放的专用空间,3)算法的实现算法4.70/1背包问题的算法描述procedureDKNAP(p,w,n,M,m)realp(n),w(n),P(m),W(m),pp,ww,M；integerF(0:n),l,h,u,i,j,p,nextF(0)1;P(1)W(1)0/S0/lh1/S0的首端和末端；l是Si-1的首端，h是Si-1的末端/F(1)next2/P和W中第一个空位；next指示P/W中可以存放(P,W)序偶的第一个位置fori1ton-1do/生成Si/klu在lrh中使得W(r)+wiM的最大r/u指示由Si-1生成的最大有效位置/forjltoudo/生成，同时进行归并/(pp,ww)(P(j)+pi,W(j)+wi)/生成中的下一个元素/whilekhandW(k)wwdo/从Si-1中取元素并归并/P(next)P(k);W(next)W(k)/所有W(k)ww的序偶直接归并nextnext+1;kk1repeat,/按照支配规则考虑(pp,ww)及Si-1中的序偶/ifkhandW(k)=wwthenppmax(pp,P(k)kk+1endififppP(next-1)then(P(next),W(next)(pp,ww)nextnext+1endif/清除Si-1中的序偶/whilekhandP(k)P(next-1)dokk+1repeatrepeat/在并入中的所有序偶之后，将Si-1中剩余的元素并入Si/whilekhdo(P(next),W(next)(P(k),W(k)nextnext+1;kk+1repe