《动态规划初步》PPT课件.ppt

《《动态规划初步》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《动态规划初步》PPT课件.ppt（41页珍藏版）》请在三一办公上搜索。

1、常州市第一中学 林厚从,动态规划初步,JSOI2007夏令营B层次（泰州）,常州市第一中学 林厚从,问题：城市交通 有n个城市，编号1n，有些城市之间有路相连，有些则没有，有路则当然有一个距离。现在规定只能从编号小的城市走到编号大的城市，问你从编号为1的城市走到编号为n的城市要花费的最短距离是多少？,输入格式：先输入一个n，表示城市数，n100。下面的n行，是一个n*n的邻接矩阵map1.n,1.n。mapi,j=0，表示城市i和城市j之间没有路相连，否则为两者之间的距离。输出格式：一个数，表示从城市1走到城市n的最短距离。输入数据保证可以从城市1走到城市n。,动态规划的引入,常州市第一中学

2、林厚从,输入样例：110 5 3 0 0 0 0 0 0 0 05 0 0 1 6 3 0 0 0 0 03 0 0 0 8 0 4 0 0 0 00 1 0 0 0 0 0 5 6 0 00 6 8 0 0 0 0 5 0 0 00 3 0 0 0 0 0 0 0 8 00 0 4 0 0 0 0 0 0 3 00 0 0 5 5 0 0 0 0 0 30 0 0 6 0 0 0 0 0 0 40 0 0 0 0 8 3 0 0 0 30 0 0 0 0 0 0 3 4 3 0,动态规划的引入,常州市第一中学 林厚从,设一个数组dis1.n，disi表示城市1到城市i的最短距离。题目就是要求

3、disn。,根据题目的限制条件：只能从编号小的城市到编号大的城市。显然，我们可以从城市1、城市2、城市n-1到城市n，前提是城市i与城市n之间有路，其中i=1，2，3，n-1。,所以，disn就应该取disi+mapi，n中的最小值，且要求mapi，n0，i=1，2，3，n-1。,也就是说要求disn，就必须先求出dis1disn-1，类似于递推算法中的“倒推法”，那么如何求disn-1呢？disn-1=min disi+mapi，n-1 且要求mapi，n-10，in-1。,城市交通分析,常州市第一中学 林厚从,现在我们把问题一般化，如何求disi呢？其中，i=1.n。,Disi=min d

4、isj+mapj，i,要满足：mapj，i0，j=1.i-1,这是一个类似于递归的公式，意思为：要求disn就要先求disn-1 dis1，要求disn-1就要先求disn-2 dis1，而要求disi，就要先求disi-1 dis1，而dis1=0。在具体计算的时候，只要从dis1开始“顺推”下去，依次求出dis2、dis3、disn-1、disn即可。,城市交通分析,常州市第一中学 林厚从,dis1:=0;for i:=2 to n dobegin min:=maxint;用打擂台的方法求出最小值 for j:=1 to i-1 do if mapj,i0 then if disj+map

5、j,imin then min:=disj+mapj,i;disi:=min;end;writeln(min=,disn);,城市交通分析,常州市第一中学 林厚从,动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。1951年，美国数学家R.Bellman提出了解决这类问题的“最优化原则”，1957年发表了他的名著动态规划，该书是动态规划方面的第一本著作。动态规划问世以来，在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用，取得了显著的效果。动态规划运用于信息学竞赛是在90年代初期，它以独特的优点获得了出题者的青睐。此后，它就成为了信息学竞赛中必不可少的一个重要

6、方法，几乎在所有的国内和国际信息学竞赛中，都至少有一道动态规划的题目。所以，掌握好动态规划，是非常重要的。,常州市第一中学 林厚从,动态规划简介,动态规划中有很多深奥的概念，使用动态规划也有很多前提条件，它与递推、递归也有着密切的联系，这些都要等到我们有一点编程经历后才好谈起，所以，我们先放开这些理论，不要被这些理论吓倒，而是去尝试分析和解决几个经典动态规划题目。学习动态规划最重要的是“一种思想方法和解题过程”，请大家积极动脑动手，跟着我一起分析和体会其中的方法和过程，然后再独立去思考和实践。,常州市第一中学 林厚从,动态规划简介,拦截导弹（NOIP1999）问题描述：某国为了防御敌国的导弹袭

7、击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹的枚数和导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间有一个空格），计算这套系统最多能拦截多少导弹？如果要拦截所有导弹最少要配备多少套这种导弹拦截系统？,样例输入：8 389 207 155 300 299 170 158 65 样例输出：6（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）,常州市第一中

