文档介绍：计算机算法设计与分析
North China Electric Power University
Computer Algorithms Design & Analysis
华北电力大学计算机科学与工程系
Dept. puter Science&Engineering of North China Electric Power University
第四章动态规划
★动态规划的原理
★伪币问题
★矩阵连乘问题
North China Electric Power University
★流动推销员问题
★加工顺序问题
★经典动态规划实例
North China Electric Power University
§1 动态规划的原理
最短路径问题:某地区需要由发电厂A至用户端E架设一条高压输电线路,途中经过三个城镇B,C,D,每个城镇各需建设一个降压变电站。城镇B,D各有两个位置可供选择,城镇C由三个位置可供选择,如下图所示。图中各线段旁数据表示该段路径的长度。为如何选址才能使由A到E所用的输电线路最短。
A
B1
B2
C1
C2
C3
D1
D2
E
3
3
1
3
6
4
2
3
6
2
3
2
4
5
4
6
North China Electric Power University
fk: 第k阶段某位置到E的最短距离
dk: 第k阶段某出发位置至第k阶段某终点位置的距离
问题的目标是求f1(A)
所以需先求f2(B1), f2(B2),欲求f2(B1), f2(B2)需先求f3(C1), f3(C2) , f3(C3),同样欲求f3先求f4 ,因此,在求解过程中应按
f4f3 f2 f1顺序计算。这也是一般多阶段决策问题的动态
规划算法的基本思路,即从终点到始点逐步寻优。
f1(A)=min
d1(A, B1)+ f2(B1)
d1(A, B2)+ f2(B2)
North China Electric Power University
下面给出动态规划算法的基本思路:
在第四阶段:k=4 则 f4(D1)=4 f4(D2)=6
在第三阶段:k=3 则
f3(C1)=min
d3(C1, D1)+ f4(D1)
d3(C1, D2)+ f4(D2)
= min
6+4
2+6
=8
相应的最短路径为: C1D2 E
f3(C2)=min
d3(C2, D1)+ f4(D1)
d3(C2, D2)+ f4(D2)
= min
3+4
2+6
=7
相应的最短路径为: C2D1 E
f3(C3)=min
d3(C3, D1)+ f4(D1)
d3(C3, D2)+ f4(D2)
= min
4+4
5+6
=8
相应的最短路径为: C3D1 E
North China Electric Power University
在第二阶段:k=2 则
f2(B1)=min
d2(B1, C1)+ f3(C1)
d2(B1, C2)+ f3(C2)
= min
1+8
3+7
=9
相应的最短路径为: B1C1 D2 E
d2(B1, C3)+ f3(C3)
6+8
f2(B2)=min
d2(B2, C1)+ f3(C1)
d2(B2, C2)+ f3(C2)
= min
4+8
2+7
=9
相应的最短路径为: B2C2 D1 E
d2(B2, C3)+ f3(C3)
3+8
在第一阶段:k=1 则
f1(A)=min
d1(A, B1)+ f2(B1)
d1(A, B2)+ f2(B2)
= min
5+9
3+9
=12
相应的最短路径为: A  B2C2 D1 E
North China Electric Power University
A(12)
B1(9)
B2(9)
C1(8)
C2(7)
C3(8)
D1(4)
D2(6)
E
3
1
2
3
4
4
6
上面的计算结果可以表示成下面的形式:
2
分析与总结:
1) 与穷举法相比,动态规划算法大大减少了计算的工作量。问
题的规模越大,动态规划算法比穷举法节省的计算工作量越
多。
North China Electric Power University
2) 用动态规划算法不仅求出了全过程的最优方案,而且得到了
任意一子过程的最优方案,这一特点对许多实际问题非常有
用。
3) 动态规划算法虽然把整个过程划分为若干个阶段,但每个阶
段的计算总是把当前效益与整