算法-如何以最短的路程走遍北京的所有地铁站

算法-如何以最短的路程走遍北京的所有地铁站

夜无邪 发布于 2017-03-10 字数 58 浏览 1064 回复 2

假设每站之间的距离一样,可以走重复路线。求算法思路。

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

浮生未歇 2017-07-30 2 楼

图论中经典题目 遍历所有图中的边一次(可以重复) 求最短路径 是 邮路问题.

无向图的中国邮路问题是容易解决的,是P问题;而有向图的中国邮路问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出,而美国国家标准和技术研究院(NIST)的 Alan Goldman 首先将此问题命名为中国邮路问题。

地铁站问题是无向图问题 :

无向图上中国邮路问题的解法

若图中有欧拉回路,因为欧拉回路通过所有的边,因此任何一个欧拉回路即为此问题的解。
若图中不存在欧拉回路,其中必存在有奇数个边的端点,且这类的端点一定大于等于2个。因此有些边需要再重复一次,使奇数边的端点变为偶数边的端点。

欧拉回路的解法 也是可以完美解决的.资料还是很多.

参考: 点击我

瑾兮 2017-06-01 1 楼

这个问题并不完全等价于中国邮路问题,目的是到达所有的地铁站,没有必要遍历所有的地铁线一次。
该问题更相近与旅行商问题,唯一不同的一点是,不需要回到出发点。所以这个北京地铁站问题,可能是一个NP问题。
我想到的一个解法是:
1.求出图的所有生成树
2.把每个生成树,转化成邮路问题,用你上面的方法找出最优解
3.比较所有生成树的最优解,得到全局最优解