5 7
4
6
伊犁
H
求费用最小的方案
Dijkstra算法
图上作业法
计算过程
R
正向
4 2
RAm RAm=4, RBm=5, RCm=min{RAm-C8,RBm-C12}=8 RAm-C8 RAm-D RDm=min{RAm-D,RBm-D}=6 RDm REm=min{RAm-E9,RBm-E8}=8 RBm-E8 RFm=min{RCm-F13, RDm-F10 RDm-F10,REm-F14}=10 RDm-G9 RGm=min{RDm-G9,REm-G13}=9 RGm RHm=min{RCm-H14,REm-H12}=12 REm-H12 RSm=min{RFm-S15,RGm-S13,RHm18-S}=13 RGm-S13 RSm
A 4 4 5 7 5 5 B 5 3
C 5 8 6 D4 63 6 E 5 8 4
F 1 0 G 9
5 4 6
S 13
H
1 2
图上作业法
A 4 9 5 7 5 5 B 1 3 2 4 2
计算过程
FSm=5, 6 H GSm=4, 6 HSm=6 CSm=min{C-FSm,C-HSm}=10 DSm=min{D-FSm,D-GSm}=7 ESm=min{E-FSm,E-GSm,E-HSm}=9 ASm=min{A-CSm,A-DSm,A-ESm}=9 BSm=min{B-CSm,B-DSm,B-ESm}=12 RSm=min{R-ASm,R-BSm}=13
/issue3/dynamic/ /kjdt/kjdt3x_1.html /english/Links/fsf-china/english/pansystems
结点 B C D E F G H I J K A 5 4 7 B 10 9 C 7 6 4 D 5 5 E 7 6 F 7 3 3 G 2 4 H 7 I 5 J 6
一些参考资料
Ross S. Introduction to Stochastic Dynamic Programming Bertsekas Dynamic Programming Harris M. Dynamic Economic Analysis 李人厚，韩崇昭（译），《动态规划－－确定性和随机模型》，西安交通大学 出版社，1990
Q：如何求效益最大问题？
在计算中采用MAX函数
课后练习

再网上搜索Dijkstra的信息，为他作一份网
页，你怎样和他取得联系？

动态规划除了Dijkstra算法之外还有其他方法 吗？
作业：下表表示一个A－K城的运输任务，数字表 示10公里数，请为司机选择最短的路线（分别用 图上和表上作业法）。
/bookhtm/28/1000aa2a.htm
(5.7) (5.8)
例1
从上海到伊犁间有一个铁路网，某学生 暑假打算到伊犁旅游，出于经济关系只能坐火 车，而且要求费用最少。下图标出了各种可能 的行车路线，请为这位同学的决策做出指导。
图上作业法
C A 上海 4 5 B 4 2 6 D4 3 5 3 E 6 5 4
5
如果用穷举法，先要 计算从上海到伊犁的 所有路径的费用，再 取最小的路径。 F 5 G
生成树

指没有任何回路的图
图由点、线和长度构成 以前的网络图，求关键路径为求最长路。


煤气管道的铺设

某新建小区着手铺设煤气管道，已知每 一幢楼的接入位置和距离，请求出最短 的铺设方案。
破圈法
4 C 5 8 B
9
O 13
6
D
10
A
9
最短路：
4 C 5 B
6
D
O A
9
问题

最短生成树唯一吗？

如果是求最长生成树，如何解决？源自1 2 3练习
求最短生成树
2
5 2
3 -4 3 5
2
1
4
3
1
动态规划
(Dynamic Programming)
动态规划(Dynamic Programming)
1、动态规划解决的问题
可解决运输问题（p165例3）、生产问题（p165例4）、库存 问题、定价问题和资金运用等问题。
对于状态很多的问题，图上表示不易， 适宜采用表上作业法。见P164-165
表上作业法
á ã ½ µ R A B C D E F G H ·¾ Â ¶ Ñ Ó · Ã
A B C 4 5 4 7
D 2 5
E 5 3
F
G
H
S
5 4 6
6 3 5 4
5 4 6 A B AC AD BE ADF ADG BEH ADGS 4 5 8 6 8 10 9 12 13
R 逆向 13
C 5 1 6 0 D4 73 6 E 5 9 4
F 5
G 4 4
5 S
图上作业法 C A R上海 4 5 B 4 2 6 D4 3 5 3 E 6 5 4 费用最小的方案为RADGS＝13 有时可能有几条费用最小方案，也可一同求出。 H 6 G 5 F 5
5 7
4
S伊犁
表上作业法
2、涉及学科 3、Bellman最优化原理－P163 4、图上作业法
5、表上作业法
Bellman最优化原理
Bellman方程(最短路方程、动态规划基本方程 ) 每一点最优都是上一点最优加上这段长度。即当前最优 只与上一步有关。
u s 0, u min{u w }. i ij i j j
/02/0212/a/0212a17_2.asp
.tw/water-resource/water/CH08.html
/gb/technology/cybernetics/abc/abc202.html