最小生成树及应用
生成树
指没有任何回路的图
图由点、线和长度构成
以前的网络图,求关键路径为求最长路。
煤气管道的铺设
某新建小区着手铺设煤气管道,已知每一幢楼的接入位置和距离,请求出最短的铺设方案。
A
B
C
D
O
13
8
6
5
4
9
9
10
破圈法
A
B
C
D
O
6
5
4
9
最短路:
问题
最短生成树唯一吗?
如果是求最长生成树,如何解决?
1
2
3
练习
求最短生成树
1
2
3
4
5
1
2
5
3
-4
2
3
动态规划
(Dynamic Programming)
动态规划(Dynamic Programming)
1、动态规划解决的问题
可解决运输问题(p165例3)、生产问题(p165例4)、库存问题、定价问题和资金运用等问题。
2、涉及学科
3、Bellman最优化原理-P163
4、图上作业法
5、表上作业法
Bellman最优化原理
Bellman方程(最短路方程、动态规划基本方程)
每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。
最小生成树及其应用 来自淘豆网m.daumloan.com转载请标明出处.
