动态规划策略教材(PPT 42页).ppt

动态规划,河海大学计算机信息学院丁海军dinghaijun,例1：求出从顶点1点到顶点7点的最短路径,方法？,一、导言,最优性原理根据穷举法，(1,3,5,7)为优化解。优化原理指：相对于初始决策13造成的问题状态，（3，5，7）必须是3到7的最短路。否则（1，3，5，7）也不可能是优化的。无论第一步决策取2,3,4中那一节点，其后的决策序列必须是该节点到目的节点的最短路节点1到目的节点的最短路长度可从2,3,4到目的节点的最短路长度节点1到这些节点的边成本经枚举得到,应用优化原理设计算法的过程如下：选择子问题的表示：设f(i)为i到目的节点的最短路长度建立f(i)的递归方程设Ai为与i相邻的结点集合，则有,初始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开始。,例1:(数字三角问题)如图所示的数字三角形，从顶部出发，在每一个节点可以选择向左走或者向右走，一直走到底部，要求找到一条路径，使路径上的数字和最大。,贪心法？,穷举法？,用函数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,思考：请同学们手工计算一下结果？如何编程？,如何编程与数据结构有关：将原始数塔写成下面的形式，用dataij表示这个矩阵,用矩阵dij表示上面的fi(x),用矩阵表示的递归公式是什么样子？,Dij=dataij+maxdi+1j,di+1j+1,Dnj=dataij,i=n-1,n-2,2,1,最终的结果d11=？,下一个问题：求的dij后如何让具体最大值路径？,b=dij-dataijif(b=di+1j),then(i,j)(i+1,j)if(b=di+1j+1),then(i,j)(i+1,j+1),总结：动态规划问题的设计要素？划分子问题用参数表达子问题的边界，将问题求解转化为多步判断问题确定优化目标函数根据问题性质，以函数的极大或者极小为依据，确定是否满足最优原理列出关于优化函数的递推方程和边界、约束条件注意：递推方程中总会存在极大或极小运算求解递推方程两种求解递推方程的方法自顶向下：递归方法自底向上：迭代方法,例2:(资源分配问题)设有n个单位的资源(比如n万元的资金),分配给m个项目，gi(x)为第i个项目的到x单位的资源所产生的利润。求利润总和为最大的资源分配方案。下表是n=7万元资金分配给三个项目A、B、C的利润表,分析：根据题意，本质上是求下面的优化问题J(x1,x2,.,xm)=maxg1(x1)+g2(x2)+gm(xm)x1+x2+xm=n0xin，要求xi是整数,这是一个整数规划问题。,解法1：最笨的求解方法？穷举发,解法2：动态规划方法关键：找到一个递归公式,假设，将数量为x单位的资源分配前i个项目的最大利润为fi(x),可以写出下面的递归公式,最终所需要的最大值是：fm(n)=?,如何编程？需要解决数据结构问题,将函数用数组表示，x用j表示，y用k表示，可写出下面的递归公式,fmn就是所需要的最大利润。实际编程时，还缺少一个东西？每个项目到底分配到多少资源量？,定义数组aijaij=kmax表示前i个项目分配资源量为j的情况下，使得前i个项目利润最时，第i个项目分配的资源量为kmax。,求的aij之后，就可以求的每个项目分的资源量：j=n;for(i=m;i=1;i-)xi=aij;j=j-xi;,二、动态规划问题的设计方法,1.动态规划的特点最优值递归（递推）公式重复子问题自顶向下递归实现存在问题：大量重复计算解决办法：备忘录自底向上递推实现根据问题递推公式性质，循环递推即可,三、进一步的例子,例3:(矩阵链乘)给定n个矩阵A1,A2,An,其中Ai与Ai+1是可乘的(i=1,2,3,n-1)。考察这n个矩阵的连乘积A1A2A3An由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的(i=1,2,n-1)。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少?,为了表示方便,以矩阵加括号表示矩阵相乘的顺序,输入：向量P=，n个矩阵的行数、列数实例：P=A1:10100,A2:1005,A3:550,完全加括号的矩阵连乘积可递归地定义为：,（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(B)(C),设有四个矩阵A、B、C、D,它们的维数分别是,16000,10500,36000,87500,34500,四种加括号方式,穷举法列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：,将矩阵连乘积A1A2A3,An简记为Ai:j,这里ij,考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为,计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量,动态规划,划分子问题，确定子问题的边界，有i和j确定子问题的边界,设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n当i=j时，Ai:j=Ai，因此，mi,i=0当ij时,这里的维数为,的位置只有种可能,可以递归地定义mi,j为：,确定优化函数和递推方程：,设立标记函数（决策函数）为了确定加括号的次序，定义si,j,记录mi,j最优时k的位置si,j=k,问题：如何编程实现？,自顶向下递归实现自底向上迭代（递推）实现,intRecurMatrixChain(P,i,j)mi,j=si,j=ifor(k=itoj1)q=RecurMatrixChain(P,i,k)+RecurMatrixChain(P,k+1,j)+pi1pkpjIf(qmi,j)mi,j=qsi,j=k/endif/endforreturnmi,j,这里没有写出算法的全部描述（进入递归调用的初值等）,方法1：直接递归方法实现,26,复杂性满足递推关系,数学归纳法证明T(n)2n1n=2,显然为真假设对于任何小于n的k命题为真,则,*递归实现的复杂性,27,n=5，计算子问题：81个；不同的子问题：15个,复杂性高的原因：子问题重复计算,方法2：直接递推方法,MatrixChain(P,n)令所有的mi,j初值为01ijnfor(r2ton)/r为计算的矩阵链长度for(i1tonr+1)/n-r+1为最后r链的始位置ji+r1/计算链ijmi,jmi+1,j+pi1*pi*pj/Ai(Ai+1.Aj)si,ji/记录分割位置for(ki+1toj1)tmi,k+mk+1,j+pi1*pk*pj/(Ai.Ak)(Ak+1.Aj)if(tmi,j)mi,jtsi,jk/endif/endfor(k=)/endfor(i=.),算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。,例4:(最长公共子序列)概念：若给定序列X=x1,x2,xm,另一序列Z=z1,z2,zk，如果存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。则称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=x1,x2,xm和Y=y1,y2,yn，X和Y的公共子序列有很多，找出X和Y的最长公共子序列。,分析：设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的最长公共子序列。(2)若xiyj且zkxi，则ZK是Xi-1和Yj的最长公共子序列。(3)若xiyj且zkyj，则Zk是Xi和Yj-1的最长公共子序列。,由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中，Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其他情况下，由最优子结构性质可建立递归关系如下：,递推方程、决策函数,标记函数：Bi,j,其值为字符、，分别表示Ci,j取得最大值时的三种情况,LCS(X,Y,m,n)/求最长公共子序列长度for(i=1tom)Ci,0=0/边界情况for(i=1ton)C0,i=0for(i=1tom)for(j=1ton)if(Xi=Yj)Ci,j=Ci1,j1+1Bi,j=elseif(Ci1,jCi,j1)Ci,j=Ci1,jBi,j=elseCi,j=Ci,j1Bi,j=endfor(j=),Construct_Sequence(B,i,j)/输入：Bi,j/输出：X与Y的最长公共子序列if(i=0orj=0)thenreturn/一个序列为空if(Bi,j=“”)输出XiConstruct_Sequence(B,i1,j1)elseif(Bi,j=“”)Construct_Sequence(B,i1,j)elseConstruct_Sequence(B,i,j1),算法的计算复杂度计算优化函数和标记函数：时间为O(mn)构造解：每一步至少缩小X或Y的长度，时间(m+n）空间：(mn),输入：X=,Y=，标记函数：解：X2,X3,X4,X6,即B,C,B,A,实例,例4:(最长递增子序列)若给定序列A=(a1,a2,am),如果存在一个下标序列i1i2ik，使得则称为长度为k的子序列。问题：给定序列A，求其最长的子序列例如（5,2,8,6,3,6,9,7）的最长子序列是(2,3,6,7),分析：1.贪心法构造两个实例（5,2,8,6,3,6,9,7）（3,18,7,14,10,12,23,41,16,24）,有什么规律吗？,（3,18,7,14,10,12,23,41,16,24）,2.动态规划方法构造两个实例（5,2,8,6,3,6,9,7）（3,18,7,14,10,12,23,41,16,24）,forj=1tonL(j)=1+maxL(i)|(i,j)EendforreturnmaxL(j)|j=1,2,n,Thereisonelastissuetobeclearedup:theL-valuesonlytellustheleng