《动态规划DynamicProgrammingDPppt课件》由会员分享，可在线阅读，更多相关《动态规划DynamicProgrammingDPppt课件（73页珍藏版）》请在金锄头文库上搜索。
1、动态规划DynamicProgrammingDPppt课件Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望OutlinenWhatistheDPqDefinitionqSolutionsnTypicalapplicationsq0/1KnapsackqMatrixMultiplicationChainsqAllPairsShortestPathsqMaximumNon-crossingSubsetnets:MNSqLongestCommonSubsequencenAdvancedto
2、picsqHiddenMarkovModelqMathematicsoptimization一个简单的例子：多段图n最短路(1-3-5-7)上的子路径也是到目的节点7的最短路.例如,(3-5-7)n无论最短路的下一跳是2,3,4中的那个节点,其后的路径也应是最短路12346571467658121任务描述：找出从起点1到终点7的最短路径多段图：一般情形n设c(i)为结点i到目的节点e的最短路长度,A(i)为与i相邻的节点集合,有:qc(s)为所求最短路径长度qc(e)=0qc(i)=minjA(i)c(j)+cost(i,j)siD&CHow to solve a DP problemnDef
3、ineanvaluefunctionofstatesnWriteouttherecursiveequationofvaluenSolvetherecursiveequationqTop-downapproachqBottom-upapproachnTracebacktheoptimalsolution0/1背包问题(0/1 Knapsack)n问题描述q有n种可选物品1,n，放入容量为c的背包内，使装入的物品具有最大效益q表示nn,c分别为物品个数和背包容量np1,p2,pn为个体物品效益值nw1,w2,，wn为个体物品容量n问题解析q0/1背包问题的解指物品1,n的一种放法(x1, ,xn的
4、0/1赋值),使得效益值最大q假定背包容量不足以装入所有物品:面临选择n优化原理:无论优化解是否放物品1,优化解对物品2,n的放法,相对剩余背包容量,也是优化解背包问题满足的优化原理n(1,1,0,0,1)为其优化解,即放物品1,2,5n物品1占背包容量2,剩下容量为8q考虑子问题:n=4,c=8,物品为2,3,4,5q(1,0,0,1),即放物品1和5,是子问题的优化解n因而背包问题满足优化原理假设：n=5,c=10p=6,3,5,4,6w=2,2,6,5,4优化值间的递归式n虽然不知道优化解是否放物品1,但从优化原理我们能建立优化值间的递归式n设f(i,y)为以背包容量y,放物品i,n,得
5、到的优化效益值,以下递归关系成立:qf(1,c)=maxf(2,c),f(2,c-w1)+p1q先求子问题的优化值(递归),再从2种可能性中求出最优的.n须对任意给定容量y,任意i,n种物品求解子问题.0/1背包问题：一个简单的例子n放进物品1(x1=1),背包容量还剩r=16x2,x3=1,0为子问题的优化解,值为18，总效益值为20+18=38n不放物品1(x1=0)则对于剩下的两种物品而言,容量限制条件为116，1,1为子问题优化解,值为33n前者效益值为38,后者为33;所以优化解为1,1,0,优化值为38例题：n=3, c=116 w=100,14,10p=20,18,15,0/1背
6、包问题：递归关系n令f(i,y)表示容量为y,物品i,i+1,n 的优化效益值,按优化原理可列递归关系如下：n初始背包问题的递归方程q f(1,c)=maxf(2,c),f(2,c-w1)+p1n迭代q计算从f(n,*)开始(15-1)式)q然后应用(15-2)式递归计算f(i,*)(i=n-1,n-2，,2)，q最后得出 f(1,c)0/1背包问题：例15-4n初始化：n利用递归式（15-2），可得：n因此最优解f(1,116)=maxf(2,116)，f(2,116-w1)+p1=maxf(2,116),f(2,16)+20=max33,38=38例题 n=3, w=100,14,10,
7、p=20,18,15, c=1160/1背包问题：例15-4 （解续2）n求解优化解：traceback方法计算x1,xn值:qf(1,c)=f(2,c)=x1=0；否则x1=1,c=c-w1。qx2:f(2,c)=f(3,c)=x2=0否则x2=1,c=c-w2qXi:f(i,c)=f(i+1,c)=xi=0否则xi=1,c=c-win该例中,qf(2,116)=33f(1,116),所以x1=1.剩余容量=116-100=16,qf(2,16)=18,f(3,16)=14f(2,16),因此x2=1q此时r=16-14=2,不足以放物品3,所以x3=0动态规划小结:n一般步骤q确定决策序列
8、(Decisionsequences)q明确问题状态(Problemstates)q验证优化原理(Principleofoptimal)q构造、求解优化值递归方程(Recurrenceequation)q回溯(traceback)构造优化解(Optimalsolution)n算法复杂性q动态规划递归方程往往不能直接用递归实现,会引发大量重复计算,算法的计算量将非常可观。最好是用迭代法求解动态规划法列出的递归方程q迭代实现需要存贮所有子问题的优化解的值，因此动态规划法设计的算法往往需要较大的存储空间q算法的复杂性来自子问题的数目,通常子问题的数目往往很大动态规划：应用n0/1背包问题n矩阵乘法链
9、n最短路径n网络的无交叉子集0/1背包问题-设计策略n1.递归方法n2.权为整数的迭代方法n3.元组方法递归方法n程序的最坏时间复杂性t(n)qt(1)=a；qt(n)=2t(n-1)+b(n1)，其中a,b为常数q求解可得t(n)=(2n)递归方法：例15-5n为了确定f(1,10),调用函数F(1,10)n比较F(i+1,y),F(i+1,y-wi)+pin递归调用关系如图树型结构所示:q其中每个节点用y值来标记;q第j层的节点对应F(j,*);q根节点表示F(1,10),而它有左、右子节点,分别对应F(2,10)和F(2,8)。n=5, c=10p=6,3,5,4,6w=2,2,6,5,
10、4 ,求f (1,10).10108108861084286201045883226310递归方法：例15-5（续）n通过递归调用树,可以看到程序总共执行了26次递归调用n重复计算的节点,如f(3,8)，f(4,8),f(4,2),f(5,8),f(5,3),f(5,2)n如果保留以前的计算结果,则可将节点数减至20,因为可以丢弃图中的阴影节点10108108861084286201045883226310W取整数时的迭代方法(1)n该算法用二维数组fiy来保存各个f的值因此每个f(i,y)只计算一次n二维数组需(nc)空间n该算法的复杂性(nc)-伪多项式算法:c是算法输入的一部分,c的二进
11、制表示的长度为log2cW取整数时的迭代方法(2)n函数Traceback从fiy产生优化的xi值nTraceback的复杂性为(n).上述程序有两个缺点:1)要求物品重量为整数;2)当背包容量c 很大时,例如c2n,程序的复杂性为(n2n).元组法：元组描述n对于每个i,将f(i,y)的跳跃点以元组(y, f(i,y)形式存于表P(i)中.qP(i)中元组(y,f(i,y)按y的增序排列.q元组(a,b)代表一种装物品i,n的方案:以容量a,能得到效益值b.如何只使用最少的计算从P(i+1)获得P(i)？元组法：元组合并n令Q=(s,t)|wisc的元组(w,v)元组法：例15-6nP(5)
12、=(0,0),(4,6)，Q=(5,4),(9,10)n合并得：P(4)=(0,0),(4,6),(9,10)n计算Q=(6,5),(10,11)n合并得P(3)=(0,0),(4,6),(9,10),(10,11)n计算Q=(2,3),(6,9)n合并得P(2)=(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)n计算Q=(2,6),(4,9),(6,12),(8,15)n合并得P(1)=(0,0),(2,6),(4,9),(6,12),(8,15)n最优效益值为15n回溯求解为1,1,0,0,1设n=5，c=10 p=6,3,5,4,6 w=2,2,6,5,4 求
13、f(1,10)nP(i)中的元组个数至多为P(i+1)中元组个数的2倍.初始P(n)=2,所以:P(i)中的元组个数不超过2(n-i+1)n计算Q需O(|P(i+1)|)的时间,合并P(i+1)和Q需要O(|P(i1)|+|Q|)=O(2|P(i+1)|)的时间.所以计算P(i)需O(2n-i+1)时间n计算所有P(i)时所需要的总时间O(2n)。n存在输入使算法最坏情形为2n量级元组法：性能分析矩阵乘法链（Matrix multiPlication Chains: MPC）nmn矩阵A与np矩阵B相乘需元素乘法数mnpn计算三个矩阵A(mn),B(np)和C(pq)的乘积有两种方式:q第一种
14、方式中先用A乘以B然后乘以C,这种乘法的顺序可写为(A*B)*Cq第二种方式为A*(B*C)n尽管这两种不同的计算顺序所得的结果相同,但所需元素乘法数却不同q第一种方式乘法数：mp(n+q)q第二种方式乘法数：nq(m+p)MPC 示例n假定A为1001矩阵,B为1100矩阵,C为1001矩阵,(A*B)*C需乘法数为1001100100100120000n而 A*(B*C)所需乘法数为1100110011200n长度q的矩阵乘法链有指数量级(2q)的可能的相乘方式n找一种相乘方式,使得元素乘法数最少MPC动态规划解n用M(i,j)表示链Mi,Mj(ij)的乘积.假设优化的乘法顺序先计算M(i
15、,k)和M(k+1,j),再将二者相乘n则计算M(i,j)的优化乘法顺序在计算M(i,k)和M(k+1,j)时也是优化的n考虑5个矩阵的乘法链,其行列数为r =(10,5,1,10,2,10),即M1为105的矩阵,等等q优化的乘法顺序为(M1M2)(M3M4)M5)=190q子链M(3,5)=M3M4M5的优化乘法顺序为(M3M4)M5),是上述长度5的链的优化解在子链上的乘法顺序MPC动态规划解(续)n设c(i,j)为计算M(i,j)的优化乘法数(优化值),根据优化原理,优化值之间满足:qc(i,j)=minik0 return cij;cij=u;A deep look at the s
16、tructures of MPCMPC 迭代算法n函数c 的动态规划递归式可用迭代的方法来求解.若按s=2,3,q-1的顺序计算c(i,i+s),每个c 和kay 仅需计算一次.但需很大的存储空间。MPC 迭代算法:示例12345105015090190205030903020404020050设q = 5和r =（10 , 5 , 1 , 10 , 2 , 10）求解MPCMPC 迭代程序时间复杂度n复杂性为O(q3).q计算C(i,i+s)需(s)时间.q对s2,q-1,要计算q-s个C(i,i+s),时间复杂度为(q-s)s).q所以时间复杂度为(q3)n计算出kay后同样可用程序15-
17、6中的Traceback函数算出相应的最优乘法顺序最短路径(All Pairs Shortest Paths: APSP)n最短路径:假设G为有向图,其中每条边都有一个成本(cost),图中每条有向路径的长度(或成本)定义为该路径上各边的成本之和n对于每对顶点(i,j),定义从i 到j的所有路径中,具有最小长度的路径为从i到j的最短路径n求每对点间的最短路n假定图上无负成本的环路APSP: 例15-15n如图15-4所示。从顶点1到顶点3的路径有1)1,2,5,32)1,4,33)1,2,5,8,6,34)1,4,6,3n由该图可知,各路径相应的长度为10,28,9,27.因而路径3)是该图中
18、顶点1到顶点3的最短路径。APSP: 动态规划解n将节点按1到n编号.n定义c(i,j,k)=i到j的中间节点编号不超过k的最短路长度.qc(i,j,0)=cost(i,j)ifGelsec(i,j,0)=qc(i,i,k)=0forallkqc(i,j,n)是要求的i到j的最短路长度n我们建立c(i,j,k)和c(i,j,k-1)之间的递归关系APSP:递归式n对于任意k0，qc(i,j,k)=minc(i,j,k-1),c(i,k,k-1)+c(k,j,k-1)n性质qc(i,k,k-1)=c(i,k,k)qc(k,j,k)=c(k,j,k-1)n如果直接用递归程序求解上式,则计算c(i,
19、j,n)的复杂度极高.利用迭代方法.可将计算c值的时间减少到O(n3).n迭代算法的伪代码如图15-5所示。APSP：迭代算法n令C(k)代表矩阵(c(i,j,k)i,j=1,nn初始C(0)=(c(i,j),即图的邻接矩阵.n算法迭代计算C(k):q对k行k列的元素nC(k)(i,k)=C(k-1)(i,k)nC(k)(k,j)=C(k-1)(k,j).q对k行k列以外的元素nC(k)(i,j)=maxC(k-1)(i,j),C(k-1)(i,k)+C(k-1)(k,j)APSP：改进的递归算法(1)Kayij是从i到j的最短路径中编号最大的节点,通过该节点可以回溯最短路径节点APSP：改进
20、的递归算法(2)APSP: 例15-17n图15-6a给出某图的长度矩阵a，15-6b给出由程序15-9所计算出的c 矩阵，15-6c为对应的kay值。根据15-6c中的kay 值，可知从1到5的最短路径是从1到kay15=4的最短路径再加上从4到5的最短路径，因为kay45=0，所以从4到5的最短路径无中间顶点。从1到4的最短路径经过kay14=3。重复以上过程，最后可得1到5的最短路径为：1，2，3，4，5。APSP:习题（1）APSP:习题（2）C(0)(i,j)=c(i,j)C(1)(3,2)=minC(0)(3,2),C(0)(3,1)+C(0)(1,2)=7C(2)(1,3)=mi
21、nC(1)(1,3),C(1)(1,2)+C(1)(2,3)=min11,4+2=6C(3)(1,2)=min4,6+7=4C(3)(2,1)=min6,2+3=5Maximum Noncrossing Subset of Nets:MNS1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10n每个i有唯一一个Ci对应，称为网(i,Ci)n(i,Ci)与(j,Cj)组成非交叉子网，若（ij）有(Ci=ci,j-1 thenthen 12. ci,j=ci-1,j13. bi,j=2;14. else else ci,j=ci,j-1 15. bi,j=3;14 bi,
22、j stores the directions. 1diagnal, 2-up, 3-forward.Example 1 of an LCS X=BDCABAandY=ABCBDABConstructing an LCSPrintLCS(b,X,i,j)1. i=m2. j=n;3. if i=0 or j=0 then exit;4. if bi,j=1 then i=i-1; j=j-1; print “xi”; 5. if bi,j=2 i=i-16. if bi,j=3 j=j-17. Goto Step 3.The time complexity:O(nm).01234iXiABCY
23、jBBACD000000000010001121111212211223BB C BLCS(reversedorder):B C BLCS(straightorder):Hidden Markov ModelHMM=(I,O,A,B,)nI=i1,.iN：setofstatenO=v1,.,vM：setofobservationnA=aij，aij=p(It+1=ij|It=ii):transitionprobabilitynB=bik，bik=p(Ot=vk|It=ii):symbolprobabilityn=i，i=p(I1=ii):initstatedistributionWhere:I
24、=isthestatesequenceO=istheoutputsequenceThree Problems of HMMnEvaluation:GivenmodelandoutputsequenceO,computingp(O|)nDecoding:GivenmodelandoutputsequenceO,tofindthestatesequenceXsuchthat:maximizep(O,I|)nLearningGivenoutputsequenceO,tofindthemodelsuchthat:maximizep(O,I|)复习要求n根据优化原理列递归式n设计实现递归式的迭代算法(列
25、表)n应用q0/1背包问题q矩阵乘法链q求各对点之间的最短路qMNSn要求会做实例；分析算法的复杂度课堂练习(1)n0/1背包问题:n=4,c=20,w=(10,15,6,9)p=(2,5,8,1)产生元组集合P(1),P(2),P(3)和该背包问实例的解n证明当重量和效益值均为整数时动态规划算法的时间复杂度为O(min2n,n1inpi,nc)提示:|P(i)|1+ijnpj课堂练习(2)n子集和数问题:设S=s1,s2,.,sn为n个正数的集合,试找出和数不超过M且最大的S的子集n该问题是NP-难度问题,试用动态规划法设计一算法练习(3)nr=(10,20,50,1,100),给出优化的乘
26、法顺序和元素乘法数目练习(4),习题19nT(i,j)=任务i按第j种方式所需时间(j=1,2)nC(i,j)=任务i按第j种方式所需成本(j=1,2)n任务是拓扑排序的，必须先完成任务1才能完成任务2n要求在时间t之前完成所有任务且成本最小ncost(i,j)任务1到i能在j时间内完成的最小成本ncost(1,j)=jT(1,1)=C(1,1)T(1,1)=jT(1,2)=minC(1,1),C(1,2)T(1,2)=jcost(i,j)=mincost(i-1,j-T(i,1)+C(i,1),cost(i-1,j-T(i,2)+C(i,2)表示在时间j内无法安排前i个任务；练习(4)n上述列递归的方式称为从前向后(backward)n也可按书上提示从后向前列递归n设n3,T=(2,1,4;3,2,1)C=(1,5,2;2,3,4)，t=8分号前为第一种选择；分号后为第二种选择。计算优化的完成任务的方案。n分析算法的复杂性练习(5),习题20n假定一机器由n种元件组成。现有三个供应商：w(i,j)=供应商j提供的元件i的重量；c(i,j)=供应商j提供的元件i的成本(取整数值)；求成本不超过c，机器重量最轻的采购方案n同于习题19
