第二次课动态规划.pptx
《第二次课动态规划.pptx》由会员分享,可在线阅读,更多相关《第二次课动态规划.pptx(83页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 动动 态态 规规 划划 是是 19511951年年 由由 美美 国国 数数 学学 家家 贝贝 尔尔 曼曼(Richard Richard Bellman)Bellman)提提出出,它它是是解解决决一一类类多多阶阶段段决决策策问问题题的的优优化化方方法法,也是考察问题的一种途径。也是考察问题的一种途径。动动态态规规划划方方法法是是现现代代企企业业管管理理中中的的一一种种重重要要决决策策方方法法。如如果果一一个个问问题题可可将将其其过过程程划划分分为为若若干干个个相相互互联联系系的的阶阶段段问问题题,且且它它的的每每一一阶阶段段都都需需进进行行决决策策,则则这这类类问问题题均均可可用用动动态态规
2、规划划方法进行求解。方法进行求解。根根据据多多阶阶段段决决策策过过程程的的时时序序和和决决策策过过程程的的演演变变,动动态态规规划划方方法法有有以以下下四四种种类类型型:离离散散确确定定型型、离离散散随随机机型型、连连续续确确定定型和连续随机型型和连续随机型。第1页/共83页几类算法的经典名言几类算法的经典名言动态规划:不做重复的事;动态规划:不做重复的事;动态规划:不做重复的事;动态规划:不做重复的事;贪心法:只选最好的;贪心法:只选最好的;贪心法:只选最好的;贪心法:只选最好的;分支定界法:没戏的就杀掉;分支定界法:没戏的就杀掉;分支定界法:没戏的就杀掉;分支定界法:没戏的就杀掉;回溯法:
3、碰壁就回头。回溯法:碰壁就回头。回溯法:碰壁就回头。回溯法:碰壁就回头。作人生规划要善于利用动态规划;作人生规划要善于利用动态规划;找女朋友要善于利用好贪心算法;找女朋友要善于利用好贪心算法;人生重大决策要活学活用回溯法;人生重大决策要活学活用回溯法;第2页/共83页算法总体思想算法总体思想算法总体思想算法总体思想动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)=第3页/共83页为什么动态规划比递归
4、算法有效?为什么动态规划比递归算法有效?但是经分解得到的子问题往往不是互相独立的。不同子问题的数但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次,因此利用递归算法得到的算法往往是指数复杂度计算了许多次,因此利用递归算法得到的算法往往是指数复杂度的算法。的算法。如果能够保存已解决的子问题的答案,而在需要时再找出已求得如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。的答案,就可以避免大量重复计算,从而得到
5、多项式时间算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)第4页/共83页POJ 2753 FibonacciPOJ 2753 FibonacciPOJ 2753 FibonacciPOJ 2753 Fibonacci数列例子:数列例子:数列例子:数列例子:确定确定Fibonacci sequence fnFibonacci sequenc
6、e fn项的值项的值:考虑考虑Fibonacci sequenceFibonacci sequence的递归定义的递归定义:我们将得到如下的递归算法我们将得到如下的递归算法:在POJ上递交之后,返回的结果是:Time Limited。而不是可爱的ACWhy?第5页/共83页子问题的重叠性子问题的重叠性子问题的重叠性子问题的重叠性 将上述递归算法展开将上述递归算法展开:可以看出可以看出 f(n-1)f(n-1)被调用被调用 1 1次次,f(n-2),f(n-2)被调用被调用 2 2次次,等等等等.这将导致大量的调用这将导致大量的调用 最终解为:最终解为:第6页/共83页树形递归树形递归计算过程中
7、存在冗计算过程中存在冗余计算,为了除去余计算,为了除去冗余计算,可以从冗余计算,可以从已知条件开始计算,已知条件开始计算,并记录计算过程中并记录计算过程中的中间结果。的中间结果。f(5)f(3)f(2)f(1)f(2)f(4)f(0)f(1)f(0)f(3)f(2)f(1)f(1)f(0)f(1)11001010冗余计算冗余计算第7页/共83页动态规划动态规划例:例:POJ 2753 FibonacciPOJ 2753 Fibonacci数列数列int fn+1;int fn+1;f1=f2=1;f1=f2=1;int I;int I;for(i=3;i=n;i+)for(i=3;i=n;i+
8、)fi=fi-1+fi-2;fi=fi-1+fi-2;cout fn endl;cout fn endl;用空间换时间用空间换时间第8页/共83页动态规划算法的基本要素一、最优子结构一、最优子结构一个最优化策略具有这样的性质,不论过去状态和决策如何,一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其问题满足最优化原理又称其为为最优子结构性质最优子结构性质
9、。同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的求解速度更快(空间占用小,问题的维度低)例如:最短路径问题。a b c在分析问题的最优子结构性质时,所用的方法具有普遍性:首在分析问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的最优解导出的子问题的解不是最优的,然后再先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。而导致矛盾。第9页/共83页动态规划算法的基本要素二、重叠子问题二、重叠子问题递归算法求解问题时,每次产生的子问题并不总是新问题,有递
10、归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。些子问题被反复计算多次。这种性质称为这种性质称为子问题的重叠性质子问题的重叠性质。动态规划算法,对每一个子问题只解一次,而后将其解保存在动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间,从而获得较高的解题效率。态规划算法只需要多项式时间,从而获
11、得较高的解题效率。第10页/共83页一、例子(最短路问题)一、例子(最短路问题)假如上图是一个线路网络,两点之间连线上的数字表示两点假如上图是一个线路网络,两点之间连线上的数字表示两点间的距离(或费用),我们的问题是要将货物从间的距离(或费用),我们的问题是要将货物从A A地运往地运往E E地,地,中间通过中间通过B B、C C、D D三个区域,在区域内有多条路径可走,现三个区域,在区域内有多条路径可走,现求一条由求一条由A A到到E E的线路,使总距离最短(或总费用最小)。的线路,使总距离最短(或总费用最小)。AB1B2B3C1C2C3D1D2E24374632426534633334第11
12、页/共83页将该问题划分为将该问题划分为4 4个阶段的决策问题个阶段的决策问题第第一一阶阶段段为为从从A A到到B Bj j(j=1j=1,2 2,3 3),有有三三种种决决策策方方案案可可供供选选择;择;第二阶段为从第二阶段为从B Bj j到到C Cj j(j=1,2,3j=1,2,3),也有三种方案可供选择;),也有三种方案可供选择;第第三三阶阶段段为为从从C Cj j到到D Dj j(j=1,2)(j=1,2),有有两两种种方方案案可可供供选选择择;第第四四阶阶段为从段为从D Dj j到到E E,只有一种方案选择。,只有一种方案选择。AB1B2B3C1C2C3D1D2E243746324
13、26534633334第12页/共83页如如果果用用完完全全枚枚举举法法,则则可可供供选选择择的的路路线线有有3321=183321=18(条),将其一一比较才可找出最短路线:(条),将其一一比较才可找出最短路线:ABAB1 1CC2 2DD3 3EE其长度为其长度为1212。AB1B2B3C1C2C3D1D2E24374632426534633334第13页/共83页显然,这种方法是不经济的,特别是当阶段数显然,这种方法是不经济的,特别是当阶段数很多,各阶段可供的选择也很多时,这种解法很多,各阶段可供的选择也很多时,这种解法甚至在计算机上完成也是不现实的。甚至在计算机上完成也是不现实的。由于
14、我们考虑的是从全局上解决求由于我们考虑的是从全局上解决求A A到到E E的最短的最短路问题,而不是就某一阶段解决最短路线,因路问题,而不是就某一阶段解决最短路线,因此可考虑从最后一阶段开始计算,由后向前逐此可考虑从最后一阶段开始计算,由后向前逐步推至步推至A A点:点:第14页/共83页第四阶段,由第四阶段,由D D1 1到到E E只有一条路线,其长度只有一条路线,其长度f f4 4(D D1 1)=3=3,同理同理f f4 4(D D2 2)=4=4。第三阶段,由第三阶段,由C Cj j到到D Di i分别均有两种选择,即分别均有两种选择,即,决策点为D1AB1B2B3C1C2C3D1D2E
15、24374632426534633334第15页/共83页,决策点为D1,决策点为D2AB1B2B3C1C2C3D1D2E24374632426534633334第16页/共83页第二阶段,由Bj到Cj分别均有三种选择,即:决策点为C2 AB1B2B3C1C2C3D1D2E24374632426534633334第17页/共83页决策点为C1或C2决策点为C2 AB1B2B3C1C2C3D1D2E24374632426534633334第18页/共83页第一阶段,由A到B,有三种选择,即:决策点为B3f1(A)=15说明从A到E的最短距离为12,最短路线的确定可按计算顺序反推而得。即AB3C2
16、D2E上述最短路线问题的计算过程,也可借助于图形直观的表示出来:AB1B2B3C1C2C3D1D2E24374632426534633334第19页/共83页图图中中各各点点上上方方框框的的数数,表表示示该该点点到到E E的的最最短短距距离离。图图中中红红箭箭线表示从线表示从A A到到E E的最短路线。的最短路线。从引例的求解过程可以得到以下启示:从引例的求解过程可以得到以下启示:对对一一个个问问题题是是否否用用上上述述方方法法求求解解,其其关关键键在在于于能能否否将将问问题题转化为相互联系的决策过程相同的多个阶段决策问题。转化为相互联系的决策过程相同的多个阶段决策问题。AB1B2B3C1C2
17、C3D1D2E2437463242653463333434676991112第20页/共83页所所谓谓多多阶阶段段决决策策问问题题是是:把把一一个个问问题题看看作作是是一一个个前前后后关关联联具具有有链链状状结结构构的的多多阶阶段段过过程程,也也称称为为序序贯贯决决策策过过程程。如如下下图图所所示:示:在在处处理理各各阶阶段段决决策策的的选选取取上上,不不仅仅只只依依赖赖于于当当前前面面临临的的状状态态,而而且且还还要要注注意意对对以以后后的的发发展展。即即是是从从全全局局考考虑虑解解决决局局部部(阶段)的问题。(阶段)的问题。各各阶阶段段选选取取的的决决策策,一一般般与与“时时序序”有有关关
18、,决决策策依依赖赖于于当当前前的的状状态态,又又随随即即引引起起状状态态的的转转移移,整整个个决决策策序序列列就就是是在在变变化化的的状状态态中中产产生生出出来来,故故有有“动动态态”含含义义。因因此此,把把这这种种方方法称为动态规划方法。法称为动态规划方法。决策过程是与阶段发展过程逆向而行。决策过程是与阶段发展过程逆向而行。第21页/共83页拦截导弹(poj1887)某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有
19、一套系统,因此有可能不能拦截所有的导弹。第22页/共83页输入输入数据为导弹依次飞来的高度,所有高度值均为不大于30000的正整数。输出输出只有一行是这套系统最多能拦截的导弹数。第23页/共83页输入样例389 207 155 300 299 170 158 65输入样例6第24页/共83页题目分析因为只有一套导弹拦截系统,并且这套系统除了第一发炮弹能到达任意高度外,以后的每一发炮弹都不能高于前一发炮弹的高度;所以,被拦截的导弹应该按飞来的高度组成一个非递增序列。题目要求我们计算这套系统最多能拦截的导弹数,并依次输出被拦截导弹的高度,实际上就是要求我们在导弹依次飞来的高度序列中寻找一个最长非递
20、增子序列。第25页/共83页设X=x1,x2,xn为依次飞来的导弹序列,Y=y1,y2,yk为问题的最优解(即X的最长非递增子序列),s为问题的状态(表示导弹拦截系统当前发送炮弹能够到达的最大高度,初值为s=第一发炮弹能够到达任意的高度)。第26页/共83页如果y1=x1,即飞来的第一枚导弹被成功拦截。那么,根据题意“每一发炮弹都不能高于前一发的高度”,问题的状态将由s=变成sx1(x1为第一枚导弹的高度);第27页/共83页在当前状态下,序列Y1=y2,yk也应该是序列X1=x2,xn的最长非递增子序列(大家用反证法很容易证明)。也就是说,在当前状态sx1下,问题的最优解Y所包含的子问题(序
21、列X1)的解(序列Y1)也是最优的。这就是拦截导弹问题的最优子结构性质。第28页/共83页设D(i)为第i枚导弹被拦截之后,这套系统最多还能拦截的导弹数(包含被拦截的第i枚)。我们可以设想,当系统拦截了第k枚导弹xk,而xk又是序列X=x1,x2,xn中的最小值,即第k枚导弹为所有飞来的导弹中高度最低的,则有D(k)=1;当系统拦截了最后一枚导弹xn,那么,系统最多也只能拦截这一枚导弹了,即D(n)=1;其它情况下,也应该有D(i)1。第29页/共83页根据以上分析,可归纳出问题的动态规划递归方程为:第30页/共83页假设系统最多能拦截的导弹数为dmax(即问题的最优值),则 dmax (i为
22、被系统拦截的第一枚导弹的顺序号)第31页/共83页所以,要计算问题的最优值dmax,需要分别计算出D(1)、D(2)、D(n)的值,然后将它们进行比较,找出其中的最大值。第32页/共83页根据上面分析出来的递归方程,我们完全可以设计一个递归函数,采用自顶向下的方法计算D(i)的值。然后,对i从1到n分别调用这个递归函数,就可以计算出D(1)、D(2)、D(n)。第33页/共83页但这样将会有大量的子问题被重复计算。比如在调用递归函数计算D(1)的时候,可能需要先计算D(5)的值;之后在分别调用递归函数计算D(2)、D(3)、D(4)的时候,都有可能需要先计算D(5)的值。如此一来,在整个问题的
23、求解过程中,D(5)可能会被重复计算很多次,从而造成了冗余,降低了程序的效率。第34页/共83页其实,通过以上分析,我们已经知道:D(n)=1。如果将n作为阶段对问题进行划分,根据问题的动态规划递归方程,我们可以采用自底向上的方法依次计算出D(n-1)、D(n-2)、D(1)的值。这样,每个D(i)的值只计算一次,并在计算的同时把计算结果保存下来,从而避免了有些子问题被重复计算的情况发生,提高了程序的效率。第35页/共83页int main()int h2000,d2000,count,c,max,i,j;/h表示高度值,d表示最优值,c是能拦截得最多导弹数 count=0;while(sca
24、nf(%d,h+count+)!=EOF);/输入高度 dcount-1=1;c=1;for(i=count-2;icount;j+)if((hi=hj)&maxdj)max=dj;di=max+1;if(cdi)c=di;printf(%dn,c);第36页/共83页思考题上述问题修改成:要求拦截所有导弹,则需要多少套上述系统?第37页/共83页实例POJ2122:Flight PlanningYour job is to write a program that plans airplane flights.Each flight consists of a series of one o
25、r more legs.Your program must choose the best altitude for each leg to minimize the amount of fuel consumption during the trip.第38页/共83页The airplane has a fixed airspeed,given by the constant VCRUISE,and a most-efficient cruising altitude,AOPT.When flying at altitude AOPT,fuel consumption in gallons
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二次 动态 规划
限制150内