8、学 林厚从,“拦截导弹”问题分析,先讨论第一问：假设ai表示拦截的最后一枚导弹是第i枚时，系统能拦得的最大导弹数。例如，样例中的a5=3，表示：如果系统拦截的最后一枚导弹是高度为299的话，最多可以拦截第1枚（389）、第4枚（300）、第5枚（299）三枚导弹。显然，a1a8中的最大值就是第一问的答案。关键是怎样求得a1a8？,我们换一个角度，假设现在已经求得a1a7（注：在动态规划中，这样的假设往往是很必要的），那么怎样求a8呢？,a8要求系统拦截的最后1枚导弹必须是65，也就意味着倒数第2枚被拦截的导弹高度必须不小于65，则符合要求的导弹有389、207、155、300、299、170、

9、158。,常州市第一中学 林厚从,假如拦截的倒数第2枚导弹是300，则a8=a4+1；假如拦截的倒数第2枚导弹是299，则a8=a5+1；类似地，a8还可能是a1+1、a2+1、。当然，我们现在要求得是以65结尾的最多导弹数目，因此a8要取所有可能值的最大值，即：a8=max a1+1，a2+1，a7+1=maxai+1(i=1.7)。,类似地，我们可以假设a1a6为已知，来求得a7。同样，a6、a5、a4、a3、a2也是类似求法，而a1就是1，即如果系统拦截的最后1枚导弹是389，则只能拦截第1枚。,“拦截导弹”问题分析,常州市第一中学 林厚从,这样，求解过程可以用下列式子归纳：a1=1ai

10、=maxaj+1 其中：i1，j=1.i-1，且hj=hi,第一问的答案就是a1a8中的最大值。,“拦截导弹”问题分析,常州市第一中学 林厚从,longest1:=1;for i:=2 to n do 分阶段求出每步的最优值 begin maxlong:=1;for j:=1 to i-1 do if himaxlong then maxlong:=longestj+1;longesti:=maxlong end;maxlong:=longest1;以下打擂台求出最大值 for i:=2 to n do if longestimaxlong then maxlong:=longesti;wri

11、teln(max=,maxlong);,这种解题方法就称为“动态规划”,“拦截导弹”问题分析,常州市第一中学 林厚从,“拦截导弹”问题分析,关于第二问：由于它紧接着第一问，所以很容易受前面的影响，多次采用第一问的办法，然后得出总次数，其实这是不对的。要举反例并不难，比如长为7的高度序列“7 5 4 1 6 3 2”，最长不上升序列为“7 5 4 3 2”，用多次求最长不上升序列的结果为3套系统；但其实只要2套，分别击落“7 5 4 1”与“6 3 2”。所以不能用多次“动态规划”的方法做，那么，正确的做法又是什么呢？,我们的目标是用最少的系统击落所有导弹，至于系统之间怎么分配导弹数目则无关紧要

12、，上面错误的想法正是承袭了“一套系统尽量多拦截导弹”的思维定势，忽视了最优解中各个系统拦截数较为平均的情况，本质上是一种贪心算法，但贪心的策略不对。如果从每套系统拦截的导弹方面来想行不通的话，我们就应该换一个思路，从拦截某个导弹所选的系统入手。,常州市第一中学 林厚从,“拦截导弹”问题分析,题目告诉我们，已有系统目前的瞄准高度必须不低于来犯导弹高度，所以，当已有的系统均无法拦截该导弹时，就不得不启用新系统。如果已有系统中有一个能拦截该导弹，我们是应该继续使用它，还是另起炉灶呢？事实是：无论用哪套系统，只要拦截了这枚导弹，那么系统的瞄准高度就等于导弹高度，这一点对旧的或新的系统都适用。而新系统能

13、拦截的导弹高度最高，即新系统的性能优于任意一套已使用的系统。既然如此，我们当然应该选择已有的系统。如果已有系统中有多个可以拦截该导弹，究竟选哪一个呢？当前瞄准高度较高的系统的“潜力”较大，而瞄准高度较低的系统则不同，它能打下的导弹别的系统也能打下，它够不到的导弹却未必是别的系统所够不到的。所以，当有多个系统供选择时，要选瞄准高度最低的使用，当然瞄准高度同时也要大于等于来犯导弹高度。,常州市第一中学 林厚从,“拦截导弹”问题分析,解题时用一个数组sys记下当前已有系统的各个当前瞄准高度，该数组中实际元素的个数就是第二问的解答。,sys1:=h1;tail:=1;for i:=2 to n dob

