文档介绍：动态规划
什么是动态规划?
(一)动态规划是解决多阶段决策问题的一种方法。
所谓多阶段决策过程,是将所研究的过程划分为若干个相互联系的阶段,在求解时,对每一个阶段都要做出决策,前一个决策确定以后,常常会影响下一个阶段的决策。
图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)
思路
先看第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};
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
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)。
…
选择数据结构,将每条路经的长度存在数组中。
东西方向上的道路长度存在两维数组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
南北方向上道路长度存至数组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}};
为了计算方便,将图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