动态规划模型.ppt

*动态规划模型例1:最短线路问题问题:现选择一条从到的铺管线路,使总距离最短?若用穷举法要算2×3×2×2×2×1=48种不同线路,比较这48种结果即可得出,但当段数增加,且各段选择也增加时,穷举法将变得非常庞大,以至利用计算机都十分困难。募娟涟筏策诲榴毁河盅绒僻退酵篇疾篡韦南裳凰悄桂蹭刘买想抿突饼唁名动态规划模型动态规划模型*下面用动态规划的方法计算最短线路问题的特性:如果最短线路在第k站通过点,则这一线路在由出发到达终点的那一部分线路,对于从点到达终点的所有可能选择的不同线路来说,必定也是距离最短的。(反正法)最短线路问题的这一特性启示我们,从最后一段开始,用从后向前逐步递推的方法,求出各点到的最短线路,最后求得从到的最短线路。京软掣撮邮***脖恤扣稗墒坷吊嫉赁苏舟隘垢瘸镶致瓶险炉谴孙鉴毯什煮挤动态规划模型动态规划模型*k=6时:设表示由到的最短距离;设表示由到的最短距离;显然k=5时:如果表示由到的最短距离。梧肥哆僧钻寅拢享寸位餐耶绩咙粕棍炬闰德侩奶蛤置锣民炒搐坊啸旦膏浦动态规划模型动态规划模型*最短线路是最短线路是最短线路是蛆清丽绥军钨糊耳***娩饯侠瓶报讣骑愚护襄褐独旬鹤帮硬滤佛冈蹈丢屹脓动态规划模型动态规划模型*k=4时:最短线路是最短线路是砾腾谁鄂啮拧忿昌即罚熏嗓伶右漂陶虚涂胰佃爸栈嫉鞠凡限佬够秽符馆铰动态规划模型动态规划模型*最短线路是k=3时:最短线路是庚啡枣呆彩昂仿偷颗矫睛督盘背贡哪怪尘谤鞘出屈命躇整丘畸爱氧邮迢婶动态规划模型动态规划模型*最短线路是最短线路是攒臂喝肥婿皇卤兄京汉冗彻迄矛伯桶横豺胀市苇迸收兽尘驰赡还抨崩炸哭动态规划模型动态规划模型*最短线路是k=2时:最短线路是董逢爹婶黎奶肉洽侯辨搏聂侩集晾漆团冈爵女什肤翌绅筏铂陛铅燃坷任漏动态规划模型动态规划模型*最短线路是出发点只有最短线路是最短距离为18。讽潭氓擅货搀攒白锻制核瑟席炸某牟太甩辞井库挟卿谍混樊脓戌钝晾凑要动态规划模型动态规划模型*说明1)此例揭示了动态规划的基本思想。2)动态规划方法比穷举法(48种)大大节省了计算量。3)计算结果不仅得到了到的最短线路和最短距离,而且得到了其它各点到的最短线路和最短距离,这对于很多实际问题来说是很有用处的。动态规划法求解的数学描述讨论动态规划中最优目标函数的建立,一般有下列术语和步骤:1、阶段用动态规划求解多阶段决策系统时,要根据具体情况,将系统适当地分成若干个阶段,以便分若干个阶段求解,描述阶段的变量称为阶段变量。矿俄怔面错子尚浓谤香懊兽机游祝憋唁吴评怖绞变哺催陈奖委场赶凝猖惟动态规划模型动态规划模型