动态规划(普及组-吴建锋).ppt_第1页
动态规划(普及组-吴建锋).ppt_第2页
动态规划(普及组-吴建锋).ppt_第3页
动态规划(普及组-吴建锋).ppt_第4页
动态规划(普及组-吴建锋).ppt_第5页
已阅读5页,还剩65页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、动态规划(普及组),绍兴柯桥中学 吴建锋,认识动态规划,动态规划在运筹学等领域都得到很大的运用,它是求解最优化分阶段决策问题的一种数学方法,大约产生于50年代。1951年美国数学家Bellman等人根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决。与此同时,他提出了解决这类问题的“最优性原理”,研究了许多实际问题,从而创建了解决最优化问题的一种新的方法动态规划。,多阶段决策过程,1,2,3,n,“动态”的内涵,在分阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前的状态,又随即引起状态的改变(转移),一个决策序列就是在变化

2、的状态中产生出来的,所以有“动态”的含义。因此,把处理它的方法称为动态规划方法。,问题1:求最短路径长度,假如有下图所示的交通示意图,有向边上的数值表示边的长度,求A到D的最短路径的长度 。,A,B,C,D,13,19,28,15,解法1:从初始阶段出发的顺推求解,1、用fi表示A到结点i的最短距离 2、我们可以求得fA=13,fB19 (第一阶段) 3、第二阶段求解过程如下: fB+28=41 fD的候选最优解 fC+15=34 fD的候选最优解 4、保存较优解:fD=minfB+28,fC+15,解法2:目标阶段出发的逆推求解,1、如果用fi表示编号为i的结点到终点d的最短距离,那么动态规

3、划分阶段求解的过程如下所示: (1)fD:=0 初始化 (2)fB:=28+fD; fC:=15+fD 第一阶段求解 (3)fA:=min13+fB,19+fC 状态转移方程的体现,第二阶段求解,什么叫状态转移方程,对于当前阶段的某个状态,必定有有上个阶段的子问题的某一批状态通过对应的决策变换而来,这些子问题的一批状态通过对应的决策应用,就导致了状态转移,新的状态就是当前阶段的某个状态。由于这个新状态的子状态可能不止一个,所以决策后的对应局部解也可能不止一个,在这些解中取一个最优解,就是当前阶段当前状态的最优解,这个求最优解的过程可用一个表达式来描述,这个表达式就是状态转移方程。,状态转移方程

4、应用举例,在下列交通路线中,求节点1到节点10 的最短路径的长度。,1,4,3,2,6,5,9,8,7,10,13,21,9,15,17,3,24,5,27,11,13,8,19,16,25,11,20,分阶段决策的手工计算,第一阶段: f2=f1+13=13;f3=f1+21=21;f4=f1+9=9 第二阶段: f5=minf2+15,f3+17,f4+24=28; f6=minf2+3,f3+5,f4+27=16 第三阶段: f7=minf5+11,f6+8=24; f8=minf5+13,f6+19=35; f9=minf6+16=32,目标阶段求解,第四阶段: f10=minf7+2

5、5,f8+11,f9+20=46,具体化的状态转移方程,1、f5=minfj+x,,f6=minfk+y, 2、fj+x中的fj就是上阶段子问题各状态的最优解 ;而x则是某个子状态转移到当前状态产生的决策效应(或者是代价),一般化的状态转移方程,实际编程实现时,状态转移方程往往是一个通用计算式,在这个通用计算式中往往会包含各种子状态、子状态对应子问题的最优解、决策等参数。,动态规划的算法设计,如果用i表示当前需求解的阶段号(有时为了描述的方便,i也可表示当前阶段的前一个阶段),j表示当前阶段各个状态(或者说是阶段的各个节点编号),k表示前一阶段各个子状态能选择的策略,用fI,j表示起点1到第i

