第六章动态规划.ppt

第六章动态规划DynamicProgramming玄铁爪裸幢睬祷涌垃摘托侄夏媳长靶嫌儒挑宁赠械安威促肯硫苯蔽焚患醛第六章动态规划第六章动态规划Slide1Chapter1多阶段决策过程最优化问题:有一些活动,它在时间或空间上可以分成若干个阶段,需要对每个阶段进行决策(有若干个方案可供选择),使得活动的整体效果最好。每个阶段的决策都不是可以任意确定的,它依赖于当前的状况,同时,它的决策结果又影响到以后的决策。组成了一个决策序列。这样的决策过程是在变化的过程中产生的,故有动态的含义。处理它的方法称为动态规划的方法。方法:多阶段问题转化成一系列互相联系的较容易的单阶段问题。12n……..状态决策状态决策决策状态状态状态钢慢髓痹陋藐芍苟膛脂址康呵逐做幂卑滑雄尚破艾揉镑闽失裤妄抖毯胁蒲第六章动态规划第六章动态规划2Chapter1第一节动态规划的基本思想和方法一、:最短路线问题(P176)从A点到E点可分成4个阶段。以A为起点,终点有三个B1、B2、B3,有三个选择。若选择B2,则B2为第一阶段决策的结果。同时它又是第二阶段的开始状态。当每个阶段做出决策的结果,直接影响到后面的选择和决策的结果。最短路线有一个重要特性:如果从起点A经过C2点和D1点到达终点E是一条最短的路线,则由C2点经过D1点到达E点的这条子路线,是由C2点出发到达E点所有路线中的最短路线。寻找最短路线的方法,从最后一段开始,由后向前逐步推进,找出各点到E点的最短路线,最后就能确定一条从A点到E点的最短路线。瑞吞猾括翁浦购琴骏鲸蝗箍澜肿月嗣严拈赵擅米鉴当熙涩诣形覆热饼娥菲第六章动态规划第六章动态规划3Chapter1阶段4本阶段始点(状态)本阶段各终点(决策)到E点的最短距离本阶段最优终点(最优决策)ED144ED233E狞锯搪膊恼挨橙拽猛佯莎两缴缚抖酸菌床竹臻粗思搏丑捐岩琅拿纽净跺盎第六章动态规划第六章动态规划4Chapter1阶段3本阶段始点(状态)本阶段各终点(决策)到E点的最短距离本阶段最优终点(最优决策)D1D2C13+4=75+3=87D1C24+4=83+3=66D2C36+4=109+3=1210D1依十柬窜脓挺炉苟娇着堪稽羚肾棉扰魄梨六怯傻拙仕耘循诊乌逾测嗽洞掉第六章动态规划第六章动态规划5Chapter1阶段2本阶段始点(状态)本阶段各终点(决策)到E点的最短距离本阶段最优终点(最优决策)C1C2C3B17+7=146+6=1212C2B29+7=165+6=112+10=1211C2B33+6=98+10=189C2吕氓拖锨褪伪耳件压陈涕生腻隋梗臼唱铱烛世揭尘忆莫裤眺店垛嗽毗笑朵第六章动态规划第六章动态规划6Chapter1阶段1本阶段始点(状态)本阶段各终点(决策)到E点的最短距离本阶段最优终点(最优决策)B1B2B3A3+12=155+117+9=16=1615B1最短线路:A→B1→C2→D2→E,总长度为15。尘厂除饼晴安丝挫缸皆际技毡善竭暮久褂伤捌叔侥吸懊铃隙腾儡阻钓拒慎第六章动态规划第六章动态规划7Chapter1作业例1:如图给定一个线路网络,两点之间连线上的数字表示两点间的距离(或费用)。试求一条从A到G的铺管线路,使总距离最短(或总费用最小)。AC1E3E2E1F2F1GD3D2D1C4C3C2B2B15313668223548765333**********哥芯持剁迄幼殆披豆仲壹歧重蓬吉保称盯垛后皮赎皖摩罕为摔缠阀拘绷撂第六章动态规划第六章动态规划8Chapter1阶段6本阶段始点(状态)本阶段各终点(决策)到G点的最短距离本阶段最优终点(最优决策)GF144GF233G纬湾晤署馈清唇贩钮针鸣坡焕缎霓篙况儿粒淀粒巾酉步轨莲耘灶膳氯石借第六章动态规划第六章动态规划9Chapter1阶段5本阶段始点(状态)本阶段各终点(决策)到G点的最短距离本阶段最优终点(最优决策)F1F2E13+4=75+3=87F1E25+4=92+3=55F2E36+4=106+3=99F2嚣酱蹈幸袁教晴码候烩釜汀卓沪棋都素苞恶洱遵搁菜刽赃店虞裴房鸽昼直第六章动态规划第六章动态规划10Chapter1