动态规划应用例：飞行计划幻灯片课件.ppt

第五章动态规划及其应用
经典名句：做过了就不要再做
本周POJ上做题：动态规划
1037 A decorative fence、 1050 To the M次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
一、例子（最短路问题）
假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从A地运往E地，中间通过B、C、D三个区域，在区域内有多条路径可走，现求一条由A到E的线路，使总距离最短（或总费用最小）。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
将该问题划分为4个阶段的决策问题
第一阶段为从A到Bj（j=1，2，3），有三种决策方案可供选择；
第二阶段为从Bj到Cj（j=1,2,3），也有三种方案可供选择；
第三阶段为从Cj到Dj(j=1,2)，有两种方案可供选择；第四阶段为从Dj到E，只有一种方案选择。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
如果用完全枚举法，则可供选择的路线有3×3×2×1=18（条），将其一一比较才可找出最短路线：
A→B1→C2→D3→E
其长度为12。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。
由于我们考虑的是从全局上解决求A到E的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至A点：
第四阶段，由D1到E只有一条路线，其长度f4（D1）=3，
同理f4（D2）=4。
第三阶段，由Cj到Di分别均有两种选择，即
，决策点为D1
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
,决策点为D1
，决策点为D2
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
第二阶段，由Bj到Cj分别均有三种选择，即：
决策点为C2
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
决策点为C1或C2
决策点为C2
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
第一阶段，由A到B，有三种选择，即：
决策点为B3
f1（A）=15说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得。即
A→B3→C2→D2→E
上述最短路线问题的计算过程，也可借助于图形直观的表示出来：
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
图中各点上方框的数，表示该点到E的最短距离。图中红箭线表示从A到E的最短路线。
从引例的求解过程可以得到以下启示：
①对一个问题是否用上述方法求解，其关键在于能否将问题转化为相互联系的决策过程相同的多个阶段决策问题。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
3
4
6
7
6
9
9
11
12