6、阶段编号为j的结点(也可理解为状态)的最短距离,那么上面问题用动态规划求解的大致程序结构如下:,穷举所有的阶段(for i:=1 to 4 do) 穷举当前阶段i所有可能的状态j 穷举j状态所有对应的子状态的所有可选择的策略k FI,j:=minfi-1,j1+xj1,k | j1表示状态j所有可能的子状态,程序代码实现,输入数据: 2 3 4 0 5 6 0 7 8 9 0 10 0 0 13 21 9 maxint maxint maxint maxint maxint maxint maxint 0 maxint maxint 15 3 maxint maxint maxint maxi

7、nt maxint maxint 0 maxint 17 5 maxint maxint maxint maxint maxint maxint maxint 0 24 27 maxint maxint maxint maxint ,数据结构,AI,j=k表示第i阶段的第j个决策点(后继节点)是k; DI,j=k表示i和j节点之间的直接联边长度是k,如果是maxint则表示没有直接联边。如果是0则表示节点本身。,程序框架,for i:=1 to 4 do begin j:=1; repeat j2:=aI,j; k:=1; repeat j1:=ai-1,k; if dj1,j2maxint

8、then fI,j2:=minfI,j2,fi-1,j1+dj1,j2 inc(k); until ai-1,k=0; inc(j); until aI,j=0; end;,一些关键的要素,1、阶段 每个阶段的处理是相同的。 2、状态 每个抽象化的节点所共有的特性值。 3、决策 所选择的处理。,分析动态规划,1、何时可考虑动态规划 2、阶段、状态、决策如何提炼 3、如何抽象出状态转移方程,问题2:数字三角形,下图所示为一个数字三角形,其中三角形中的数值为不超过100的整数,现规定从最顶层往下走到底层,每一步可沿左斜线向下或右斜线向下走。 7 3 8 8 1 0 2 7 4 4 4 5 2 6

9、5 假设三角形行数=100,编程计算从最顶层走到最底层的一条路径,使得沿着该路径所经过的数字之和最大,输出最大值。,输入和输出,trigon.in 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 trigon.out 30,为什么可用动态规划,7 3 8 8 1 0 2 7 4 4 4 5 2 6 5,算法设计,1、阶段就是行号 2、状态就是每行上的某个数字(位置号表示) 3、决策就是向右(还是向左)的走法。,状态转移方程,若用fI,j表示起点到i阶段第j个数字的最优解,用j1表示j对应的子状态,xj1,k表示j1子状态变换到j状态中的第k个决策所产生的决策效应,则可写出状态转移方

10、程如下: fI,j=maxfi-1,j1+xj1,k | j1和k最多取二个值,结合数据结构调整方程,根据输入数据特点,考虑用aI,j保存第i行第j个位置上的数字,那么前面方程中j1可取的值为j-1和j,所以状态转移方程可细化为: fI,j=maxfi-1,j+aI,j,fi-1,j+1+aI,j 其中1=i=n,1=j=i,初始化时f1,1=7。,写出核心程序段,fillchar(f,sizeof(f),0); f1,1:=a1,1; for i:=2 to n do 枚举阶段 for j:=1 to I do 枚举状态 for k:=j-1 to j do 枚举决策 if fI,jfi-1

11、,k+aI,j then fI,j:=fi-1,k+aI,j;,这样最后求得的fn,n是否是本问题的最优解?,问题3:彩石运输,阿强是一个汽车运输工,他正在给一项装饰工程运输所需的彩色石头。这些石头的颜色各异,价格也各不相同。有一天阿强突发奇想,他想在一堆彩石中有选择地把彩石装上他的卡车,使得卡车上装载的石头总价值是所有装载方案中最大的。现在有一堆彩石堆放在阿强面前,他知道任何两块石头的颜色都是不同的,但两块颜色不同的石头的重量和价格可能相同。 阿强的卡车总共可装载的重量是W,而且他知道总的彩石的块数,请你帮助阿强确定一个方案,满足阿强的奇想。 输入文件stone.in的第一行是二个整数,依次

