魔方吧·中文魔方俱乐部

标题: 上海轨道交通车站遍历问题 [打印本页]

作者: veteranhit 时间: 2009-4-12 12:59:55 标题: 上海轨道交通车站遍历问题

上海轨道交通线路图如附件所示。
求最佳乘车方案，可以在最短的时间内经过所有的车站。
假设条件：
1：站与站之间的平均运营时间为3分钟（包括停车时间）。
2：从一条线路转到另一条线路的平均换乘时间设为8分钟。
3：原则上不鼓励出站换乘，如确有需要，设出站平均换乘时间为20分钟。
不要只是给出方法，最好给出最佳方案，看看谁的方案耗时最短，o(∩_∩)o...

附件: [上海轨道交通图] 上海轨道交通图.jpg (2009-4-12 12:59:55, 179.16 KB) / 下载次数 68
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NDUxMjN8Zjg3OTQ3ODJ8MTc0MDc3Mjg3OHwwfDA%3D

作者: gejunji 时间: 2009-4-12 13:01:48

沙发了，呵呵。什么时候去七夜店里看看，坐地铁去

作者: Vicki 时间: 2009-4-12 13:03:31

原来上海已经有那么多线路~

真难的题目呀

作者: zxl0714 时间: 2009-4-12 13:18:35

用手算比较难，用计算机就非常简单了。
首先可以把每条线的起点和终点还有换乘车站看成结点，结点之间的车站都可以压缩成一条边，这样就是枚举出发点，遍历完所有边，选一个最小的即可。用迭代加深限制时间来搜索就行。

作者: fuwu1927 时间: 2009-4-12 13:19:38

很复杂，估计不会有人想去这样做吧？

作者: ↖____約啶。 时间: 2009-4-12 13:29:12

没去过上海``呵呵``蛮想去一次的

作者: fei61long 时间: 2009-4-12 17:46:49

原帖由 gejunji 于 2009-4-12 13:01 发表沙发了，呵呵。什么时候去七夜店里看看，坐地铁去

4号线上海体育场站下。。。呵呵
北海大厦，去过。。。

作者: beijiaoff 时间: 2009-4-12 19:12:23

前一段破记录的纽约地铁遍历问题就用了计算机

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

应该不难找到最优解

作者: 骰迷 时间: 2009-4-12 19:28:00

LULIJIE現身吧！！！
香港的鐵路往橫發展，問題就簡單得多

作者: beijiaoff 时间: 2009-4-12 19:52:36

地铁在交叉出延伸出来的部分必须又去有回，这个用什么方案都一样
这样砍掉他们，问题就简化了呢
最好要求不许出地铁

作者: 小波 时间: 2009-4-12 19:58:55

绝对用计算机算了，因为本身它这个系统是人为的，没有规律可循，人工算只能枚举。

作者: 剑嵩 时间: 2009-4-12 22:22:58

没去过上海哦，有机会要去看看，哈哈

作者: Bayernea 时间: 2009-4-13 00:24:19

乍一看以为是墨尔本铁路线。。。。。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)