设为首页收藏本站

切换到窄版

魔方吧·中文魔方俱乐部 › 论坛 › 『其它智力游戏』 › ★ 数学、算术趣题 (Math Puzzles) › 上海轨道交通车站遍历问题

发新帖

查看: 110493|回复: 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, 下载次数: 35)

上海轨道交通图

上海轨道交通图

使用道具举报

Rank: 3 Rank: 3

积分: 814
帖子: 693
精华: 0
UID: 82636
性别: 男

2^#

发表于 2009-4-12 13:01:48 |只看该作者

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

一刀流——修罗道

使用道具举报

WCA会员

MOD会员

域奇

Rank: 7 Rank: 7 Rank: 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: 3 Rank: 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-5-21 06:15

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部