文档介绍：第二章 动态规划及其应用
精选ppt
本周POJ上做题：动态规划
1037 A decorative fence、 1050 To the Max、 1088导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
精选ppt
动态规划算法的基本要素
二、重叠子问题
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
精选ppt
一、例子（最短路问题）
假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从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
精选ppt
将该问题划分为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
精选ppt
如果用完全枚举法，则可供选择的路线有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
精选ppt
显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。
由于我们考虑的是从全局上解决求A到E的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至A点：
精选ppt
第四阶段，由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
精选ppt
,决策点为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
精选ppt
第二阶段，由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
精选ppt
决策点为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
精选ppt
第一阶段，由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
精选ppt
图中各点上方框的数，表示该点到E的最短距离。图中红箭线表示从A到E的