文档介绍：第六章动态规划
*
第1页，共112页，编辑于2022年，星期三
动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问问题的基本思想是， 如果A= S1 →S2 →… → Sk →… → Sn →E是A到E的最短路，则Sk到E的最短路一定是Sk →… → Sn →E。
首先将问题划分为4个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。
为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。
第10页，共112页，编辑于2022年，星期三
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
第11页，共112页，编辑于2022年，星期三
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
第12页，共112页，编辑于2022年，星期三
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
第13页，共112页，编辑于2022年，星期三
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
第14页，共112页，编辑于2022年，星期三
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
第15页，共112页，编辑于2022年，星期三
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
第16页，共112页，编辑于2022年，星期三
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
第17页，共112页，编辑于2022年，星期三
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
第18页，共112页，编辑于2022年，星期三
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(B3)=19
f3(C2)=7
f3(C1)=8
f2(B1)=21
f2(B2)=14