动态规划模型.ppt

1 动态规划模型例1:最短线路问题 0A 6A 问题:现选择一条从到的铺管线路, 使总距离最短? 若用穷举法要算 2×3×2×2×2×1=48种不同线路,比较这 48种结果即可得出,但当段数增加, 且各段选择也增加时,穷举法将变得非常庞大,以至利用计算机都十分困难。 2 下面用动态规划的方法计算最短线路问题的特性: 如果最短线路在第 k站通过点,则这一线路在由出发到达终点的那一部分线路,对于从点到达终点的所有可能选择的不同线路来说,必定也是距离最短的。(反正法) kP kP kP 最短线路问题的这一特性启示我们,从最后一段开始,用从后向前逐步递推的方法,求出各点到的最短线路,最后求得从到的最短线路。 6A 0A 6A3 k=6时: 设表示由到的最短距离; )( 56Af 5A 6A设表示由到的最短距离; )( 56Bf 5B 6A显然 4)( 56?Af 3)( 56?Bfk=5时: 如果表示由到的最短距离。)( 45Af 4A 6A min )(? 45Af????????)(),( )(),( 5654 5654BfBAd AfAAd735 43 min ??????????(以下类似定义) 4 最短线路是 654AAA???)( 45Bf 532 45 min )(),( )(),( min 56545 56545??????????????????BfBBd AfABd最短线路是 654ABB??936 46 min )(),( )(),( min )( 56545 56545 45 ???????????????????BfBCd AfACdCf最短线路是 654ABC?? 5 k=4时: 752 72 min )(),( )(),( min )( 45434 45434 34 ???????????????????BfBAd AfAAdAf最短线路是 6543ABBA???692 51 min )(),( )(),( min )( 45434 45434 34 ???????????????????CfCBd BfBBdBf最短线路是 6543ABBB??? 6 893 53 min )(),( )(),( min )( 45434 45434 34 ???????????????????d BfBCdCf最短线路是 6543ABBC???k=3时: 13 68 76 min )(),( )(),( min )( 34323 34323 23 ???????????????????BfBAd AfAAdAf最短线路是 65432ABBAA???? 7 10 65 73 min )(),( )(),( min )( 34323 34323 23 ???????????????????BfBBd AfABdBf最短线路是 65432ABBAB????983 63 min )(),( )(),( min )( 34323 34323 23 ???????????????????d BfBCdCf最短线路是 65432ABBBC???? 8 12 84 68 min )(),( )(),( min )( 34323 34323 23 ???????????????????CfCDd BfBDdDf最短线路是 65432ABBCD????k=2时: 13 96 10 3 13 1 min )(),( )(),( )(),( min )( 23212 23212 23212 12 ?????????????????????????????CfCAd BfBAd AfAAdAf最短线路是 654321ABBABA????? 9 16 12 6 97 10 8 min )(),( )(),( )(),( min )( 23212 23212 23212 12 ?????????????????????????????DfDBd CfCBd BfBBdBf最短线路是出发点只有 0A18 16 3 13 5 min )(),( )(),( min )( 12101 12101 01 ???????????????????BfBAd AfAAdAf最短线路是 6543210ABBABAA??????最短距离为 18。 654321ABBBCB?????10 说明 1)此例揭示了动态规划的基本思想。 2)动态规划方法比穷举法( 48种)大大节省了计算量。 3) 计算结果不仅得到了到的最短线路和最短距离,而且得到了其它各点到的最短线路和最短距离, 这对于很多实际问题来说是很有用处的。 0A 6A 6A动态规划法求解的数学描述讨论动态规划中最优目标函数的建立,一般有下列术语和步骤: 1、阶段用动态规划求解多阶段决策系统时,要根据具