12、表示卡车的载重量W和总的彩石块数n,下面共有n行,每行包含二个用空格分隔的整数,依次表示某种颜色彩石的重量和价值。 输出文件stone.out只包含一行一个整数,表示卡车最终装载彩石的最大总价值。,输入输出,stone.in 30 5 20 50 10 30 15 44 5 14 4 13 stone.out 88,问题分析,1、有些选手会陷入二种错误的贪心算法中 2、为什么可用动态规划 3、3个要素的分析 (1)阶段 (2)状态 (3)决策,提炼出状态转移方程,用wi保存第i种彩石的重量,用pi表示它的价值,用j表示状态,则状态转移方程如下: fI,j=maxfi-1,j-wi+pi,fi-

13、1,j,核心程序代码,fillchar(f,sizeof(f),0); for i:=1 to n do for j:=1 to w do begin fI,j:=fi-1,j; if (wi=w) and (fI,jfi-1,j-wi+pi) then fI,j:=fi-1,j-wi+pi; end; write(fn,w);,问题4:joy的工具箱,Joy是一位非常出色的汽车维修工,而且他的创业能力也很强,这不,最近他成立了自己的汽车维修110公司,一旦汽车在半途抛锚,只要一个电话,joy就会立刻带着他的工具箱赶到事故地点,为驾驶员朋友维修汽车,由于抢修及时以及维修技术高,汽车维修110公

14、司的生意越来越红火。 但joy是一个追求无止境的人,在生意越做越大的同时,他又动开了新脑筋。他发现无论维修工具箱买得如何大,肯定不能把他公司里所有的维修工具装进去,100的故障排除率不仅需要精湛的维修技术,如何选择并把最为合适的维修工具装入工具箱,并把工具箱带到故障现场,也是一个非常重要的技巧。由于工具众多,joy无法根据驾驶员报告的故障现象确定最为合适的一些工具,作为朋友的你决定通过程序来帮助joy选择最为合适的工具转入到工具箱中。,当然,joy会事先告诉你一些必要的信息。比如,他的每个工具都是不同的,工具箱的总体积,joy还会告诉你他根据故障特点给每个工具合适程度的效率分数,你的程序必须能

15、确定哪些工具被装入工具箱,并输出总的最大效率分。,输入文件joy.in第一行包含二个整数v和n,分别表示工具箱总体积和所有可供选择的工具的数量。下面共有n行,每行有二个用空格分隔的整数,依次分别表示每个工具的体积大小和joy给定的效率分。 输出文件joy.out包含一个整数,表示在工具箱有限的空间内,所装入的所有工具的效率分数的最大值。,输入和输出,joy.in 23 5 11 20 9 19 10 15 7 14 8 15 joy.out 39,关键要素分析,1、阶段 2、状态 3、决策,分析状态转移方程,FI,j表示前i个工具选择部分装入占用容量为j的工具箱中的最大效率分: fi,j:=m

16、axfi-1,j-v1i+pi |,核心程序段,fillchar(f,sizeof(f),0); for i:=1 to n do for j:=1 to v do begin fi,j:=fi-1,j; if (v1i=j) and (fi,jfi-1,j-v1i+pi) then fi,j:=fi-1,j-v1i+pi; end; write(fn,v);,动态规划的应用(问题5),导弹拦截。某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于

17、该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000 的正整数),计算这套系统最多能拦截多少导弹?如果要拦截所有导弹最少要配备多少套这种导弹拦截系统?,输入和输出,missile.in 389 207 155 300 299 170 158 65 missile.out 6(最多能拦截的导弹数) 2(要拦截所有导弹最少要配备的系统数),顺推求解,1、用fi表示从第1枚导弹到第i枚导弹这个子问题的最优解(包含这枚导弹的决策序列),aj表示第j枚导弹的高度。 2、开始时所有的fi都初始化为1 3、i从2开始直到n进行顺推

18、计算所有的fi 4、最后输出最大的fi,某个阶段i的fi求解,1、fi的子问题是哪些? 2、fi子问题的最优解保存在哪里? 3、如何根据子问题的最优解推算父问题的最优解?,状态转移方程,Fi=maxfj+1 | 必须满足的是所有的aj都必须不小于ai,核心程序段,fillchar(f,sizeof(f),1); best:=1; for i:=2 to n do begin for j:=1 to i-1 do if (aj=ai) and (fj+1fi) then fi:=fj+1; if bestfi then best:=fi; end; write(best);,逆推求解,如何进行?

