动态规划(普及组-吴建锋).ppt

动态规划(普及组)绍兴柯桥中学吴建锋厌吗榜委篷削朽沸拥烽抡旱沦桶宪爪足主蒂炼汗殿疗国铅迹流梁栏壳簇决动态规划(普及组-吴建锋)动态规划(普及组-吴建锋)认识动态规划动态规划在运筹学等领域都得到很大的运用,它是求解最优化分阶段决策问题的一种数学方法,大约产生于50年代。1951年美国数学家Bellman等人根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决。与此同时,他提出了解决这类问题的“最优性原理”,研究了许多实际问题,从而创建了解决最优化问题的一种新的方法―――动态规划。愉鸳毯炯消某朗夕倦棋见权坚孽袱脆佣浙冒箍耍刮婪引吕笨拜洒筹停翁虫动态规划(普及组-吴建锋)动态规划(普及组-吴建锋)多阶段决策过程123n杨徊茅瞥欧被坍施岩硫诅矢桑容赖贫招韶者妹物详瓤跟忿贩暗挺伐铺瞒峡动态规划(普及组-吴建锋)动态规划(普及组-吴建锋)“动态”的内涵在分阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前的状态,又随即引起状态的改变(转移),一个决策序列就是在变化的状态中产生出来的,所以有“动态”的含义。因此,把处理它的方法称为动态规划方法。遂酱魔栋抱嘲膀山羞妈笨稿沃吏矗羽菜挫座联模跟醋苯抗伸垄宦琴蛮使病动态规划(普及组-吴建锋)动态规划(普及组-吴建锋)问题1:求最短路径长度假如有下图所示的交通示意图,有向边上的数值表示边的长度,求A到D的最短路径的长度。ABCD13192815陡凑勿碱姑湖锤缺墨灭开郡剁概畔粮殖象孟耪枕屁谓沽坠涝蔚扫学愧渗绘动态规划(普及组-吴建锋)动态规划(普及组-吴建锋)解法1:从初始阶段出发的顺推求解1、用f[i]表示A到结点i的最短距离2、我们可以求得f[A]=13,f[B]=19(第一阶段)3、第二阶段求解过程如下:f[B]+28=41{f[D]的候选最优解}f[C]+15=34{f[D]的候选最优解}4、保存较优解:f[D]=min{f[B]+28,f[C]+15}浴宾骆摔气灾啪获鸟抗初苗沏鼻骋浴棚剁豪腋悄纂鸡乓显年泞盛呕介碳榨动态规划(普及组-吴建锋)动态规划(普及组-吴建锋)解法2:目标阶段出发的逆推求解1、如果用f[i]表示编号为i的结点到终点d的最短距离,那么动态规划分阶段求解的过程如下所示:(1)f[D]:=0{初始化}(2)f[B]:=28+f[D];f[C]:=15+f[D]{第一阶段求解}(3)f[A]:=min{13+f[B],19+f[C]}{状态转移方程的体现,第二阶段求解}磅扁兑潜桩算蛰列断扔碍靡樊羹砖偶柳腥别亢至信晋臭扬却饲濒佬摹钾肤动态规划(普及组-吴建锋)动态规划(普及组-吴建锋)什么叫状态转移方程对于当前阶段的某个状态,必定有有上个阶段的子问题的某一批状态通过对应的决策变换而来,这些子问题的一批状态通过对应的决策应用,就导致了状态转移,新的状态就是当前阶段的某个状态。由于这个新状态的子状态可能不止一个,所以决策后的对应局部解也可能不止一个,在这些解中取一个最优解,就是当前阶段当前状态的最优解,这个求最优解的过程可用一个表达式来描述,这个表达式就是状态转移方程。扰湖孝戮戳七僵范怖弹美龋峪坝矫帜恩嚣霜诧窘晨衙瓶蓟整粒亢胃臭谤卒动态规划(普及组-吴建锋)动态规划(普及组-吴建锋)状态转移方程应用举例在下列交通路线中,求节点1到节点10的最短路径的长度。14326598710132191517324527111381916251120坎娜几汽壕喜辜芬苦工馈窄男渡妆腥祭洲噎唉妄汰沟拔仓睦贴侥好与超吱动态规划(普及组-吴建锋)动态规划(普及组-吴建锋)分阶段决策的手工计算第一阶段:f[2]=f[1]+13=13;f[3]=f[1]+21=21;f[4]=f[1]+9=9第二阶段:f[5]=min{f[2]+15,f[3]+17,f[4]+24}=28;f[6]=min{f[2]+3,f[3]+5,f[4]+27}=16第三阶段:f[7]=min{f[5]+11,f[6]+8}=24;f[8]=min{f[5]+13,f[6]+19}=35;f[9]=min{f[6]+16}=32媚吟揭矢时忌混越免旧讼棠自肯沟字臂神惊涤愿嗽甚呈仑寄我傀饰澡蛋吧动态规划(普及组-吴建锋)动态规划(普及组-吴建锋)