[6]动态规划策略

动态规划河海大学计算机信息学院丁海军[e-mail][例1]：求出从顶点1点到顶点7点的最短路径方法？一、导言最优性原理根据穷举法，(1,3,5,7)为优化解。优化原理指：相对于初始决策1－3造成的问题状态，（3，5，7）必须是3到7的最短路。否则（1，3，5，7）也不可能是优化的。无论第一步决策取{2,3,4}中那一节点，其后的决策序列必须是该节点到目的节点的最短路节点1到目的节点的最短路长度可从2,3,4到目的节点的最短路长度＋节点1到这些节点的边成本经枚举得到应用优化原理设计算法的过程如下：选择子问题的表示：设f(i)为i到目的节点的最短路长度建立f(i)的递归方程设A[i]为与i相邻的结点集合，则有)}(),({cos)()}(),1({cos)1(minmin][]1[jfjitifjfjtfiAjAj初始f(7)=0依次计算f(6),…,f(1)：f(6)=1,f(5)=2,f(4)=8+f(6)f(3)=min{1+f(5),5+f(6)}f(2)=min{7+f(5),6+f(6)}f(1)=min{1+f(2),4+f(3),6+f(4)}递归还可从前向后：f(i)=节点1到节点i的最短路的长度；递归从f(1)=0开始。例1:(数字三角问题)如图所示的数字三角形，从顶部出发，在每一个节点可以选择向左走或者向右走，一直走到底部，要求找到一条路径，使路径上的数字和最大。贪心法？穷举法？F1()F3()F4()F5()F2()用函数fi(x)表示第i层节点到底部（假设是第N层）的路径上数字和的最大值。显而易见：f1(9)=9+max{f2(12)+f2(15)}问题变成：f1(9)=?f2(12)=12+max{f3(10)+f3(6)}f2(15)=15+max{f3(6)+f3(8)}fi(x)=x+max{fi+1(x1)+fi+1(x2)+……}递归公式的终止条件：fN(19)=19fN(7)=7……思考：①请同学们手工计算一下结果？②如何编程？如何编程与数据结构有关：将原始数塔写成下面的形式，用data[i][j]表示这个矩阵用矩阵d[i][j]表示上面的fi(x)用矩阵表示的递归公式是什么样子？D[i][j]=data[i][j]+max{d[i+1][j],d[i+1][j+1]}D[n][j]=data[i][j]i=n-1,n-2,…,2,1最终的结果d[1][1]=？下一个问题：求的d[i][j]后如何让具体最大值路径？b=d[i][j]-data[i][j]if(b==d[i+1][j]),then(i,j)(i+1,j)if(b==d[i+1][j+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)=max{g1(x1)+g2(x2)+…+gm(xm)}x1+x2+…+xm=n0≤xi≤n，要求xi是整数这是一个整数规划问题。解法1：最笨的求解方法？穷举发解法2：动态规划方法关键：找到一个递归公式假设，将数量为x单位的资源分配前i个项目的最大利润为fi(x),可以写出下面的递归公式nxmixgxfyxfygxfiixyi0,,...,2,1}{1110max初始条件：最终所需要的最大值是：fm(n)=?如何编程？需要解决数据结构问题nxmixgxfyxfygxfiixyi0,,...,2,1}{1110max初始条件：n1,2,...,j,,...,2,1]][1[]][1[]}][1[]][[{]][[max0mijgjfkjifkigjifjk初始条件：将函数用数组表示，x用j表示，y用k表示，可写出下面的递归公式f[m][n]就是所需要的最大利润。实际编程时，还缺少一个东西？每个项目到底分配到多少资源量？定义数组a[i][j]a[i][j]=kmax表示前i个项目分配资源量为j的情况下，使得前i个项目利润最时，第i个项目分配的资源量为kmax。求的a[i][j]之后，就可以求的每个项目分的资源量：j=n;for(i=m;i=1;i--){x[i]=a[i][j];j=j-x[i];}]}][1[]][[{]][[maxarg0kjifkigjiajk二、动态规划问题的设计方法1.动态规划的特点最优值递归（递推）公式重复子问题自顶向下递归实现存在问题：大量重复计算解决办法：备忘录自底向上递推实现根据问题递推公式性质，循环递推即可三、进一步的例子例3:(矩阵链乘)给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的(i=1,2,3,…,n-1)。考察这n个矩阵的连乘积A1A2A3…An由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的(i=1,2,…,n-1)。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少?为了表示方便,以矩阵加括号表示矩阵相乘的顺序输入：向量P=P0,P1,…,Pn，n个矩阵的行数、列数实例：P=10,100,5,50A1:10100,A2:1005,A3:550,完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=((B)(C))设有四个矩阵A、B、C、D,它们的维数分别是1050A4010B3040C530D)))(((DBCA)))(((DCAB)))(((DBCA)))(((CDBA)))(((CDAB1600010500360008750034500四种加括号方式穷举法列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。)/4()(11)()(1)(2/311nnPnnknPkPnPnnk算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：将矩阵连乘积A1A2A3,…,An简记为A[i:j],这里i≤j考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤kj，则其相应完全加括号方式为)...)(...(211jkkkiiAAAAAA计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量动态规划①划分子问题，确定子问题的边界，有i和j确定子问题的边界设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]当i=j时，A[i:j]=Ai，因此，m[i,i]=0当ij时jkipppjkmkimjim1],1[],[],[这里的维数为iAiipp1jipppjkmkimjijimjki}],1[],[{min0],[1jki的位置只有种可能kij可以递归地定义m[i,j]为：②确定优化函数和递推方程：③设立标记函数（决策函数）为了确定加括号的次序，定义s[i,j],记录m[i,j]最优时k的位置s[i,j]=k问题：如何编程实现？①自顶向下递归实现②自底向上迭代（递推）实现intRecurMatrixChain(P,i,j){m[i,j]=s[i,j]=ifor(k=itoj1){q=RecurMatrixChain(P,i,k)+RecurMatrixChain(P,k+1,j)+pi1pkpjIf(qm[i,j]){m[i,j]=qs[i,j]=k}//endif}//endforreturnm[i,j]}这里没有写出算法的全部描述（进入递归调用的初值等）方法1：直接递归方法实现26复杂性满足递推关系11111111)(2)()()()()(1))1()()((1)1()(nknknknkkTnOknTkTnOnTnOknTkTnOnT数学归纳法证明T(n)2n1n=2,显然为真假设对于任何小于n的k命题为真,则11111112)12(2)(22)()(2)()(nnnkknknOnOkTnOnT*递归实现的复杂性27n=5，计算子问题：81个；不同的子问题：15个子问题1-12-23-34-45-51-22-33-44-51-32-43-51-42-51-5数8121412845542221112复杂性高的原因：子问题重复计算方法2：直接递推方法MatrixChain(P,n){令所有的m[i,j]初值为01ijnfor(r2ton)//r为计算的矩阵链长度for(i1tonr+1){//n-r+1为最后r链的始位置ji+r1//计算链i—jm[i,j]m[i+1,j]+pi1*pi*pj//Ai(Ai+1..Aj)s[i,j]i//记录分割位置for(ki+1toj1){tm[i,k]+m[k+1,j]+pi1*pk*pj//(Ai..Ak)(Ak+1..Aj)if(tm[i,j]){m[i,j]ts[i,j]k}//endif}//endfor(k=…)}//endfor(i=….)A1A2A3A4A5A630353515155510102020251137520103504375]5][5[]4][2[71252053510002625]5][4[]3][2[1300020153525000]5][3[]2][2[min]5][2[541531521pppmmpppmmpppmmm算法复杂度分析：算法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的最长