魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 111082|回复: 12
打印 上一主题 下一主题

上海轨道交通车站遍历问题 [复制链接]

Rank: 1

积分
56
帖子
40
精华
0
UID
23357
性别
保密
跳转到指定楼层
1#
发表于 2009-4-12 12:59:55 |只看该作者 |倒序浏览
上海轨道交通线路图如附件所示。
求最佳乘车方案,可以在最短的时间内经过所有的车站。
假设条件:
1:站与站之间的平均运营时间为3分钟(包括停车时间)。
2:从一条线路转到另一条线路的平均换乘时间设为8分钟。
3:原则上不鼓励出站换乘,如确有需要,设出站平均换乘时间为20分钟。
不要只是给出方法,最好给出最佳方案,看看谁的方案耗时最短,o(∩_∩)o...

上海轨道交通图.jpg (179.16 KB, 下载次数: 53)

上海轨道交通图

上海轨道交通图

Rank: 3Rank: 3

积分
814
帖子
693
精华
0
UID
82636
性别
2#
发表于 2009-4-12 13:01:48 |只看该作者
沙发了,呵呵。什么时候去七夜店里看看,坐地铁去
一刀流——修罗道

使用道具 举报

Vicki WCA会员  MOD会员 

银魔

域奇

Rank: 7Rank: 7Rank: 7

积分
16832
帖子
12003
精华
8
UID
10183
性别
居住地
江门市

魔方改造大师 爱心大使 八年元老

3#
发表于 2009-4-12 13:03:31 |只看该作者
原来上海已经有那么多线路~

真难的题目呀
广东新会魔友群41696806 限五邑地区魔友加入        新浪微博@vicki又叫域奇

使用道具 举报

Rank: 1

积分
171
帖子
132
精华
0
UID
30495
性别
保密
4#
发表于 2009-4-12 13:18:35 |只看该作者
用手算比较难,用计算机就非常简单了。
首先可以把每条线的起点和终点还有换乘车站看成结点,结点之间的车站都可以压缩成一条边,这样就是枚举出发点,遍历完所有边,选一个最小的即可。用迭代加深限制时间来搜索就行。

使用道具 举报

Rank: 2

积分
499
帖子
431
精华
0
UID
65094
性别
保密
5#
发表于 2009-4-12 13:19:38 |只看该作者
很复杂,估计不会有人想去这样做吧?

使用道具 举报

Rank: 3Rank: 3

积分
603
帖子
462
精华
0
UID
69646
性别
6#
发表于 2009-4-12 13:29:12 |只看该作者
没去过上海``呵呵``蛮想去一次的

使用道具 举报

Rank: 1

积分
169
帖子
144
精华
0
UID
40379
性别
保密
7#
发表于 2009-4-12 17:46:49 |只看该作者
原帖由 gejunji 于 2009-4-12 13:01 发表 沙发了,呵呵。什么时候去七夜店里看看,坐地铁去
4号线上海体育场站下。。。呵呵
北海大厦,去过。。。

使用道具 举报

Rank: 4

积分
1304
帖子
1005
精华
3
UID
27092
性别
8#
发表于 2009-4-12 19:12:23 |只看该作者
前一段破记录的纽约地铁遍历问题就用了计算机

上海还是比纽约地铁少了太多太多了~呵呵

应该不难找到最优解
北京交通大学 魔方群 71663425

使用道具 举报

红魔

All Blue

Rank: 4

积分
1196
帖子
999
精华
2
UID
38845
性别
9#
发表于 2009-4-12 19:28:00 |只看该作者
LULIJIE現身吧!!!
香港的鐵路往橫發展,問題就簡單得多

使用道具 举报

Rank: 4

积分
1304
帖子
1005
精华
3
UID
27092
性别
10#
发表于 2009-4-12 19:52:36 |只看该作者
地铁在交叉出延伸出来的部分必须又去有回,这个用什么方案都一样
这样砍掉他们,问题就简化了呢
最好要求不许出地铁
北京交通大学 魔方群 71663425

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-11-1 07:09

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部