24小时热门版块排行榜

返回列表

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

gnss

铜虫 (正式写手)

应助: 2 (幼儿园)
金币: 275.9
散金: 65
帖子: 490
在线: 91.3小时
虫号: 826995
注册: 2009-08-13
性别: GG
专业: 大气遥感和大气探测

[求助] 30金币求助：最长路径问题，要求遍历每个节点，总路径最长

某地区150个地面点，每个点坐标(x,y,z)，任意两点i,j间组成基线，基线的长度为L(i,j)。
问题：找出一条路径，要求：
1, 经过每一个站点；
2, 每个站点可能不止使用一次；
3, 任何两条基线不相关，即如果路径含有i->j->k,则不允许存在i->k;
4 即该路径含150个节点，149条互不相关的基线;
5, 对L(i,j)求和，要求总路径最长。

这是一个什么问题呢？暴力枚举搞不定，计算量太大了。
30金币求助一下。我同时也在学习中。

[ Last edited by gnss on 2012-6-12 at 15:07 ]

回复此楼

» 猜你喜欢

职称评审没过，求安慰已经有56人回复
最近几年招的学生写论文不引自己组发的文章已经有5人回复
26申博自荐已经有3人回复
A期刊撤稿已经有4人回复

» 本主题相关价值贴推荐，对您同样有帮助:

考博成功散点金币已经有187人回复
SCI再次投稿，先散6个金币，攒人品，如果送审散66个金币，如果接收散金IF*100 已经有15人回复
求帮忙分析一下这三个红外图谱，谢谢。有【金币】赠送。。。。。已经有14人回复
尘埃落定，特散金币100 已经有208人回复
渤海钻探创国内水平段最长纪录已经有4人回复
Euler 工程第廿六题：最长的循环节已经有9人回复
Euler 工程第14题：找最长的数列已经有9人回复
100金币求助CeF3：要求为国药批号为F20060915的CeF3！已经有3人回复
20金币求助两句话汉译英，急求，谢谢,谢绝软件翻译已经有3人回复
有比我更悲剧的吗？说说你最长审稿时间的一篇文章已经有40人回复
【交流】急，60金币交流-考博,大家还在做实验吗？复习到哪个阶段了？已经有13人回复
【求助】25金币求助：氧化铝作为吸附剂的柱层析问题已经有19人回复
【求助】用DS2.5对接错误(已经自己解决，请退换金币) 已经有4人回复
【分享】保诺给解决户口了，撒15个金币已经有107人回复

1楼 2012-06-12 15:06:19

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

smswt

铁杆木虫 (小有名气)

应助: 4 (幼儿园)
金币: 6049.6
帖子: 112
在线: 362.5小时
虫号: 905964
注册: 2009-11-18
专业: 光学

【答案】应助回帖

★ ★ ★ ★ ★
感谢参与，应助指数 +1
gnss: 金币+5, ★★★很有帮助, 您这个算法每个点只能使用一次，我的没有这个限制 2012-06-14 08:37:01

没学过图论，看下这个方法可以不
1.把给的N个点分成两个集合A，B
2.对有限集合，A，B之间点的距离肯定有一个最大值，把这个距离设成L(A,B)
现在实行算法如下：
1,让A为空集，B为N所有点的集合，从B中任意选一个点放到A（不知道任意选对不对）
2，计算L(A,B)，找到A，B中对应该距离的点（假设分别为i，j）
3.连接i->j，同时把j点从B中去掉，放入A中
4.重复2,3，直到B为空集

这种方法可以保证已经有通路的点不会再连接，同时每次连接都找的是最大距离，应该可以的到你要的结果，就是理论证明起来有点难