| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 7401 人关注过本帖
标题:[求助]如何求出遍历所有城市的最短路径
只看楼主 加入收藏
swbenxi
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2007-6-3
收藏
 问题点数:0 回复次数:10 
[求助]如何求出遍历所有城市的最短路径
各位大大:如果有一幅路线图,上面有N个城市,并且有这N个城市之间的交通路费(一个城市至少有一个连接路线),如果去旅游,要把这所有城市都游玩一遍,问怎样才能用最少的钱把这N个城市走完(一个城市可以走2次或以上,即是个无向图)我想了好久~~拜托各位大大了
搜索更多相关主题的帖子: 遍历 路径 旅游 路线图 
2007-06-03 22:55
viky
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1752
专家分:0
注 册:2007-5-31
收藏
得分:0 
我的最小生成树丫!!!!!!!!!!!!!!!!!!!

中環nite 燈光閃閃...
2007-06-04 00:17
swbenxi
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2007-6-3
收藏
得分:0 
可以详细点吗~我们老师给了个类似拓扑排序的算法~想知道有没类似的算法~谢谢
2007-06-04 14:51
longfeng867
Rank: 1
来 自:重庆
等 级:新手上路
威 望:1
帖 子:182
专家分:0
注 册:2007-5-20
收藏
得分:0 
[QUOTE]

我的最小生成树丫!!!!!!!!!!!!!!!!!!!

[/QUOTE]
你太有才了~~~~

在这个连处女膜都可以伪造的世界里,还有什么值得我相信!
2007-10-04 00:54
cobby
Rank: 1
等 级:新手上路
威 望:1
帖 子:565
专家分:0
注 册:2007-7-11
收藏
得分:0 

楼主的问题看似有点问题。
既然规定好费用要最低,且每个城市至少经过一次,怎么可能会允许城市经过2次或2次以上呢?那1次以上的开销不是白白浪费了嘛。


这个问题叫旅行商问题(Traveling Salesman Problem, TSP),是一个典型的NP难问题,没有一个能给出问题精确解的多项式算法。
你们老师如果说给一个拓扑排序算法,那肯定只能用于几个城市的小规模TSP问题,一般中等规模以上的TSP问题多用智能优化算法(如GA、ACO等)在有限时间内给出近似解。


努力成为菜鸟!
2007-10-08 17:01
cobby
Rank: 1
等 级:新手上路
威 望:1
帖 子:565
专家分:0
注 册:2007-7-11
收藏
得分:0 
PS:一般的对称TSP问题一般默认图形是强连通图

努力成为菜鸟!
2007-10-08 17:02
discus815
Rank: 1
等 级:新手上路
帖 子:43
专家分:0
注 册:2007-10-11
收藏
得分:0 
好深奥

旋转的木马,没有翅膀,但是却可以带着你飞翔.......
2007-10-12 09:05
longerhe
Rank: 1
等 级:新手上路
帖 子:120
专家分:0
注 册:2006-10-10
收藏
得分:0 
支持用最小生成树...
2007-10-12 11:11
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
不用说,先定义一个图,然后画出每几个城市的顶点。加上权值,然后按最小生成树,
2007-10-12 11:11
cobby
Rank: 1
等 级:新手上路
威 望:1
帖 子:565
专家分:0
注 册:2007-7-11
收藏
得分:0 
最小生成树只能应用于小规模问题,且所得不一定是精确解。

努力成为菜鸟!
2007-10-12 11:15
快速回复:[求助]如何求出遍历所有城市的最短路径
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021778 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved