动态规划.PPT

河南省实验中学 常庆卫,动态规划 (dynamic programming),河南省实验中学 常庆卫,动态规划 dynamic programming 20世纪50年代由美国数学家Richard Bellman发明。 是一种算法设计技术，是一种使多阶段决策过程最优的通用方法。,河南省实验中学 常庆卫,最优化原理,最优化原理：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。,河南省实验中学 常庆卫,无后效性,动态规划的过程是一个状态转移的过程：不断地从一个已知的状态出发，推出一个新的状态。但是，如果新的状态又能推出前面的状态（影响前面的状态），那么这样的状态划分就具有了后效性。动态规划能够成功的一个必要条件就是无后效性。,河南省实验中学 常庆卫,例：,下图中，顶点A为起点，顶点E为终点，试求从起点至终点的最短路径所需费用。,河南省实验中学 常庆卫,DisX:为城市X到E的最短路线的长度；（X表示任意一个城市） MapI,J:表示I，J两个城市间的距离，若MapI，J=0，则两个城市不连通。 用深度优先搜索来做：,河南省实验中学 常庆卫,Var Se:未访问的城市集合； Function Long(Who:当前访问城市):Integer; 求当前访问城市与城市E的最短距离。 Begin If Who=E Then Long:=0 Else Begin Min:=Maxint; For I取遍所有城市 Do If （MapWho,I0） And (I In Se) Then Begin Se:=Se-I; J:=MapWho,I+Long(I); Se:=Se+I; If JMin Then Min:=J; End; Long:=Min; End; End;,河南省实验中学 常庆卫,Begin Se:=除A外所有城市的集合； DisA:=Long(A); End.,时间复杂度:O(n!),河南省实验中学 常庆卫,在求从B1到E的最短路径的时候，先求出从C2到E的最短路径；而在求从B2到E的最短路径的时候，又求了一遍从C2到E的最短路径。也就是说，从C2到E的最短路径我们求了两遍。同样可以发现，在求从C1、C2到E的最短路径的过程中，从D1到E的最短路径也被求了两遍。而在整个程序中，从D1到E的最短路径被求了四遍.,河南省实验中学 常庆卫,求解的过程中，同时将求得的最短路径的距离“记录在案”，随时调用. 由后往前依次推出每个Dis值，直到推出DisA为止。,河南省实验中学 常庆卫,我们可以用阶段作为每个城市的次序，然后从阶段3倒推至阶段1，再推出DisA。 公式： DisX=Min DisY+MapX,Y Y是下一个阶段中与X相连通的城市 注：可以把E看成第4个阶段，A看成第0个阶段。,河南省实验中学 常庆卫,DisE=0 For X=阶段3的每个城市Downto 阶段0的每个城市 Do Begin DisX:=Maxint; For Y=阶段X的下一个阶段中的每个城市 Do If DisY+MapX,YDisX Then DisX:=DisY+MapX,Y; End.,时间复杂度:O(n2),河南省实验中学 常庆卫,有4个点，分别是A、B、C、D，如图所示，相邻两点用两条连线C2k,C2k-1(1k3)表示两条通行的道路。连线上方的数字表示道路的长度。我们定义从A到D的所有路径中，长度除以4所得余数最小的路径为最优路径。求一条最优路径。,河南省实验中学 常庆卫,由于决策的各个阶段都是互相联系的，因此在寻找问题的最优决策序列时，一般不可能在一个决策步上直接确定某个方案是否为最优方案，但根据最优原理，可从最后的决策阶段往前推，从而求出各个决策步上的最优方案。,河南省实验中学 常庆卫,如图是一个城市道路示意图。每条边上的数字是这段道路的长度。条件：从A地出发，只许向右或向上走。目标：寻找一条从A地到B地的最短路径和长度。,A,B,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,3,3,3,4,4,4,4,3,3,3,2,3,2,5,河南省实验中学 常庆卫,A,2,3,4,5,6,7,8,9,10,11,12,2,3,1,1,3,2,2,2,2,2,4,2,2,2,3,2,4,2,5,13,14,15,16,17,18,19,B,1,3,1,1,2,3,4,4,1,2,3,3,河南省实验中学 常庆卫,设有一个三角形的数塔，顶点结点称为根结点，每个结点有一个整数数值（小于3000）。从顶点出发，可以向左走，也可以向右走，可以找到一条从根结点开始到达底层的路径 问题：当三角形数塔给出后，找出一条路径，使路径上的值为最大。若这样的路径存在多条，选根部偏左的路径。,河南省实验中学 常庆卫,河南省实验中学 常庆卫,河南省实验中学 常庆卫,data1n,1n,1 2 3 4 5,1 2 3 4 5,河南省实验中学 常庆卫,状态:f(i,j)表示以第i行,第j列的结点为根的子树的最优值。,状态转移方程: f(i,j)=maxf(i+1,j),f(i+1,j+1)+datai,j (1=in,1=j=i),边界状态: f(n,1)=datan,1 f(n,2)=datan,2 f(n,n)=datan,n,f(n,k)=datan,k (1=k=n),河南省实验中学 常庆卫,f1n,1n,1 2 3 4 5,1 2 3 4 5,河南省实验中学 常庆卫,满二叉树有m层,叶子节点有n个。 则有：n=2m,河南省实验中学 常庆卫,搜索策略： 时间复杂度20*21*22*2m=21/m(m+1) 2m2,河南省实验中学 常庆卫,data1n,1n,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,1 2 3 4 5,河南省实验中学 常庆卫,状态:f(i,j)表示以第i行,第j列的结点为根的子树的最优值。,状态转移方程: f(i,j)=maxf(i+1,2*j-1),f(i+1,2*j)+datai,j (1=in,1=j=2i-1),边界状态: f(n,1)=datan,1 f(n,2)=datan,2 f(n,n)=datan,n,f(n,k)=datan,k (1=k=n),河南省实验中学 常庆卫,搜索策略： 时间复杂度20*21*22*2m=21/m(m+1) O(2m2),动态规划： 时间复杂度m*2m+1 O(m*2m),M是层数,不会很大,以n的可承受范围,应该在20以内,上述两个算法的时间复杂度相差不大。,河南省实验中学 常庆卫,动态规划的实质,动态规划的实质是分治思想和解决冗余。因此，动态规划是一种将问题实例分解为更小的、相似的问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。,河南省实验中学 常庆卫,求最长不下降序列 设有一个长度为n的正整数的序列：b1,b2,bn,对于下标i1i2iL,若有bi1= bi2 = = biL,则称存在一个长度为L的不下降序列。 例如，下列数列 7 9 16 38 24 37 18 44 19 21 22 63 15 对于下标i1=1, i2=4, i3=5, i4=9, i5=13, 满足13 16 38 44 63 存在长度为5的不下降序列 对于下标i1=2, i2=3, i3=4, i4=8, i5=10, i6=11, i7=12, i8=13 满足7 9 16 1819212263 存在长度为8的不下降序列 求出最长的不下降序列,河南省实验中学 常庆卫,7 9 16 38 24 37 18 44 19 21 22 63 15,n=1时：ans=1,n=2时：ans=1,7,或,n=3时：ans=2,7 9,n=4时：ans=2,7 9,或,13 16,状态：,f(i) 表示以第i个数为首项的最长不下降序列,河南省实验中学 常庆卫,1,2,3,7,8,9,10,11,12,13,14,下图 表示对于数列m(从第m项到第n项）以第m项为首项的最长不下降序列,m,14,13,12,14,13,14,11,14,13,14,阶段0,阶段1,阶段2,阶段13,阶段14,阶段12,河南省实验中学 常庆卫,f(i)=,max,f(i+1) +1 datai=datai+1,1 dataidatai+1,f(i+2) +1 datai=datai+2,1 dataidatai+2,f(n-1) +1 datai=datan-1,1 dataidatan-1,f(n) +1 datai=datan,1 dataidatan,河南省实验中学 常庆卫,设二维数组data:array1n,13 of integer;,河南省实验中学 常庆卫,初始化 datai,1数列 datai,21 datai,30,输出结果,For in-1 down 1 do,L0;k0;,For ji+1 to n do,(dataj,1datai,1)and(dataj,2L),Y,N,Ldatai,2;kj;,Y,N,Datai,2L+1;datai,3k,L0,河南省实验中学 常庆卫,正向递推方法： 状态：f(i)表示以第i项为尾的数列（第1项到第i项）的最长不下降序列。,河南省实验中学 常庆卫,f(i)=,max,f(i-1) +1 datai=datai-1,1 dataidatai-1,f(i-2) +1 datai =datai-2,1 dataidatai-2,f(2) +1 datai =data2,1 dataidata2,f(1) +1 datai =data1,1 dataidata1,河南省实验中学 常庆卫,设二维数组data:array1n,13 of integer;,河南省实验中学 常庆卫,渡轮问题： Palmia河在某国从东向西流过，并把该国分为南北两个部分。河的两岸各有n个城市，且北岸的每一个城市都与南岸的某个城市是友好城市，而且对应的关系是一一对应的。现在要求在两个友好城市之间建立一条航线，但由于天气的关系，所有航线都不能相交，因此，就不可能给所有的友好城市建立航线。 问题：当城市个数和友好关系建立之后，选择一种修建航线的方案，能建最多的航线而不相交。,1,2,3,4,5,6,7,1,2,3,4,5,7,6,河南省实验中学 常庆卫,小羊头啃苹果,Sherlock最近认识了一只很可爱的牧羊犬，自称小羊头。她很喜欢吃苹果，常常偷偷溜到Sherlock的花园来瞻仰种在那儿的两棵苹果树。然而小羊头实在太小了，够不着苹果树上的苹果。于是Sherlock只好施展魔法，使得每分钟都有一只苹果从两棵树的其中一棵上掉下来。众所周知，苹果掉到地上是会烂掉的，而没人喜欢吃烂苹果，因此小羊头只有在苹果掉落时站在苹果树下才能接住苹果并狼吞虎咽之。她吃苹果速度非常快，完全可以忽略不计，而且她跑步也很快，从一棵树跑到另一棵树所花的时间同样也可以忽略不计，然而她却非常懒，只愿意跑W( W = 30)次。现今苹果已经开始掉落了，小羊头正站在A树底下，而且我们知道Sherlock目前还只是个菜鸟巫师，MP（魔法值）有限，所以该法术只能撑T(1 = T = 1000)分钟。聪明的你可以帮助小羊头在这T分钟内吃到最多的苹果么？,河南省实验中学 常庆卫,输入 第一行：包含两个整数，T和W 第二至T+1行：1或者2，分别表示该时刻苹果从A树或者B树上掉落 输出 仅一行：小羊头所能吃到的最多的苹果数 样例输入： 7 2 2 1 1 2 2 1 1 样例输出： 6,输入输出,河南省实验中学 常庆卫,首先提取问题模型： 若相邻的数字均为1或者2，那么不妨把这些苹果合并起来，得到某一段时间某一棵树连续掉落的苹果数 那么此问题就转化为：已知一串数字，从中提取部分数相加，约定奇偶位相间取的次数不能超过W次，求最大和 注意小羊头刚开始是站在A树下的，初始化时需要做相关操作,河南省实验中学 常庆卫,思考过程,思考每一个状态需要保留哪些信息 思考某一个状态与先前哪些状态有关，可以由哪些状态推出 构建方程 思考该方程是否满足两个基本条件 仔细检查方程初始化、上下界部分是否正确,河南省实验中学 常庆卫,状态：Fi, j表示到第i个数为止，已经奇偶相间提取了j次，所得的最大和。 边界状态 Ai表示第i个数的值 F0,0=0 F0,1=0 F1,0 = A1 F1,1=A1 F2,0=A1 F2,1=A1+A2 Fk,0=Ai (1=i=k and i是奇数),河南省实验中学 常庆卫,状态转移方程： Fi, j = max(fi-1,j-1, fi-2,j) + Ai,河南省实验中学 常庆卫,0 1 2 3 4,0 1 2 3 4 5,*,*,*,河南省实验中学 常庆卫,F3, 0 = 2 F3, 1 = max(f2,0, f1,1) + A3 = max(0,0)+2=2 F3, 2 = max(f2,1, f1,2) + A3 = max(1,0)+2=3,返回,河南省实验中学 常庆卫,F4, 0 = 2 F4, 1 = max(f3,0, f2,1) + A4 = max(2,1)+2=4 F4, 2 = max(f3,1, f2,2) + A4 = max(2,0)+2=4 F4, 3 = max(f3,2, f2,3) + A4 = max(3,0)+2=5,返回,河南省实验中学 常庆卫,F5, 0 = 4 F5, 1 = max(f4,0, f3,1) + A5 = max(2,2)+2=4 F5, 2 = max(f4,1, f3,2) + A5 = max(4,3)+2=6 F5, 3 = max(f4,2, f3,3) + A5 = max(4,0)+2=6 F5, 4 = max(f4,3, f3,4) + A5 = max(5,0)+2=7,返回,河南省实验中学 常庆卫,最长共公子串： 设A，B两个字符串，找出A，B中最长共公子串，可以不连续，但顺序不能颠倒。 例如：A=abcdefghijklmn B=kxmdyfliju 此时存在子串km，长度为2 dfij，长度为4 但子串kmdfij虽然在A，B中都存在，但顺序不同，不是符合要求的子串。,河南省实验中学 常庆卫,有限资源分配问题:设资源总数为m，工程项目数为n,给每项工程分配的资源数目不同，获得的利润也不相同，各工程的投资利润表G如下表所示，其中Gi,j是对工程i 投资j可获得的利润（1=i=n, 0=j=m）.求如何分配资源才能获得最大的利润。,河南省实验中学 常庆卫,3,6,2,0,2,1,2,3,1,0,1,1,1,0,1,1,1,2,2,5,2,6,1,3,3.0,下图 表示对1-X项工程投资Y的最大利润,X,Y,阶段0,阶段1,阶段2,2,2,2,4,2.7,2.45,2.2,1.9,1.3,0,2.25,2.0,1.8,0,1.8,0,河南省实验中学 常庆卫,f(i,j)= maxg(i,j) +f(i-1,0), g(i,j-1) +f(i-1,1) , g(i,0) +f(i-1,j),f(i,j)=,max,g(i,j) +f(i-1,0),g(i,j-1) +f(i-1,1),g(i,j-2) +f(i-1,2),g(i,1) +f(i-1,j-1),g(i,0) +f(i-1,j),河南省实验中学 常庆卫,河南省实验中学 常庆卫,最小代价子母树 设有N堆沙子排成一排，其编号为1,2,3,N(N=100)。每堆沙子有一定的数量。现要将N堆沙子并成为一堆。归并的过程只能每次将相邻的两堆沙子堆成一堆，这样经过N-1次归并后成为一堆。找出一种合理的归并方法，使总的代价最小。,河南省实验中学 常庆卫,河南省实验中学 常庆卫,239=min178,20+156,43+118,87+65,145+22,185+77,178=min145,20+98,43+66,87+25,137+69,185=min127,15+118,46+65,98+22,156+74,145=min87,20+69,43+37,98+65,127=min98,15+66,46+25,98+56,156=min98,24+65,69+22,118+67,87=min43,20+24,46+44,98=min46,15+37,69+52,98=min69,24+25,66+49,118=min66,37+22,65+59,河南省实验中学 常庆卫,f(1,n)=minf(1,n-1),f(1,2)+f(3,n),f(1,3)+f(4,n),f(2,n)+g(1,n),f(i,j)表示从i堆沙子到j堆沙子的归并最小代价数。,河南省实验中学 常庆卫,F(i,j)= minf(i,j-1), f(i,i+1)+f(i+2,j), f(i,j-2)+f(j-1,j), f(j+1,j)+g(i,j),F(i,j)=,min,+g(i,j),f(i,j-1),f(i,i+1)+f(i+2,j),f(i,i+2)+f(i+3,j), ,f(i,j-3)+f(j-2,j),f(i,j-2)+f(j-1,j),f(j+1,j),河南省实验中学 常庆卫,多边形游戏是单人玩的游戏。开始时，给定一个由N个顶点构成的多边形，每个顶点被赋予一个整数值，每条边被赋予一个算术运算符。 首次移动允许一条边删除； 接下来的每次移动，包括下面步骤; （1）选出一条边E，以及边E所连接的顶点V1和V2； （2）用一个新的顶点V，来取代边E和顶点V1，V2。其中顶点V的值是由顶点V1和V2的值经边的运算而得到的结果； （3）游戏的目的是逐步删除所有的边，使得最后剩下一个顶点。该顶点的值便是游戏结束后的得分。 请你编写一个程序，对任意给 定的这样多边形，计算可能的最高分，并列举所有可以导致得最高分的被首次删除的边。,河南省实验中学 常庆卫,3,7,6,-3,6,-4,+,+,+,*,*,*,河南省实验中学 常庆卫,3,7,6,-3,6,-4,+,+,*,*,*,河南省实验中学 常庆卫,3 * (-4) + 6 * (-3) + 6 * 7,河南省实验中学 常庆卫,运算数：aj , aj+1 , aj+2 , , aj+i-1,运算符： bj , bj+1 , bj+2 , , bj+i-2,F(i,j,1)=maxf(i-1,j,1)bj+I-2 f(1,i+j-1,1), f(i-1,j,1)bj+I-2 f(1,i+j-1,2), f(i-1,j,2)bj+I-2 f(1,i+j-1,1), f(i-1,j,2)bj+I-2 f(1,i+j-1,2), f(i-1,j,1)bj f(1,j,1), f(i-1,j,1)bj f(1,j,2), f(i-1,j,2)bj f(1,j,1), f(i-1,j,2)bj f(1,j,2),河南省实验中学 常庆卫,设有一个长度为N的数字字符串，分成K+1个部分，使得K+1个部分的乘积最大。 例如N=6，且数字字符串为30143，K=3.此时可能有的情况有以下各种： 310143=0 310143=129 310143=126 310143=1290 310143=1260 310143=3636 310143=0 310143=372 310143=3720 问题：当N，数字串，K给出之后，找出一种分法使其乘积最大。,河南省实验中学 常庆卫,设f(i,j,s)表示从Ai到Aj，s个乘号取得的最大值。 f(i,j)表示从Ai到Aj的数字最大列 f(1,n,k)=maxf(1,n-1,k-1)*g(n,n), f(1,n-2,k-1)*g(n-1,n), f(1,k,k-1)*g(k+1,n),河南省实验中学 常庆卫,一个作曲家作了n首歌曲，标号从1n(按作曲时间排列)，现在要出版这位作曲家的部分歌曲，计划用m张碟片出版，每张碟片长度为t,歌曲必须按照作曲时间选曲，即第一张碟选了1、3，第二张碟就只能从4开始选。问如何选曲才能使所选歌