第六章动态规划.ppt

第六章动态规划Dynamic programming
五十年代贝尔曼(B. E. Bellman)为代的研究成果
属于现代控制理论的一部分
以长远利益为目标的一系列决策
最优化原理,可归结为一个递推公式
一、多阶段决策过程最优化问题举例

2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
求从A到E的最短路径
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f5(E)=0
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D1)=5
f5(E)=0
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D1)=5
f5(E)=0
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f4(D1)=5
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f3(C1)=8
f4(D1)=5
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f3(C2)=7
f4(D1)=5
f3(C1)=8
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f3(C1)=8
f3(C2)=7
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f2(B1)=20
f3(C2)=7
f3(C1)=8
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f2(B2)=14
f3(C2)=7
f3(C1)=8
f2(B1)=21