19、,问题6:乘积最大,在一次数学智力竞赛中,主持人给所有参加活动的选手出了一道题目:设有一个长度为N的数字串,要求选手使用M个乘号将它分成M1部分,求出一种分法,使得这M+1个部分的乘积最大。 同时,为了帮助选手能够理解题意,主持人还举了如下一个例子: 有一个数字串:312,当N=3,M=1时有二种分法: (1)31236; (2)31262 这时,符合题意要求的结果是:31262。现在要求设计一个程序,以求得正确的答案。 输入文件product.in第一行包含二个整数,分别表示N,M(2=N=10,1=M=5),第二行是一个长度为N的数字串。 输出文件product.out包含一行一个自然数,

20、表示求得的最大乘积。,输入和输出,product.in 4 2 1231 product.out 62,算法分析,1、本来用搜索也可 2、n,m扩大时,必须用动态规划 3、用fI,j表示在前i个数字中插入j个乘号可以获得的最大值,那么fn,m就是问题的最优解。,特殊到一般抽象出转移方程,1、显然fI,j这个最优解肯定是在下列情形中产生的: fj,j-1*Aj+1Ai fj+1,j-1*Aj+2Ai fi-1,j-1*Ai,2、提炼出初步的转移方程: fI,j=maxfi1,j-1*(ai1+1ai) | j=i1=i-1 3、其中的(ai1+1ai)表示第i1+1位到第i位数字串所组成的整数。

21、,勾画出初步的代码,For i:=1 to n do For j:=0 to m do If j=i-1 then For i1:=j to i-1 do If fI,jfi1,j-1*num(ai1+1ai); *开始时所有的fI,j初始化为0,思考,1、有没有发现算法中的漏洞? 2、分析边界、确定递推初始值中完善算法,完善后的算法,所有的fI,j初始化为0; for i:=1 to n-m do fI,0:=num(a1ai); For i:=2 to n do For j:=1 to m do If j=i-1 then For i1:=j to i-1 do If fI,jfi1,j-

22、1*num(ai1+1ai);,注意的细节,实际编程时还须使用高精度算法,由于这里着重介绍动态规划,故本过程省略。,问题7:校庆100周年,在柯中建校100周年之际,学校决定举办校庆活动,发出校庆通告和邀请后,学校收到了k多的祝贺条幅,在把这些条幅挂起来的时候,学校负责人要考虑到祝贺单位和个人的知名度和发送祝贺的先后顺序,觉得有必要统筹地安排位置来挂这些条幅。 在柯中校门口的正面,有一座气势雄伟的综合楼,前面有n(1=k=n=100)多的位置可以用来挂条幅,如何把这k条条幅挂到这n个位置上使之总体效果最大呢?学校负责人是这样考虑的:首先给所有条幅按照送来的顺序从1开始编号,然后给综合楼可挂条幅

23、的位置也从1开始编号,无论怎么考虑最大效果,编号小的条幅必须挂在编号大的条幅的前面(即所在位置的编号较小);但考虑到送条幅单位或个人知名度的问题,负责人又给每个条幅挂在每个位置上的效果打了分。最终希望挂条幅的效果分到达最大。,输入文件aniversary.in第一行包含二个空格分隔的整数k和n,分别表示总条幅数量和总的可挂条幅的数量。下面一共有k行,每行有n个空格分隔的整数,输入文件第i+1行第j列的整数表示编号为i的条幅挂在编号为j的位置上的效果分(在50到50之间)。 输出文件aniversary.out包含一行一个整数,表示可能获得的最大的效果分。,输入和输出,aniversary.in 3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20 aniversary.out 53,三要素分析,1、横幅作为阶段I 2、前i个横幅放置所占的前j个位置作为状态 3、决策就是第i个横幅放置在前j个位置的哪个位置上,状态转移方程,用ansI,j表示前i个横幅放入前j个位置,并且第i个横幅放置于第j个位置上的最优解。 AnsI,j

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论