您好,欢迎访问三七文档
1§5.Dynamicprogramming第二章(动态规划)采用动态规划方法,可以优雅而高效地解决许多用分治技术无法解决的问题2例如:数塔问题如图一个数塔,从顶部出发,在每一个结点可以选择向左走或向右走,一直走到底层,要求找出一条路径,使路径上的数值和最大。91215106821895197104163从数塔的特点来看,不难发现解决问题的阶段划分,应该是自下而上逐层决策。对经过第四层2的路径,在第五层的19,7中选择19;对经过第四层18的路径,在第五层的7,10中选择10;对经过第四层9的路径,在第五层的10,4中选择10;对经过第四层5的路径,在第五层的4,16中选择16;这是一次决策过程,也是一次递推过程和降阶过程;因为以上的决策结果将5阶数塔问题变为4阶子问题,递推出第四层与第五层的和为:21(2+19),28(18+10),19(9+10),21(5+16)45阶数塔问题变为4阶子问题91215106821281921用同样的方法可以将4阶数塔变为3阶数塔,…,最后得到1阶数塔问题,就是整个问题的最优解。912153834299504959降阶过程59=9+50=9+12+38=9+12+10+28=9+12+10+18+1019101016181859121510682189519710416106125§5.1动态规划的基本思想----仍然是将待求解问题分解成若干个子问题,但保存已解决的子问题的答案,以避免大量重复计算。6动态规划动态规划(dynamicprogramming)是运筹学的一个分支,是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时,提出了著名的最优化原理(principleofoptimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著DynamicProgramming,这是该领域的第一本著作.采用动态规划方法,可以优雅而高效地解决许多用分治技术无法解决的问题解决图像数据压缩、矩阵连乘、有向图最短路径、无交叉子集以及最长公共子序列等应用问题。另外,在语音识别领域,应用动态规划技术的动态时间伸缩算法DTW取得了很大成功71.动态规划概述•DynamicProgramming方法求解每个子问题仅一次,并保存其结果,以后用到时直接存取,不重复计算——节省计算时间。(“备忘录”)•DynamicProgramming方法自底向上,而divide-and-conquer方法自顶向下。•DynamicProgramming方法适用于:当一个优化问题可分为多个子问题,子问题的解被重复使用。82.动态规划算法的步骤①分析优化解的结构。②递归地定义最优解的代价。③自底向上地计算优化解的代价保存之,并获取构造最优解的信息。④根据构造最优解的信息构造优化解。9§5.2多段图问题----求由s到t的最小成本路径(即最短路径)。多段图是一种简单而经典的使用动态规划算法的模型,它既能有效地反映动态规划算法的基本特征,而且在实际问题中也有较多的应用。10多段图的动态规划算法执行过程:91234587691011124732327111118645356425167101815757425tsv1v2v3v4v5----求由s到t的最小成本路径(即最短路径)。11最优值递推关系式为:其中,表示段中顶点到汇点的最小成本路径的成本。),(),(min),(),(,1jlCOSTlicjiCOSTEliVli…….(2.5.1)根据(2.5.1)式,我们可以由后向前逐步确定各阶段中的顶点到汇顶点t的最短路径。对于如上的5阶段网络图,蓝色字体数字标出了各顶点到汇顶点t的最短距离。91234587691011124732327111118645356425167101815757425tsv1v2v3v4v5jil12程序2-5-1:多段图的动态规划算法MultiGraph(E,k,n,P)//有n个顶点的k段图G(按段序统一编号),E是边集,c(i,j)是边(i,j)的成本,P[1:k]是最小成本路径。//1.realCOST(n);integerD(n-1),P(k),r,j,k,n;2.COST(n)=0;3.forjfromn-1by–1to1do4.设r是这样一个顶点,(j,r)E且使得c(j,r)+COST(r)取最小值5.6.D(j)=r;7.Endfor(D(j)和P(j)的说明见下页)8.P(1)=1;P(k)=n;(k为图G的段数,实例中k=5)9.forjfrom2tok-1do10.P(j)=D(P(j-1));11.endfor12.endMultiGraph)()()()(rCOSTrjcMinjCOSTErj,,91234587691011124732327111118645356425167101815757425tsv1v2v3v4v513这里,D(j)将由j到汇顶点t的最短路径上,j后面的顶点记录下来。上例中,123456789101112D[1-12]=[2,7,6,8,8,10,10,10,12,12,12,0]P(j)则记录由源顶点s到汇顶点t的最短路径上处于第j阶段中的顶点。即最短路径上的节点。上例中,v1v2v3v4v5P[1-5]=[1,2,7,10,12]91234587691011124732327111118645356425167101815757425tsv1v2v3v4v514时间花费:语句3~7的for循环所需的时间是:循环体9~11所需时间是:因而,算法MultiGraph的时间复杂度是:|)|(Ennk)(|)|(En15…….(2.5.2)事实上,我们也可以由前向后逐步确定由源顶点s到各阶段中顶点的最短路径,此时,最小成本的递归关系为:),(),(min),(),(,1jlBCOSTlicjiBCOSTEliVli16上图中的红色字体标出了由源顶点s到各顶点的最短距离。由前向后(备忘录算法)的处理方法:91234587691011124732327111118645356425169732101110151416tsv1v2v3v4v517程序2-5-2:多段图的备忘录动态规划算法Memorized_MultiGraph(E,k,n,P)//有n个顶点的k段图G(按段序统一编号),E是边集,c(i,j)是边(i,j)的成本,P[1:k]是最小成本路径。//1.realBCOST(n);integerD(n-1),P(k),r,j,k,n;2.BCOST(1)=0;3.forjfrom2tondo4.设r是这样一个顶点,(j,r)E且使得c(j,r)+BCOST(r)取最小值5.6.D(j)=r;7.endfor8.P(1)=1;P(k)=n;(k为图G的段数,实例中k=5)9.forjfromk-1by-1to2do10.P(j)=D(P(j+1));11.endfor12.endMemorized_MultiGraph)()()()(rBCOSTrjcMinjBCOSTErj,,18注:由前向后的处理方法的算法时间复杂度与由后向前的处理方法没有区别。19§5.3矩阵链乘序问题20考虑n个阵的链乘:M=M1×M2×......×Mn例如,n=4M=M1×M2×M3×M410×2020×5050×11×100乘的顺序对运算量的影响很大!21例如,M=M1×M2×M3×M410×2020×5050×11×100算法1:M1×(M2×(M3×M4))M3×M4……M2×50×1×100+20×50×100+10×20×100=125000次算法2:(M1×(M2×M3))×M4M2×M3……M1×20×50×1+10×20×1+10×1×100=2200次22计算量的花费随n的增长呈指数增长的,但n大时,穷举搜索法不可行。∴用动态规划!要试验所有可能顺序来找出运算量(费用)最小的顺序是一个指数过程,穷举搜索法是最容易想到的方法。也就是列举出所有可能的计算次序,并计算出每一种次序相应需要的数乘次数,再从中找出花费最小的一种次序来。23原则:先计算所有最小子问题的算量;再计算所有次大子问题的算量;......直到得出最小总算量(已做过的计算不再重复)。24如上例,先找M1×M2,M2×M3,M3×M4再找M1×M2×M3,M2×M3×M4,…………25设mij是计算Mi×Mi+1×......×Mj,(1≤i≤j≤n)的最小算量(费用)。其中,Mi的阶是r(i-1)×ri阶号给定的号:r0r1......rnM1×M2×M3×M410×2020×5050×11×100r0r1r1r2r2r3r3r4mij是遍取所有可能k值时的极小m.那么,jkijiforjiforrrrmmMINmjkijkikij,)(01,126上例,k=2时:(M1×M2)×M3m12+m33+r0r2r3(注:m33=0)▼mik是Mi×Mi+1×......×Mk的最低费用,乘的结果是ri-1×rk阵;▼mk+1,j是Mk+1×Mk+2×......×Mj的最低费用,乘的结果是rk×rj阵;▼ri-1×rk×rj是把以上2阵相乘所需费用。27算法2.5.3:(P.41)输入:r0,r1,…...,rn输出:最低费用begin①fori←1untilndomii←0;②forl←1untiln-1do③fori←1untiln-ldobegin④j←i+l;⑤end;⑥writem1nend)(MIN1,1jkijkikjkiijrrrmmm28注:1.在第⑤句中,每次求MIN是O(n),i循环是O(n)个,∴求MIN是O(n2)。∴总共要进行O(n3)。2.若在第⑤步中求MIN时,每次均在mi,j-1和mi+1,j中去找mij,则算法可改进O(n2)。29在算法2.5.3中,l--是m的下标宽:l=1时得:m12,m23,m34l=2时得:m13,m24l=3时得:m14操作主要集中在第⑤句,需做2件事:1.算费用;2.求MIN(←mij的MIN)。30由:M1×M2×M3×M410×2020×5050×11×100r0r1r1r2r2r3r3r4再根据公式:)(MIN1,1jkijkikjkiijrrrmmm31如果在第⑤句中要求returnk,则可知乘的顺序。m11=0m12=10000m23=1000m34=5000m22=0m33=0m44=0m13=1200m24=3000m14=2200M=M1×M2×M3×M410×2020×5050×11×100)(MIN1,1jkijkikjkiijrrrmmm321.考察上表第3行M13:(见P.41)⑴k=1M13=m11+m23+r0r1r3=0+1000+200=1200⑵k=2M13=m12+m33+r0r2r3=10000+0+500=10500∴M13的最小值是:1200)(MIN1,1jkijkikjkiijrrrmmm332.考察上表第3行M24:⑴k=2M24=m22+m34+r1r2r4=0+5000+100000=105000⑵k=3M24=m23+m44+r1r3r4=1000+0+2000=3000∴M24的最小值是:3000)(MIN1,1jkijkikjkiijrrrmmm343.考察上表第4行M14:⑴k=1M14=m11+m24+r0r1r4=0+3000+20000=23000⑵k=2M14=m12+m34+r0r2r4=10000+5000+50000
本文标题:2.5动态规划1
链接地址:https://www.777doc.com/doc-3456644 .html