14、egin minheight:=maxint;for j:=1 to tail do 找一套最适合的系统 if sysjhi then if sysjminheight then begin minheight:=sysj;select:=j end;if minheight=maxint 开一套新系统 then begin tail:=tail+1;systail:=hi end else sysselect:=hiend;writeln(total=,tail);,常州市第一中学 林厚从,动态规划简介,数字三角形（IOI1994）问题描述 如下所示为一个数字三角形：73 88 1 02 7

15、 4 44 5 2 6 5 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。规定：每一步可沿直线向下或右斜线向下走；1三角形行数100；三角形中的数字为整数0，1，99；,样例输出：30,常州市第一中学 林厚从,动态规划简介,分析数字三角形,1、穷举法：最多100行，有299条路径，超时；,2、贪心法：不正确；,3、动态规划：,假设从顶至数字三角形的某一位置的所有路径中，所经过的数字的总和最大的那条路径，我们称之为该位置的最大路径。由于问题规定每一步只能沿直线向下或沿斜线向右下走，若要走到该位置，则其前一位置必为其左上方或正上方两个位置之一，由此可知，当前位置的最优路

16、径必定与其左上方或正上方两个位置的最优路径有关，且来自于其中更优的一个。,常州市第一中学 林厚从,动态规划简介,设ai，j表示数字三角形中第i行第j列的数，再设一个二维数组sum记录每个位置的最优路径的数字总和，则：,sumi，j=maxsumi-1，j，sumi-1，j-1+ai，j 其中：2=i=n，2=j=i,边界条件：sumi，1=sumi-1，1+ai，1 第1列sumi，i=sumi-1，i-1+ai，i 对角线,这个问题呈现出明显的阶段性：三角形的每一行都是一个阶段。对最大路径的求解过程，实际上是从上往下不断地按照阶段的顺序求解。对问题适当地划分阶段是动态规划解题中的一个重要步骤

17、。,常州市第一中学 林厚从,动态规划简介,fillchar(sum,sizeof(sum),0);初始化为0sum1,1:=a1,1;for i:=2 to n do 逐行动归 for j:=1 to i do if sumi-1,j-1sumi-1,j then sumi,j:=sumi-1,j-1+ai,j else sumi,j:=sumi-1,j+ai,j;ans:=0;打擂台求最优值for j:=1 to n do if sumn,jans then ans:=sumn,j;writeln(ans);,Var sum:array1.maxn,0.maxn of longint;,程序

18、中为什么没考虑j=1或j=i的情况？,常州市第一中学 林厚从,思考题 假如本题还要你输出最大值的那条路径，即不仅要求出最优值、还要你构造出最优方案，你怎么办呢？,用1个三维数组 sum1.maxn,0.maxn,1.2来记忆最优值及最优值的来源，在递推的同时记下路径，即：sumx,y,1表示第x行、y列能够取得的最大值，sumx,y,2表示该最大值是从上一行的哪个位置得来的（如-1表示从左上方得到的，0表示从正上方得到的）。最后输出时，从下往上倒过来推即可！,动态规划简介,常州市第一中学 林厚从,动态规划的基本概念,1、阶段 用动态规划求解一个问题时，需要将问题的全过程恰当地划分成若干个相互联

19、系的阶段，以便按一定的次序去求解。阶段的划分一般是根据时间和空间的自然特征来定的，一般要便于把问题转化成多阶段决策的过程。,2、状态 状态表示的是事物某一阶段的性质，状态通过一个变量来描述，这个变量称为状态变量。各个状态之间是可以相互转换的。,3、决策 对问题的处理中做出某种选择性的行动就是决策。一个实际问题可能要有多次决策，在每一个阶段中都需要有一次决策。一次决策就会从一个阶段进入另一个阶段，状态也就发生了转移。,常州市第一中学 林厚从,动态规划的基本概念,4、策略和最优策略 所有阶段按照约定的决策方法，依次排列构成问题的求解全过程。这些决策的总体称为策略。在实际问题中，从决策允许集合中找出

