[6]动态规划策略

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,动 态 规 划,1,例,1,：求出从,顶点,1,点到,顶点,7,点的最短路径,方法？,一、导言,2,最优性原理,根据穷举法，,(1,3,5,7),为优化解。,优化原理指：相对于初始决策,1,3,造成的问题状态，（,3,，,5,，,7,）必须是,3,到,7,的最短路。否则（,1,，,3,，,5,，,7,）也不可能是优化的。,无论第一步决策取,2,3,4,中那一节点，其后的决策序列必须是该节点到目的节点的最短路,节点,1,到目的节点的最短路长度可从,2,3,4,到目的节点的最短路长度节点,1,到这些节点的边成本经枚举得到,3,应用优化原理设计算法的过程如下：,选择子问题的表示：设,f(i),为,i,到目的节点的最短路长度,建立,f(i),的递归方程,设,Ai,为与,i,相邻的结点集合，则有,4,初始,f(7)=0,依次计算,f(6),f(1),：,f(6)=1,f(5)=2,f(4)=8+f(6),f(3)=min1+f(5),5+f(6),f(2)=min7+f(5),6+f(6),f(1)=min1+f(2),4+f(3),6+f(4),递归还可从前向后：,f(i)=,节点,1,到节点,i,的最短路的长度；递归从,f(1)=0,开始。,5,例,1: (,数字三角问题,),如图所示的数字三角形，从顶部出发，在每一个节点可以选择向左走或者向右走，一直走到底部，要求找到一条路径，使路径上的数字和最大。,贪心法？,穷举法？,6,F,1,(),F,3,(),F,4,(),F,5,(),F,2,(),用函数,f,i,(x)表示第i层节点到底部（假设是第N层）的路径上数字和的最大值。,显而易见：,f,1,(9)=9+maxf,2,(12)+f,2,(15),问题变成：,f,1,(9)=?,f,2,(12)=12+maxf,3,(10)+f,3,(6),f,2,(15)=15+maxf,3,(6)+f,3,(8),7,f,i,(x)=x+maxf,i+1,(x1)+f,i+1,(x2)+,递归公式的终止条件：,f,N,(19)=19,f,N,(7)=7,思考：,请同学们手工计算一下结果？,如何编程？,8,如何编程与数据结构有关：将原始数塔写成下面的形式，用,dataij,表示这个矩阵,用矩阵,dij,表示上面的,f,i,(x),用矩阵表示的递归公式是什么样子？,Dij= dataij +maxdi+1j,di+1j+1,Dnj=dataij,i=n-1,n-2,2,1,最终的结果,d11,=,？,9,下一个问题：求的,dij后如何让具体最大值路径？,b=dij-dataij,if(b=di+1j), then (i,j),(i+1,j),if(b=di+1j+1), then (i,j),(i+1,j+1),10,总结：动态规划问题的设计要素？,划分子问题,用参数表达子问题的边界，将问题求解转化为多步判断问题,确定优化目标函数,根据问题性质，以函数的极大或者极小为依据，确定是否满足最优原理,列出关于优化函数的递推方程和边界、约束条件,注意：递推方程中总会存在极大或极小运算,求解递推方程,两种求解递推方程的方法,自顶向下：递归方法,自底向上：迭代方法,11,例,2: (资源分配问题)设有n个单位的资源(比如n万元的资金),分配给m个项目，g,i,(x)为第i个项目的到x单位的资源所产生的利润。求利润总和为最大的资源分配方案。,下表是n=7万元资金分配给三个项目A、B、C的利润表,12,分析：根据题意，本质上是求下面的优化问题,J(x,1,x,2,.,x,m,)=maxg,1,(x,1,)+g,2,(x,2,)+,+g,m,(x,m,),x,1,+x,2,+,+x,m,=n,0x,i,n， 要求x,i,是整数,这是一个整数规划问题。,解法,1：最笨的求解方法？穷举发,解法,2：动态规划方法,关键：找到一个递归公式,13,假设，将数量为,x单位的资源分配前i个项目的最大利润为f,i,(x),可以写出下面的递归公式,最终所需要的最大值是：,f,m,(n),=?,如何编程？需要解决数据结构问题,14,将函数用数组表示，,x用j表示，y用k表示，可写出下面的递归公式,fmn就是所需要的最大利润。,实际编程时，还缺少一个东西？每个项目到底分配到多少资源量？,15,定义数组,aij,aij=kmax 表示前i个项目分配资源量为j的情况下，使得前i个项目利润最时，第i个项目分配的资源量为kmax。,求的,aij之后，就可以求的每个项目分的资源量：,j=n;,for(i=m;i=1;i-),xi=aij;,j=j-xi;,16,二、动态规划问题的设计方法,1.,动态规划的特点,最优值,递归（递推）公式,重复子问题,自顶向下递归实现,存在问题：大量重复计算,解决办法：备忘录,自底向上递推实现,根据问题递推公式性质，循环递推即可,17,三、进一步的例子,例3: (,矩阵链乘,)给定n个矩阵A,1,A,2,A,n, , 其中A,i,与A,i+1,是可乘的(i=1,2,3,n-1)。考察这n个矩阵的连乘积,A,1,A,2,A,3,A,n,由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。,若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,18,给定,n,个矩阵,A,1,A,2,A,n,，其中,A,i,与,A,i+1,是可乘的,(i=1,2 ,n-1),。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少,?,为了表示方便,以矩阵加括号表示矩阵相乘的顺序,输入：向量,P,= ,，,n,个矩阵的行数、列数,实例：,P,= ,A,1,: 10 ,100,A,2,: 100 ,5,A,3,: 5 ,50,19,完全加括号的矩阵连乘积可递归地定义为：,（1）单个矩阵是完全加括号的；,（2）矩阵连乘积A是完全加括号的，则A可,表示为2个完全加括号的矩阵连乘积B和C,的乘积并加括号，即 A=(B)(C),设有四个矩阵,A,、,B,、,C,、,D,它们的维数分别是,16000,10500,36000,87500,34500,四种加括号方式,20,穷举法,列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析,：,对于,n,个矩阵的连乘积，设其不同的计算次序为,P(n),。,由于每种加括号方式都可以分解为两个子矩阵的加括号问题：,(A,1,.A,k,)(A,k+1,A,n,),可以得到关于,P(n),的递推式如下：,21,将矩阵连乘积 A,1,A,2,A,3,A,n,简记为Ai:j,这里ij,考察计算Ai:j的最优计算次序。设这个计算次序在矩阵A,k,和A,k+1,之间将矩阵链断开，ikj，则其相应完全加括号方式为,计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量,动态规划, 划分子问题，确定子问题的边界，有,i,和,j,确定子问题的边界,22,设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n,当i=j时，Ai:j=Ai，因此，mi,i,=,0,当ij时,这里 的维数为,的位置只有,种,可能,可以递归地定义mi,j为：, 确定优化函数和递推方程：,23,设立标记函数（决策函数）,为了确定加括号的次序，定义,s,i,j,记录,mi,j,最优时,k,的位置,si,j=k,问题：如何编程实现？, 自顶向下递归实现, 自底向上迭代（递推）实现,24,int RecurMatrixChain(,P,i,j,),m,i,j,=,s,i,j,=,i,for(,k=,i,to,j,1 ),q =,RecurMatrixChain(,P,i,k,),+ RecurMatrixChain(,P,k,+1,j,) +,p,i,1,p,k,p,j,If (,q,m,i,j,),m,i,j,=,q,s,i,j,=,k,/end if,/end for,return,m,i,j,这里没有写出算法的全部描述（进入递归调用的初值等）,方法1：直接递归方法实现,25,复杂性满足递推关系,数学归纳法证明,T,(,n,),2,n,1,n,=2,显然为真,假设对于任何小于,n,的,k,命题为真,则,*递归实现的复杂性,26,n,=5,，计算子问题：,81,个,；不同的子问题：,15,个,2,复杂性高的原因：子问题重复计算,27,方法,2,：直接递推方法,MatrixChain(,P,n,),令所有的,m,i,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,/,计算链,i,j,m,i,j, ,m,i,+1,j, +,p,i,1,*,p,i,*,p,j,/,A,i,(,A,i,+1,.,A,j,),s,i,j, ,i,/,记录分割位置,for(,k,i,+1 to,j,1),t,m,i,k,+,m,k,+1,j,+,p,i,1,*,p,k,*,p,j,/(,A,i,.,A,k,)(,A,k,+1,.,A,j,),if(,t,m,i,j,),m,i,j,t,s,i,j,k,/end if,/ end for(k=),/end for(i=.),28,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,)。,29,例,4:(最长公共子序列),概念：,若,给定序列,X=x,1,x,2,x,m,另,一,序列,Z,=,z,1,z,2,z,k,，,如果,存在,一个严格递增下标序列,i,1,i,2,i,k,使得对于所有,j=1,2,k,有：,z,j,=x,i,j,。,则称,Z,是,X的子,序列,。,例，,序列,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,的公共子序列有很多，,找出,X,和,Y,的最长公共子序列。,30,分析：设,X=“abcbdab”,Y=“bdcdb”,最长公共子序列是：,Z=,“,bcdb,”, 子问题划分及依赖关系,子问题边界：,X,和,Y,起始位置为,1,，,X,的终止位置是,i,，,Y,的,终止位置是,j,，记作,X,i,=,，,Y,j,=,依赖关系：,X,=,Y,=,Z,=,，,Z,为,X,和,Y,的,LCS,，那么,31,(1)若x,i,=y,j,，则,z,k,=x,i,=y,j,，且,Z,k-1,是,X,i-1,和,Y,j-1,的最长公共子序列。,(2)若x,i,y,j,且,z,k,x,i,，则,Z,K,是,X,i-1,和,Y,j,的最长公共子序列。,(3)若x,i,y,j,且,z,k,y,j,，则,Z,k,是,X,i,和,Y,j-1,的最长公共子序列。,由此可见，,2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有,最优子结构性质,。,32,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系,。,用,cij,记录序列和的最长公共子序列的长度。其中，,X,i,=x,1,x,2,x,i,；,Y,j,=y,1,y,2,y,j,。当,i=0,或,j=0,时，空序列是,X,i,和,Y,j,的最长公共子序列,。故此,时,Cij=0,。,其他,情况下，由最优子结构性质可建立递归关系如下：, 递推方程、决策函数,标记函数：,B,i, j,其值为字符,、,、,，分别表示,C,i,j,取得最大值时的三种情况,33,LCS(,X,Y,m,n,) /,求最长公共子序列长度, for(,i=,1 to,m),C,i,0=,0,/,边界情况,for(,i=,1 to,n ),C,0,i,=,0,for(,i=,1 to,m,),for(,j=,1 to,n),if (,X,i,=,Y,j,),C,i,j,=,C,i,1,j,1+1,B,i,j,=,else if(,C,i,1,j,C,i,j,1) ,C,i,j,=,C,i,1,j,B,i,j,=,else,C,i,j,=,C,i,j,1,B,i,j,=,end for(j=),34,Construct_Sequence(,B, i, j,),/,输入：,B,i,j,/,输出：,X,与,Y,的最长公共子序列,if(,i,=0 or,j,=0 ) then return /,一个序列为空,if (,B,i,j, =,“”,) ,输出,X,i,Construct_Sequence (,B, i,1, j,1),else if(,B,i,j,=,“,”,),Construct_Sequence (,B,i,1,j,),else Construct_Sequence (,B,i,j,1),算法的计算复杂度,计算优化函数和标记函数：时间为,O,(,mn,),构造解：每一步至少缩小,X,或,Y,的长度，时间,(,m,+,n,）,空间：,(,mn,),35,输入：,X,=,Y,=,，,标记函数：,解：,X,2,X,3,X,4,X,6,即,B, C, B, A,实例,36,例,4:(最长递增子序列) 若给定序列A=(a,1,a,2,a,m,),如果存在一个下标序列,i,1,i,2,i,k,，使得,则称 为长度为,k的子序列。,问题：给定序列A，求其最长的子序列,例如（5,2,8,6,3,6,9,7）的最长子序列是(2,3,6,7),37,分析：,1.贪心法,构造两个实例, （5,2,8,6,3,6,9,7）, （3,18,7,14,10,12,23,41,16,24）,2,5,3,6,8,6,7,9,有什么规律吗？,38,3,7,18,10,14,12,16,23,24,41, （3,18,7,14,10,12,23,41,16,24）,3,7,18,10,14,12,23,16,41,24,39,2.动态规划方法,构造两个实例, （5,2,8,6,3,6,9,7）, （3,18,7,14,10,12,23,41,16,24）,40,for j = 1 to n,L(j) = 1+maxL(i) | (i,j)E,end for,return maxL(j)|j=1,2,n,41,There 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 subsequence itself?,This is easily managed with a bookkeeping device. While computing L(j), we should also note down prev(j), the next-to-last node on the longest path to j.,The optimal subsequence can then be reconstructed by following these backpointers.,42,