动态规划.ppt

动态规划
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,求最短路径
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