数学建模社区-数学中国

标题: 200908网友练习《最短路径模型》 [打印本页]

作者: yejusting 时间: 2009-8-17 19:23
标题: 200908网友练习《最短路径模型》
本帖最后由为你奋斗于 2009-12-3 15:10 编辑 盖一个房子，已知需要A，B，C三个人完成。
然后，又已知，A的工作可以由D和E共同完成。（A=D; A=E）
而C的工作必须由F和G同时完成。（C=F+G）
另外，H可以完成E和F的工作。（E+F=H）
求：选择最少的人完成这个房子

当然实际问题肯定没有这么少的人，但是这个怎么建立图，又怎么转化为最短路径问题呢？？？就这个最简单的ABCDEFGH而言如何建图？

谢谢谢谢~~~

作者: mikewang719 时间: 2009-8-17 19:34
不小心路过........

作者: firstboy0513 时间: 2009-8-18 16:57
我把图片上传了，你看看，就是这样转化为最短路径的，而最短路径算法上网比较多，你可以下到的。

a.JPG (14.44 KB, 下载次数: 314)

作者: firstboy0513 时间: 2009-8-18 17:02
随便也把参考程序也给你好了，不过这个也是上网下的，不是我写的，在此声明。
你最好自己编写一个，用C或Matlab都好编dijkstra算法的，比较容易。

dijkstra最短路算法.rar

494 Bytes, 下载次数: 20, 下载积分: 体力 -2 点

作者: abc007 时间: 2009-8-18 19:56
好！！！！！

作者: abc007 时间: 2009-8-18 19:57
顶！！！！！！

作者: abc007 时间: 2009-8-18 19:59
支持！！！！！

作者: abc007 时间: 2009-8-18 20:00
很不错！！！！！

作者: minedoc 时间: 2009-8-18 20:02
学习...很好的资料......

作者: wuliling 时间: 2009-8-18 20:43
好多最优解的题目

作者: wxj880516 时间: 2009-8-18 20:55
图好像不太对。。。
A被替换：
A-B-C-房子
C-B--c-
D-B-C
C被替换：
A-B-f+g
A和C都被替换再做一条路
再做出一张图就行了，我是这么理解的。。。

作者: 兄弟 时间: 2009-8-18 23:33
好啊！谢谢了！有点不好意思！

作者: clanswer 时间: 2009-8-19 10:08
求最短路问题Dijkstra算法还是很不错的

作者: kongfanqing 时间: 2009-8-19 16:58
谢谢您，太好了

作者: yejusting 时间: 2009-8-19 18:25
3# firstboy0513
谢谢谢谢
但是注意到ABC这三个点的位置，在图中是先A再C然后B，原因应该是E+F=H，造成B和C的位置要调换，才好把H建进去，但是如果这个网络很大的话，就没有办法这样调换了，例如在已有的基础上加了一个I能够完成D和G的工作，I=D+G,因为D和G不是连在一起的，所以I就不好放上去了。B和C的位置调整也是为了，让E和F能够连在一起。
因为这个网络很大，这样的调整恐怕不太现实，不知道有什么办法能够解决这个问题吗？
再次感谢！！

作者: zhxc21 时间: 2009-8-20 14:22
同意！
顶下！

作者: 凹工口 时间: 2009-8-20 20:58
看不太懂哦。。。

作者: yejusting 时间: 2009-8-21 12:32
17# 凹工口

就是说如果这样画，就无法把H连上去了，所以B和C要做一下调换，但是因为网络不是这么简单，如果这个时候调换了B和C，出现了一个新的点I=D+G,那么I又连不进去了。

作者: firstboy0513 时间: 2009-8-25 15:12
不好意思,这几天不在学校.以下是几个图供参考,不知道对不对.

1.JPG (18.16 KB, 下载次数: 176)

2.JPG (20.58 KB, 下载次数: 170)

3.JPG (20.13 KB, 下载次数: 208)

作者: 小旋风假 时间: 2010-1-17 20:39
我感觉你这个问题问得不对，应该是求最短时间吧…………………………

作者: zgh058 时间: 2010-1-19 12:23
不理解。。。。。。。。。。。。。。。

作者: 小旋风假 时间: 2010-1-23 09:09
这题有意思呀………………………………………………

作者: wwwhuangqian 时间: 2010-4-24 20:21
软件很神奇！

作者: gao1221 时间: 2010-4-30 20:58
有道有道 …………………………………………………………………………………………………………

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)