20、最优效果的策略称为最优策略。,5、状态转移方程 前一阶段的终点就是后一阶段的起点，这种关系描述了由K阶段到K+1阶段状态的演变规律，是关于两个相邻阶段状态的方程，称为状态转移方程，是动态规划的核心。,6、指标函数和最优化概念 用来衡量多阶段决策过程优劣的一种数量指标，称为指标函数。它应该在全过程和所有子过程中有定义、并且可度量。指标函数的最优值，称为最优值函数。,常州市第一中学 林厚从,动态规划的基本概念,动态规划所处理的问题是一个“多阶段决策问题”目的是得到一个最优解（方案）大概思想如下图所示：,常州市第一中学 林厚从,运用动态规划的条件,1、最优化原理,作为整个过程的最优策略具有：无论过去

21、的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。也可以通俗地理解为：子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质。也就是说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。,比如前面的数字三角形问题，如果我们想求走到某一位置的最优路径，我们只需要知道其左上方或正上方两个位置之一的最优值，而不用考虑其它的路径，因为其它的非最优路径肯定对当前位置的结果没有影响。,常州市第一中学 林厚从,运用动态规划的条件,1、最优化原理,在数字三角形问题中，如果我们把问题稍微改变一下：将三角形中的数字改为-100100之间的整数，计

22、算从顶至底的某处的一条路径，使该路径所经过的数字的总和最接近于零。,这个问题就不具有最优子结构性质了，因为子问题最优，即最接近于零，反而可能造成问题的解远离零，这样的反例是不难构造的，本问题就不能用动态规划的方法解决了。,因此，并不是所有的“决策问题”都可以用“动态规划”来解决。只有当一个问题呈现出最优子结构时，“动态规划”才可能是一个合适的侯选方法。,常州市第一中学 林厚从,运用动态规划的条件,2、无后效性原则,1、最优化原理,所谓无后效性原则，指的是这样一种性质：某一阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说“未来与过去无关”。当前的状态是此前历史的一个完整

23、总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段I中的状态只能由阶段I+1中的状态转移方程得来，与其他没有关系，特别是与未发生的状态没有关系，这就是无后效性。,常州市第一中学 林厚从,运用动态规划的条件,2、无后效性原则,1、最优化原理,例如：给定一个平面上的n个点的坐标，规定必须从最左边一个点开始，严格地从左至右访问到最右边的点，再严格地由右向左访问到出发点，编程确定一条连接各个点的闭合的游历路线，要求整个路程最短的路径长度。,分析：本题可以根据起点，终点划分阶段，且满足无后效性原则，可以考虑用动态规划做。但如果把“规定必须从最左边一个点

24、开始，严格地从左至右访问到最右边的点，再严格地由右向左访问到出发点”这个限制条件去掉，则阶段与阶段之间没有什么必然的“顺序”，而且把各个阶段画成一个图后会出现“环路”，所以有“后效性”，就不能用动态规划做了。,常州市第一中学 林厚从,动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）解。若存在多个最优解的话，它只取其中的一个。,动态规划的基本概念,常州市第一中学 林厚从,动态规划应用举例,例1、挖地雷（NOI

25、P1996）在一个地图上有N个地窖（N=200），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。,输入 N 地窖的个数 W1 W2WN 每个地窖中的地雷数 X1 Y1 表示可从X1到Y1 X2 Y2 0 0 表示输入结束,输出 K1K2Kv 挖地雷的顺序 MAX 最多挖出的地雷数,输入：65 10 20 5 4 51 21 42 43 44 54 65 60 0,输出：3-4-5-634,常州市第一中学 林厚从,挖地

26、雷问题分析 设W（i）为第i个地窖所藏有的地雷数，A（i,j）表示第i个地窖与第j个地窖之间是否有通路，F（i）为从第i个地窖开始最多可以挖出的地雷数。,动态规划应用举例,F（i）=MAX F(j)+W(i),(ij=n,A(i,j)=1),边界：F（n）=W(n),于是就可以通过递推的方法，从后（即F（n）往前逐个找出所有的F（i），再从中找一个最大的即为第2问的解。对于具体所走的路径（第2问），可以通过一个向后的链接来实现。,常州市第一中学 林厚从,动态规划应用举例,例2、接苹果(apples)农场的夏季是收获的好季节。在John的农场，他们用一种特别的方式来收苹果：Bessie摇苹果树，

27、苹果落下，然后John尽力接到尽可能多的苹果。作为一个有经验的农夫，John将这个过程坐标化。他清楚地知道什么时候(1=t=1,000,000)什么位置(用二维坐标表示，-1000=x,y=1000)会有苹果落下。他只有提前到达那个位置，才能接到那个位置掉下的苹果。一个单位时间，John能走s(1=s=1000)个单位。假设他开始时(t=0)站在(0,0)点，他最多能接到多少个苹果？,输入：第一行是两个整数N(苹果个数，N=5000)和S(速度)；第2.N+1行：每行3个整数Xi,Yi,Ti，表示每个苹果掉下 的位置和落下的时间。输出：仅一行，一个数，表示最多能接到几个苹果。,常州市第一中学

