遍历深圳地铁的所有站

2013-02-01 00:52:02 +08:00
 flowercold
深圳地铁一共有几个站？
把所有站点都至少经过一次，要求重复经过的站点最少，最佳路线经过的站点数是多少？
一妹子说是小学生题目，可是这很明显是图论中的NSP问题啊，求指点。

http://map.baidu.com/subways/index.html?c=shenzhen
3802 次点击
所在节点    程序员
7 条回复
swulling
2013-02-01 01:31:04 +08:00
这个肯定不是小学生题目，，，
zhangxiao
2013-02-01 01:35:49 +08:00
如果是个小学生题目，可能是个考研思维发散的... 比如设计的路线可以上地面打车...
notonlysuccess
2013-02-01 10:31:09 +08:00
http://www.bnuoj.com/hackathon/contest_show.php?cid=2#problem/0

NPC问题，前阵子时间正好搞过一下，可以去这个网站看看
forest520
2013-02-01 13:15:57 +08:00
没有多少个站，先穷举所有可能性，把结果保存，直接查结果
chunshuai
2013-02-01 13:24:05 +08:00
楼主头像是本人么？
iEverX
2013-02-02 02:37:37 +08:00
把所有的端点和交叉点抽象成点，地铁线抽象成线，线的权重就是线上地铁站的个数。。然后，就是一个最小生成树问题
iEverX
2013-02-02 02:38:06 +08:00
抱歉。。说错了。。

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/59429

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX