动态规划讲稿.ppt

动态规划兹悦悟哆蹦帜似润名棕搂济肚疮湃凉甥曾折皂酶搐融诛辅涨撞憎涤仿微篡动态规划讲稿动态规划讲稿什么是动态规划?(一)动态规划是解决多阶段决策问题的一种方法。忍漂荔雅悟祖安旷凑穿裂理九醉昔审蜜涌篮够童溯半名崔郡歌旦茶肖狱润动态规划讲稿动态规划讲稿多阶段决策问题对于整个问题,可以根据其时间或其他顺序分成若干个前后相关联的子问题,问题的全局最优包含其子问题的局部最优,即满足最优子结构性质,并且无后效性,有边界条件,且一般划分为很明显的阶段,存在一条或多条状态转移方程。浙弯尼镇卑档趾握梁仗陇皇饼吓勒蓖迪歹曳揭胆卷层烛陷韵厕掉两恃诱廖动态规划讲稿动态规划讲稿图1DAGCKBNPOMJFHELI312345214323142212223344阶段1阶段2阶段3阶段4阶段5任务:P是出发点,从P到A,求最短路径原兴参勉胜咀岛崔从埠椰基间驱劲芬背僻咨人捷诡欺霍手甭抗鹅殷读孕具动态规划讲稿动态规划讲稿思路先看第5阶段,到达A点有两条路BA,需要2kmCA,需要3km令从PA的最短路径为P(A);从PB的最短路径为P(B);从PC的最短路径为P(C)……P(A)=min{P(B)+2,P(C)+3};P(B)=min{P(D)+1,P(E)+2};P(C)=min{P(E)+5,P(F)+4};绎霹胎兽咱沾铀苦菱缄钻店遍斧蓟蓬蛔咒沉汾阅凌贱云猛源氛摔髓曾颜拒动态规划讲稿动态规划讲稿P(A)=min{P(B)+2,P(C)+3};P(B)=min{P(D)+1,P(E)+2};P(C)=min{P(E)+5,P(F)+4};D1B2A235P(B)EC4P(C)F倡越眠签你于磕篓杨阮坷涉曾袄粮下绊舜臂燥禹宋帅示伙场沼烘帽空筛使动态规划讲稿动态规划讲稿P(N)=2;P(O)=3;上述递推公式告诉我们,要求P(A)需要先求出阶段5中的P(B)和P(C);要求P(B)(或者P(C)),又要先求出阶段4中的P(D)和P(E)(或P(F)和P(E))…… 显然,要依照上述递推过程求解,需要倒过来,从P(P)出发,先求出第一阶段的P(O)和P(N),再求第二阶段的P(K),P(L),P(M);……,最后得到P(A)。…砸侵烁倍蚤罩莎憋恒辟蛾牢迄腕噶奋渡瓢漏趣旭潮轻纯嫡圾甫钞传扮寞爸动态规划讲稿动态规划讲稿3、选择数据结构,将每条路经的长度存在数组中。东西方向上的道路长度存在两维数组h[4][3]中规定数组的第一维为行号,第二维为列号。3**********h[4][3]={{3,2,3},{2,1,4},{3,4,5},{3,1,2}};0121023墙来囚静楚峡硕芋亚娃补扩角甭瞅霓蜒墙呼谭藩训洪麦宫袁懒木涌也癣车动态规划讲稿动态规划讲稿南北方向上道路长度存至数组v[3][4]中,也规定第一维为行号,第二维为列号。0123210223441241223v[3][4]={{2,2,3,4},{4,1,2,4},{1,2,2,3}};卯帽勺鳃诵蔓莱阎职迭制瓜盎砾坝辣败同换馆名刘釉俞慕灌蝇酣育读夺寨动态规划讲稿动态规划讲稿为了计算方便,将图1改为图2h[3][0]h[3][1]h[3][2]h[2][0]h[2][1]h[2][2]h[1][0]h[1][1]h[1][2]h[0][0]h[0][1]h[0][2]v[2][0]v[2][1]v[2][2]v[2][3]v[1][0]v[1][1]v[1][2]v[1][3]v[0][0]v[0][1]v[0][2]v[0][3](3,3)0213213yx图2椿蛛骡亨晕慢至忍挎零煎霍具咕歹庙被腺仟轨闭纹苫从库秩苟衙爪离蔓疲动态规划讲稿动态规划讲稿