文档介绍：动态规划
1
什么是动态规划？
（一）动态规划是解决多阶段决策问题的一种方法。
2
所谓多阶段决策过程，是将所研究的过程划分为若干个相互联系的阶段，在求解时，对每一个阶段都要做出决策，前一个决策确定以后，常常会影响下一个阶段的决策。
3
图1
D
A
G
C
K
B
N
P
O
M
J
F
H
E
L
I
3
1
2
3
4
5
2
1
4
3
2
3
1
4
2
2
1
2
2
2
3
3
4
4
阶段1
阶段2
阶段3
阶段4
阶段5
任务：
P是出发点，从P到A，求最短路径（图1）
4
思路
先看第5阶段，到达A点有两条路
B A，需要2km
C 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}；
5
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}；
D 1 B 2 A
2 3
5
P(B) E C
4 P(C)
F
6
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)。
…
7
选择数据结构，将每条路经的长度存在数组中。
东西方向上的道路长度存在两维数组h[4][3]中规定数组的第一维为行号，第二维为列号。
3
1
2
3
4
5
2
1
4
3
2
3
h[4][3] = { {3,2,3}, {2,1,4}, {3,4,5}, {3,1,2} };
0
1
2
1
0
2
3
8
南北方向上道路长度存至数组v[3][4]中，也规定第一维为行号，第二维为列号。
0
1
2
3
2
1
0
2
2
3
4
4
1
2
4
1
2
2
3
v[3][4] = {{2, 2, 3, 4},{4, 1, 2, 4},{1, 2, 2, 3}};
9
为了计算方便，将图1改为图2
h[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)
0
2
1
3
2
1
3
y
x
图2
10