28、林厚从,动态规划应用举例,样例apples.in5 30 0 10 3 2-5 12 6-1 0 3-1 1 2apples.out3说明：John可以接到第1,5,4个苹果。,常州市第一中学 林厚从,动态规划应用举例,接苹果问题分析 首先划分阶段，很明显，按照苹果掉落的时间先后顺序来划分阶段，所以有必要按时间从小到大给各个苹果排个序，并按顺序标上1.n的编号。,假如John现在正站在某个位置上接苹果，为了使他到当前为止接到的苹果数最大，我们想要知道的是他前一步在哪个位置接苹果，并且要知道到那个位置为止接到的苹果最多是多少。,假设dis(i，j)表示第i个苹果与第j个苹果之间的直线距离。tim

29、e(i)表示第i个苹果掉落的时刻。F(i)表示John当前站在第i个苹果的位置上最多能接到的苹果总数（包括他以前接的）。,F(i)=max F(j)+1 其中0=j=i-1，且dis(i,j)=(time(i)-time(j)*S,初始条件：F(0)=0表示John站在出发点(0,0)时一个苹果也没接到。,常州市第一中学 林厚从,动态规划应用举例,例3、低价购买（buylow）“低价购买”这条建议是在股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的购买建议：低价购买，再低价购买。每次你购买一支股票，你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以

30、上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(216范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买，再低价购买”的原则。写一个程序计算最大购买次数。这里是某支股票的价格清单：日期 1 2 3 4 5 6 7 8 9 10 11 12价格 68 69 54 64 68 64 70 67 78 62 98 87 最优秀的投资者可以购买最多4次股票，可行方案中的一种是：日期 2 5 6 10价格 69 68 64 62,常州市第一中学 林厚从,动态规划应用举例,输入 输入共两行，第1行为 N(1=N=5000)，表示股票发行天数；

31、第2行:N个数，是每天的股票价格。输出 输出两个数:最大购买次数和拥有最大购买次数的方案数(=231)当两种方案“看起来一样”时（就是说它们构成的价格队列一样时），这两种方案被认为是相同的。样例BUYLOW.IN1269 68 54 70 68 64 70 67 78 62 98 87BUYLOW.OUT4 4,先探索一下样例，最大购买次数为4次，共有4种方案，分别为：69、68、64、6269、68、67、6270、68、64、6270、68、67、62,常州市第一中学 林厚从,动态规划应用举例,我们发现，这道题和“导弹问题”的几乎完全相同！实际上是在一个数列中选出一个序列，使得这个序列是一

32、个下降序列（即序列中的任意一个数必须大于它后面的任何一个数），且要使这个序列的长度最长。但是这道题要输出总的方案数，这就需要对原有的求解过程作一些变动。求方案总数最主要的是要剔除重复方案。在样例中，第2和第5个数都是68。以第一个68结尾的最长下降序列的方案为69、68；以第二个68结尾的最长下降序列的方案为69、68 和70、68这时候就产生了方案的重复，即产生了两个69、68。显然后面的68要比前面一个更优，因为后面的68位置更靠后，以这个68结尾的最长下降序列的总数肯定要比前面一个多，而且其方案必定囊括了前面一个68的所有方案。因此，在解题过程中，我们就可以只考虑后面一个68。推广开来，

33、如果当前状态之前存在重复的状态，我们只要考虑离当前状态位置最近的那一个即可。,常州市第一中学 林厚从,动态规划应用举例,设F（i）表示到第i天，能够购买的最大次数。,其中：1=j=i-1，且OKj=trueOKj=true表示相同价格时，该位置更优。,F（1）=1,F（i）=max F(j)+1,常州市第一中学 林厚从,总 结,1、递推的边界条件一般很明显，而动态规划的边界条件比较隐蔽，容易被忽视；2、递推的数学性一般较强，而动态规划的数学性相对较弱；3、递推一般不划分阶段，而动态规划一般有较为明显的阶段；4、动态规划往往是用来求一个最优值，而一般的递推往往是用来计数或是求一个值。,动态规划和一般递推的不同点？,动态规划和一般递推的相同点？,无后效性和有边界条件。,小结及作业,上机调试所有课堂上的例题。,