文档介绍：第7章
动态规划
(Chapter7 Dynamic Programming)
1
动态规划的基本概念
动态规划的应用举例
动态规划的最优性原理与数学模型
2
1951年美国数学家R. Bellman等人创建了动态规划。
基本思想:将一个复杂问题分解成若干个阶段, 每一个阶段作为一个小问题进行处理, 从而决定整个过程的决策。
求解过程分两步: 先按整体最优化递序地求出各个可能状态的最优化决策, 再顺序地求出整个问题的最优策略和最优路线。
3
动态规划的基本概念
最短路径问题
。求A到E的最短路径。
引例
4
如果用穷举法, A到E: 3×3×2=18条路径
求从A到E的最短路径问题, 可以转化为三个性质完全相同, 但规模较小的子问题, 即分别从B1、B2、B3到E的最短路径问题。
计算每条路径的长度, 总共 4×18=72次加法计算;
对18条路径的长度比较, 总共 18-1=17次比较。
如果从A到C的站点有k个, 总共3k-1×2条路径, 求最短路总共(k+1)3k-1×2次加法, 3k-1×2-1次比较。
当k值增加, 需要进行的加法和比较次数将迅速增加。
例如当k=10时, 加法次数为433026次, 比较39365次。
5
记从Bi (i=1, 2, 3) 到E的最短路径为S(Bi),则从A到E的最短距离S(A)可表示:
6
计算S(B1)又可归结为性质完全相同, 但规模更小的问题, 即分别求C1, C2, C3到E的最短路径问题S(Ci) (i=1, 2, 3), 而求S(Ci)又可以归结为求S(D1)和S(D2)这两个子问题。
, 在这个问题中, S(D1)和S(D2)是已知的, 它们分别是:
7
S(D1)=5, S(D2)=2
从这两个值开始, 逆向递归计算S(A)的值。
计算过程如下:
8
S(C1)=8, 且如果到达C1, 则下一站应到达D1
S(C2)=7, 且如果到达C2, 则下一站应到达D2
S(C3)=12, 且如果到达C3, 则下一站应到达D2
计算S(Bi):
9
S(B1)=20, 且如果到达B1, 则下一站应到达C1
S(B2)=14, 且如果到达B2, 则下一站应到达C1
S(B3)=19, 且如果到达B3, 则下一站应到达C2
计算S(A)
从A到E的最短路径为:
10
A B2 C1 D1 E
计算过程及结果用下图表示。从图中任一点到E的最短路径。仅用了18次加法, 11次比较。