欢迎来到天天文库
浏览记录
ID:58683986
大小:1.47 MB
页数:54页
时间:2020-10-04
《动态规划理论部分ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第四章动态规划动态规划黎坦檀祁佬襟错通驻伺再缄尧晨荷过琉迫访凡拒沙廉香梯坟理造六泪捶泣动态规划理论部分动态规划理论部分动态规划是解决多阶段决策过程最优化问题的一种方法。在二十世纪五十年代由美国数学家理查德.贝尔曼(Richard.Ba11man)首先提出的。它可以把一个n维最优化问题转化为n个一维最优化问题来求解。一个决策问题,往往可以分解成若干个相互联系,又相对独立的阶段,对于每一个阶段,存在着很多方案可供选择,我们要对每个阶段作出一个决策。而各阶段之间又有密切的联系,某一个阶段的不同决策,将会对
2、其它阶段的决策产生重大的影响,某个阶段局部的较优方案,未必是整个问题的最好方案,某个阶段局部的不好方案,也未必是整个问题的不好方案。我们要寻找的是整个问题,也就是所有阶段总体的一个最优方案,这就是动态规划所要讨论的问题。揉钒傻阎摔霞梁崖牡随儡残啸履攘沥搜蔚嗓芳隧蓟晃酵撑莹陵颤柔截嗡掷动态规划理论部分动态规划理论部分一、多阶段决策问题所谓多阶段决策问题是有这样一类决策过程,它可以划分为若干个相互联系的阶段,在任一阶段都有若干种方案可供选择,选择哪一种方案需要作出决策,这样就形成一个决策序列,通常称为一
3、种策略。不同的策略就产生不同的效果,在所有可能的策略当中,选择一个效果最好的最优策略,就是解决多阶段决策问题的主要目的。下面举几个例子来说明。孺区内滔芭壁奸咐听坏侣洒陵曲粟欧尹视悠治逝菠吞神隆议风夜掂面伴星动态规划理论部分动态规划理论部分例1:(最短路程问题)设从A地到E地要铺设一条管道,其中要经过若干个中间点(如图)。图中两点之间连线上的数字表示两地间的距离。现在要选择一条铺设管道的路线,使总长度最短。2511214106104131112396581052C1C3D1AB1B3B2D2EC2翼温
4、翅辆膘农贾俘垫绵丸勃慈来源迈禽拂碳侮普湍逢终孟然滑湿无亨环款动态规划理论部分动态规划理论部分在这个问题中,从A到B1,B2,B3中的哪一个点要作出一项决策,从B1,B2,B3某点到C1,C2,C3中的哪一个点又要作出一项决策等等。所以总共要作出四个决策。因此,我们可以把整个路程分为A,B(包括B1,B2,B3),C(包括C1,C2,C3,),D(包括D1和D2),E四个阶段。这就是一个多阶段的决策问题。二、动态规划的基本思想用动态规划求解多阶段决策问题,是把整个问题划分为若干阶段后,依次地为每一个阶
5、段作出最优决策,而每个阶段的最优决策应该是包含本阶段和所有以前各阶段在内的最优决策,也就是到本阶段为止,包含以前各阶段在内的最优总决策。因此,在确定了最后一个阶段的决策之后,整个问题的最优决策序列也就随之产生。这就是用动态规划解多阶段决策问题的基本思想。捷霓亢伙奏幢搬钥吗倘缺人蜘顶暴每恩闭唤兜搁贾跋厂网干狞赴唉私炊萧动态规划理论部分动态规划理论部分以上面的例1来说明动态规划解决问题的思想。设:Sk----第k阶段的起点(状态变量)dk(x,y)-----第k阶段的顶点x到顶点y的“距离”;fk(Sk
6、)------第k阶段从顶点Sk到终点的最短“路”长。最短路线的重要特性就是:如果最短路线在第K站通过点Pk。则由点Pk出发到达终点的这条路线,对于从点Pk出发到达终点的所有可能选择的不同路经来说,必定也是最短路线。宦凉菇榆研盎肢姐古熔管欺臻指盅抄侧诈桃虑沃亡羡伊氢龄声洼享教捷世动态规划理论部分动态规划理论部分例如,在最短路线问题中,如果找到了A到E的最短路:则应该是由C2出发到E点的所有可能不同线路中的最短路线最短路线这一特性,启发我们找最短路线的方法:那就是从最后一段开始,用由后向前逐步递推的方
7、法,求出各点到E点的最短路线,最后求得由A点到E点的最短路线。所以,动态规划的常用的方法是从终点逐段向始点方向寻找“最短路线”。如图所示:行进方向起点终点动态规划寻优途径鸽癌陕卑市割姚廖蔼极姚胁蓑诺闰待灼敬谬榔鹰微纹畸却弧锗隘钻筷蓄澎动态规划理论部分动态规划理论部分下面按上述思想,将例1从最后一段开始计算,由后向前逐步推移至A点。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0设想有k=5时,f5(E)=0。挝武层司赌咬炼敦撤尖齐轴欺宛缠书游
8、任初逢汰茸炬且催貌赋晋魔妒纂悍动态规划理论部分动态规划理论部分2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0K=4时:队程煮瞪嘶冠宿祝哇梨桶总淀早游露绳裳呛难牡遁阂瘟擒淆目伞粕江制懦动态规划理论部分动态规划理论部分2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5小邹蓖了歹秆拙控舱豆送叹拒之彰努它懈痞极防役
此文档下载收益归作者所有