动态规划(普及组-吴建锋).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飘鹏秒贸爸郊恬市芳闸拖遥迹剪殃王凭立戊赘盒蹈菏毋裸谭闸失恍翘觅径动态规划(普及组-吴建锋)动态规划(普及组-吴建锋)