| 查看: 2120 | 回复: 7 | ||
gnss铜虫 (正式写手)
|
[求助]
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人回复
2楼2012-06-12 15:52:33
libralibra
至尊木虫 (著名写手)
骠骑将军
- 程序强帖: 40
- 应助: 817 (博后)
- 金币: 12914.1
- 红花: 64
- 帖子: 2238
- 在线: 287.3小时
- 虫号: 696514
- 注册: 2009-02-05
- 专业: 计算机软件
3楼2012-06-13 02:12:25
dxwbucea
铁虫 (著名写手)
- 应助: 20 (小学生)
- 金币: 17156.4
- 红花: 1
- 帖子: 1722
- 在线: 80.4小时
- 虫号: 1586258
- 注册: 2012-01-24
- 专业: 计算数学与科学工程计算
4楼2012-06-13 07:49:51
5楼2012-06-13 07:54:54
【答案】应助回帖
★ ★ ★ ★ ★
感谢参与，应助指数 +1
gnss: 金币+5, ★★★很有帮助, 您这个算法每个点只能使用一次，我的没有这个限制 2012-06-14 08:37:01
感谢参与，应助指数 +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为空集 这种方法可以保证已经有通路的点不会再连接，同时每次连接都找的是最大距离，应该可以的到你要的结果，就是理论证明起来有点难 |
6楼2012-06-13 15:09:15
7楼2012-06-14 10:41:33
 |
8楼2015-06-11 16:11:31