[互联网]动态规划.ppt

制作：初三级,动态规划,1.引例 2.动态规划的概念和术语 3.记忆化搜索亮亮市赛历险记 4.其它算法与动态规划的比较 5.NOIP 2012 普及组 flower静态规划,目录,动态规划的最优化原理,一、引例（最短路问题）,假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从A地运往E地，中间通过B、C、D三个区域，在区域内有多条路径可走，现求一条由A到E的线路，使总距离最短（或总费用最小）。,如果用完全枚举法，则可供选择的路线有3×3×2×1=18（条），将其一一比较才可找出最短路线： AB1C2D3E （长度为12） 显然，这种方法是不经济的，特别是当路线数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。,因此，要获得A-E的最小值，就是要获得 (A-D1的最小值+D1-E的长) (A-D2的最小值+D2-E的长) 中的较小值 而要获得A-D1的最小值又要获得 (A-C1的最小值+C1-D1的长) (A-C2的最小值+C2-D1的长) (A-C3的最小值+C3-D1的长) 中的最小值，以此类推,所谓多阶段决策问题是： 把一个问题看作是一个前后关联具有链状结构的多阶段过程。如下图所示：,从上题的求解过程可以得到以下启示：,1.在处理各阶段决策的选取上，要注意对以后的发展。即是从全局考虑解决局部（阶段）的问题。(关于这点，我们会在后面与贪心对比) 2. 决策依赖于当前的状态，又随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动态”含义。因此，把这种方法称为动态规划方法。,我们可以将一个问题转化为多阶段决策问题,Back,动态规划的基本术语,1、阶段。阶段的划分，一般根据时序和空间的自然特征来划分，但要便于把问题的过程能转化为阶段决策的过程。 2、状态。状态就是阶段的起始位置。 状态变量和状态集合。描述过程状态的变量称为状态变量。通常一个阶段有若干个状态。第k阶段的状态就是该阶段所有始点的集合。如引例中,注意: 状态应具有无后效性。即如果某阶段状态给考虑，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。,3.决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多间题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。,4.策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。,Back,记忆化搜索,亮亮市赛历险记,亮亮同学在市赛中遇到了 这样一道题,滑雪(snow.pas) trs喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便，我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须向下倾斜。 例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1，其实25-24-233-2-1更长，事实上这是最长的一条。 输入文件 第1行: 两个数字r，c(1=r,c=100)，表示矩阵的行列。 第2r+1行:每行c个数，表示这个矩阵。,样例,输入： 5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9,输出： 25,题目分析,看到这个题目亮亮先想到的是暴搜，但是看看数据范围1100，而搜索时间代价以指数级增长肯定是承受不起的。动态规划来说时间空间肯定能承受，可是拓扑关系有那么一点点复杂，像亮亮这要又懒又可爱的同学是不愿意太费脑筋的。那么还有没有其他的算法呢？这就出现了伟大的记忆化搜索！（下文详细介绍）,算法一：搜索,聪明的亮亮一下子就想到了搜索算法：从每一个点开始，判断临近四个点能不能走，能走则继续走，否则返回一步。最后输出最大值。优点是非常容易实现。 可是这样会有许多地方重复搜索了很多遍，岂不是浪费时间？加上前面对于时间复杂度的估算，亮亮只好遗憾地放弃了这种方法。,算法二：动态规划,好吧。想到了动态规划算法这条新路，亮亮开心+猥琐地笑了！ 但是亮亮头天晚上没睡好觉，脑子一片混乱。经过一些时间的脑力劳动，亮亮以牺牲几个脑细胞的代价（亮亮是很懒的），终于还是没有理清拓扑关系，状态转移方程自然无从谈起。亮亮只好愤怒地放弃了动态规划算法。,焦急。,天哪，快没时间了！亮亮焦急地思索着 突然， 灵光一现！,算法三：记忆化搜索,记忆化搜索结合了搜索和动态规划的优点。它是以搜索的形势实现动态规划的思想，具体来说用函数实现 ：对于具有最优子结构的问题，如果搜索到已经搜过的地方则直接返回最优值，否则搜索最优值并记录。最后输出最大值。 附：亮亮在赛后发现记忆化搜索也是有缺点的，即会比动态规划慢一个常数倍。因此如果容易打动态规划就不要用记忆化搜索。（不要像亮亮那么懒！）,const fx1:array14of longint=(-1,1,0,0); fx2:array14of longint=(0,0,-1,1); /方向数组 var m,n,i,j,max:longint; a,b:array1100,1100of longint; function dfs(x,y:longint):longint; var x1,y1,max1,i:longint; begin if (bx,y0) then exit(bx,y); /如果搜过最优值就不用再搜了 max1:=1; /边界为1 for i:=1 to 4 do begin x1:=x+fx1i;y1:=y+fx2i; if (x10)and(x10)and(y1=n)and(ax1,y1ax,y)then begin if (max1dfs(x1,y1)+1) then max1:=dfs(x1,y1)+1; end; end; /搜索临近的点产生最优值 bx,y:=max1; /记录最优值 exit(bx,y); end; begin readln(m,n); for i:=1 to m do for j:=1 to n do read(ai,j);readln; for i:=1 to m do for j:=1 to n do if (maxdfs(i,j) then max:=bi,j; /max记录最长路径 writeln(max); /输出 end.,具体程序实现,结局,亮亮同学终于在市赛中攻克了这道难题！ （亮亮真的很聪明！鼓掌） 虽然完满的结局有点无聊 可是还是要恭喜亮亮！ 谢谢大家,Back,1.搜索与动态规划 2.递推与动态规划 3.贪心与动态规划,其它算法,Back,搜索与动态规划, 不解释 =会有很多比较的,Back,动态规划与递推,登塔教程,有一种算法与动态规划很类似，想必诸位也听说过递推。 递推也是把一个复杂的问题转化为数个小的问题，通过相邻数据的的递推关系式求出解，例如求斐波那契数列。 但实际上，动态规划适合解决最优化问题，而递推适于解决判定性和计数问题。这两者存在着本质上的区别。Now,lets see an interesting question to learn about this.这个问题，就是传说中的 ,动态规划和递推的比较,数塔问题！,问题描述 现在有个很简单的问题。如图所示的数塔，从顶部出发，在每一结点可以选择向左走或向右走，一直走到底层，要求找出一条路径，使路径上的值最大。 输入 第一行是数塔层数n。 第二行起，按数塔图形，有一个或多个的整数，表示该层节点的 值，共有n行。,数塔问题（IOI94）,(*林泽锴*),输出 输出共一行，输出最大值k。 样例输入 5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11 样例输出 86 数据范围 对40%的数据，1n 20; 对100%的数据,1 n 100。,如何解决？,很明显，本题如果用穷举法，程序的运行可能需要很长时间，甚至是直接轰的一声。同时，用贪心法往往得不出最优解，例如样例，如果用贪心法，输出结果就为13+11+12+14+13=63。 所以，现在应该使用一种新的算法，能够保证原地满血满状态复活,动态规划!,问题分析 只要对该题稍加分析，就可以得出一个结论： 如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化的问题。 我们采用动态规划中的顺推解法。按三角形的行划分阶段。若层数为n, 则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段， ，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。 设：fi,j从第i层中的第j个点至三角形顶点有一条最佳路径， 该路径所经过的数字的总和最大，fi,j表示为这个数字和； 由于每一次状态有两个决策，或沿左斜线向上，或沿右斜线向上，因此： fi-1,ji阶段中点沿左斜线向上的点； fi-1,j-1i阶段中点沿右斜线向上的点； 因而可写出转移方程： fi,j:=max(fi,j+fi-1,j,fi,j+fi-1,j-1); (其中max是求最大值的函数) 经过一次顺推，便可分别求出由顶至底个数的条路径，在这条路径所经过的个数字和中，最大值即为正确答案。 同样的道理，也可以用逆推的方式求出解，转移方程是： fi,j:=max(fi,j+fi+1,j,fi,j+fi+1,j+1); （max同上）,程序 顺推： var i,j,n,k:longint; f:array0100,0100 of longint; function max(a,b:longint):longint; begin if ab then exit(a) else exit(b); /求两数的最大值 end; begin readln(n); for i:=1 to n do for j:=1 to i do read(fi,j); for i:=1 to n do /每一层就是一个阶段,共有n个阶段 for j:=1 to i do /一层当中的每一个节点就是一个状态,共有i个状态 fi,j:=max(fi,j+fi-1,j,fi,j+fi-1,j-1); /每个状态有两个决策,即加上上一层左边或右边的数 k:=0; for i:=1 to n do if fn,ik then k:=fn,i; /最后第n层的n个数,其中f的最大值即为答案 writeln(k); end.,逆推： var i,j,n,k:longint; f:array0100,0100 of longint; function max(a,b:longint):longint; Begin if ab then exit(a) else exit(b); /求两数的最大值 end; Begin readln(n); for i:=1 to n do for j:=1 to i do read(fi,j); for i:=n-1 downto 1 do /每一层就是一个阶段,共有n个阶段 for j:=1 to i do /一层当中的每一个节点就是一个状态,共有i个状态 fi,j:=max(fi,j+fi+1,j,fi,j+fi+1,j+1); /每个状态有两个决策,即加上上一层左边或右边的数 k:=0; writeln(f1,1); /f1,1即为答案,不需要像顺推一样进行比较 end.,Back,动态规划与贪心,神奇的导弹,动态规划算法主要条件是最优子结构和无后效性。也就是说动态规划不仅能得出全局最优解，也能得出局部最优解。 贪心算法在每一个步骤都能求出最优解，也就是说贪心能求出局部最优解。贪心也就是每一步决策是完全基于现在的状态的。在某些情况下，贪心也能得出最优解。但是经常，贪心算法会因为目光短浅而得不到全局最优解。,事实上，有些问题是动态规划和贪心都解决不了的，像欧拉回路（中国邮路问题，每条边只遍历一次），就是只能用搜索解决的。同时，搜索能保证正确性，而且不用动脑、打起来方便，是骗分的不二法门。但是搜索的时间代价和空间代价都是很大的，所以搞搜索的也不要灰心，你们还不是一无是处的。 下面我们就给一道题，看看三个方法的异同。,拦截导弹,【问题描述】 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。,【输入样例】 389 207 155 300 299 170 158 65 【输出样例】 2,样例 不解释！,贪心法,按照常识，我们知道每次如果不用开一个新的系统，那么就尽量在原来的系统中挑一个最小的。这样每次插入排序，时间复杂度和空间复杂度都不会很大。也可以保证正确。 但是用贪心的也不要太高兴了。这道题只是凑巧才能对，如果题目加上一问“一套系统最多能拦截多少导弹”，贪心就是行不通的了。 那么源程序在这里就不贴了，自己打去,搜索,搜索只是略提一下，只要枚举就行，不过时间实在是有点长（也不是很长，比如说最大的一个点，只需要102541倍的宇宙历史长度就可以过了），有兴趣的同学们可以去试一试。 那么源程序在这里就不贴了，自己打去,因为比前面的高的导弹最后都会被拦截，所以只要求最长不下降子序列就可以，这样，每一枚导弹都能被拦截。 而且即使加上刚刚提到的那一问，也可以求。因为每一枚能拦到的导弹都不比原来的高，所以只用求最长不上升子序列就行了。 for i:=1 to n do for j:=i-1 downto 0 do if (ajopti) then opti:=optj+1;/同求最长不上升子序列的原理， 只要有一个都比它高就累加1，最后求出最大的 anstime:=0; for i:=1 to n do if optianstime then anstime:=opti;/比较大小 end;,动态规划,Back,NOIP 2012 普及组 flower,静态规划,什么是静态规划？,给定一个数的序列H0,H1,Hn,若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0in)联系起来，这样的式子就叫做递推关系。 静态规划算法（又叫做递推）是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。,例子：一道静态规划的问题,【问题描述】 小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出更多种花，规定第i 种花不能超过ai 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。 试编程计算，一共有多少种不同的摆花方案。 （2012NOIP普及组复赛）,【输入】 输入文件flower.in，共2行。 第一行包含两个正整数n和m，中间用一个空格隔开。 第二行有n个整数，每两个整数之间用一个空格隔开，依次表示a1 a2 an。 【输出】 输出文件名为flower.out。 输出只有一行，一个整数，表示有多少种方案。 注意： 因为方案数可能很多，请输出方案数对1000007取模的结果。,【数据范围】 对于20%数据，有 0n8，0m8，0ai8； 对于50%数据，有 0n20，0m20，0ai20； 对于100%数据，有 0n100，0m100，0 ai100。,算法思路,一般人看到这个题目，首先想到的是递归，但是题目中的数据范围对于这种算法来说还是太大了，十分容易超时。是对于没学过静态规划算法或对这种算法十分不熟练的人，这是唯一的选择。,程序实现,如果用递归算法，时间复杂度呈指数型，大约能过前三个点。 var d,n,m,tot:longint; a:array1100of longint; procedure dfs(i,j,dep:longint); /递归 var x:longint; begin if (dep=m) then begin if (i1000007)do tot:=tot-1000007;/其实就是tot:=tot mod 1000007;啊 exit; end; if (i=n)and(j=an)then exit; if (jai)then dfs(i,j+1,dep+1); for x:=i+1 to n do dfs(x,1,dep+1); end; begin readln(n,m); for d:=1 to n do read(ad);readln; for d:=1 to n do dfs(d,1,1); writeln(tot); end.,算法思路,于是，爱因斯坦为了在NOIP中拿到高分，苦思冥想，终于想出了一种好的算法，那就是神奇的静态规划！,算法思路,设摆放前 i 种花,并且摆 j 盆花，共有 k i , j 种摆法，于是就有了递推关系式： 1. k1,m=1（0mai） 2. km,n=0（m为任何合理的值,n0） 3. ai ki,j= ki-1,j-x x=0 ( x 意为此时若第 i 种花摆 x 盆。 ) (是什么意思？看程序就好啦！ ),程序实现,如果用静态规划算法，时间复杂度O(n3)，所有点都能过， 程序也要简短许多哦！ var i,j,k,m,n:longint; a:array1100of longint; hello:array0100,0100of longint; begin readln(n,m); for i:=1 to n do read(ai); for i:=0 to a1 do hello1,i:=1; for i:=2 to n do for j:=0 to m do for k:=0 to ai do if j-k=0 then begin inc(helloi,j,helloi-1,j-k); helloi,j:=helloi,j mod 1000007; end; writeln(hellon,m); end.,总结归纳,由此可见，静态规划算法几乎完胜递归算法，时间要快得多（就是使用空间略大，但绝对可以忍受的），对于这种数据： 0n100，0m100，0 ai100 递归算法可能就要用上几倍宇宙历史长度的时间，但是静态规划在1秒以内就算完了，远远快于递归算法。,谢谢,