动态规划模型
例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、阶段
用动态规划求解多阶段决策系统时,要根据具体情况,将系统适当地分成若干个阶段,以便分若干个阶段求解,描述阶段的变量称为阶段变量。
动态规划模型 来自淘豆网m.daumloan.com转载请标明出处.
