图论的实际应用之二 最小树型图 (300分)

  • 主题发起人 主题发起人 LeeChange
  • 开始时间 开始时间
L

LeeChange

Unregistered / Unconfirmed
GUEST, unregistred user!
半山腰修了个水库,山脚下有一些村庄.现在要给这些村庄修供水管道.修水管不象架电线,连起来就行,还得考虑水是往低处流的.已知一矩阵a[0..n, 0..n],若a[0, i]>0表示从水源到村庄i修水管的费用为a[0, i],若a[0, i]=0表示从水源无法直接修水管到村庄i.同样a[i, j](i<>0, j<>0)表示村庄i到j修水管的费用,若为0,则表示无法修从村庄i到村庄j的水管.显然a[i, j]不一定等于a[j, i].编程求一修水管的方案,使得村村有水用,且总造价最小.
提示:千万别以为跟最小生成树一样,那个是针对无向图的,这题可是有向图.
上一题:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1947897
下一题:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1953299
 
我想想，好像还是用贪心法
 
我不太好说贪心法不对，但绝对敢说贪心法不好。
 
呵呵，这个问题我还没遇到过，今天下午来好好考虑考虑
我对图论倒是挺感兴趣的
 
算法我不大行，看看
 
对啊，怎么做呢？
 
是用深度优先搜索吧，比较适合有向图，
为了生成这个最小树有个叫什么“普里姆”算法的（数据结构书上这么说的，以前上课没有好好学，现在都忘了）
 
用关键路径算法可以解决这个问题
 
原来LeeChange当上斑竹了，恭喜~~~~
这道题用遍沥树可以吗？(就是上次和你学的那个好象叫分支限界法)
 
用拓扑排序。删除入度为零的结点及边。
 
to 来如风 and yanyandt2:
深度优先从理论上讲是能解任何题的。但解此题有更高效的方法。
to laoli:
拓扑排序求一个可行解是非常高效的，但如果要求最优解，则需要在每个存在两个以上的无前驱结点的时候做分支。
 
我放弃思考了，看是看书，看懂要花点时间
 
当出现两个结点时，可以根据权值大小来选择的，可以由小到大或由大到小。这样得到的路径就是唯一的了。
 
to AI:
如果你是在看吴的那本书上用顶点收缩的算法，可要好好下一番工夫,那个程序写的晦涩难懂.虽然技巧性很强,但我不喜欢.
to laoli:
这样做有点贪心的意思,但不能保证全局的解最优.
 
那还有那本书上有讲啊？
 
这些不都是数据结构的东西么？
书上都有的啊？
 
严蔚敏的《数据结构》里面图的部分有这个算法吧？
 
to anbncnfn:
可以推荐一下您看的那本数据结构吗?
在现在使用的给大学生用的数据结构的教材中好象没有提最小树型图的,离散数学的教材里到是有提过的,但纯理论,晦涩的很.
在给中学生用的算法的书里到是有实践,估计AI这两天正看的冒火呢.
 
呵呵，原来anbncnfn说的是清华的绿皮书呀.
那本书在下还是比较有发言权的,如果没记错,只说了最小生成树,没有树型图.
 
您必须登录或注册才可回复。

Similar threads

S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
I
图形显示技巧
回复
0
查看
612
import
I
I
Delphi中的基本图象处理代码～～～
回复
0
查看
783
import
I
I
常用算法（3）动态规划
回复
0
查看
1K
import
I
后退
顶部