里程最长的地铁哪条,运营里程最长的地铁

2015年，网站「MNYC」试图发文吸引读者自己开电脑遍历，寻找纽约市地铁的最长路线。

In Search of the Longest Subway Ride | WNYC | New York Public Radio, Podcasts, Live Streaming Radio, News​www.wnyc.org/story/search-longest-subway-ride/

2018年

( 可能是 ) 最漫长的帝都地铁之旅​mp.weixin.qq.com/s?__biz=MzAwNDkyMjg0Mw==&mid=2247485058&idx=1&sn=eebd4eae55fd8e5235dc8826220015a4&chk *** =9b25ca36ac524320c38feaa9817a94b9c1c90f83cbd12d62337cce91b059903f07377bbd160d&scene=0#rd

看起来他们都不知道比较简化的可靠算法。

这两个问题是一致的。

无向、有环连通图每一条边上的长度不同（有正的权重），节点没有权重求任意或给定两点间的最长路线，不可以重复通过同一条边，但可以重复通过节点

可以合理地猜测，最长路线可能可以互相转化，而非唯一的。

这个问题和另外一类不能重复通过节点的问题不同。那个问题已经被证明是NP-hard（据英文 *** ），没有很快的算法。

需要注意的是，

部分地铁系统有单向区间，或者同一区间往来长度不同。如有可能简化，应将其简化。部分地铁系统有跨区间换乘。这些换乘站应被视为同一个站，被同一换乘站覆盖的区间应被视为一条起终点都在该站的边，计算时可以先取出，最后加在路径中——因为只要你经过这个换乘站，你就一定要走一次这条边。

——由于这是一个闲得无聊的人才会应用的问题，所以也许没有现成好找的算法。我找来找去也没找到网上哪里写了这个算法，因此斗胆写出来。

但这个算法很简单，大概肯定有人想过。

这里没有给出证明。以我的能力也无法给出证明。

这是一个欧拉路径或者「一笔画问题」的变种。

欧拉说，如果连通图中的所有节点里，连接的边数是奇数的节点数量为0或2，那么该图存在欧拉路径，或者说可以一笔画。下图中圆圈内的数字即表示与节点相连的边数。——还需要注意的是，下图不是连通图。

作者维基共享资源用户Pan，详情见https://commons.wikimedia.org/wiki/File:UndirectedDegrees_(Loop).svg

如果图中所有节点连接的边数都是偶数，那么从任意一点开始都可以一笔画，路径最后会回到起点；而如果有两个奇数节点，那么一笔画必须从其中一个奇数节点开始，到另一个奇数节点结束。

下图中的“串”字，只有顶部和底部两个奇数节点（各自连接1条边），其余节点为2（左右两侧）和4（中间），因此可以一笔画，起点和终点必须分别位于两端。由于“串”字由此性质，路边烤串摊使用一根LED灯带就能做成招牌。

作者维基共享资源用户A52ljgh89，作者释出至公有领域

问题是，绝大多数地铁系统有超过2个奇数节点（任何不是换乘站的终点站都是连接1条边的节点），因此没有欧拉路径。需要放弃部分边，以使得欧拉路径存在。

也就是说，这个问题可以转化成：求全地铁线网的最长路线（任意两点），是求边的总长（权重）最大的、存在欧拉路径的子图。

由于图的总长（所有边长度的和）一定，所以求最长可以反过来认为是求放弃的边最短。

欧拉还说，一个图中，奇数节点的数量一定是偶数。

那么，如果假设这个数是n，最少只需要放弃数量为n−22\frac{n-2}{2} 的边，即可保证奇数节点的数量是2。

但有的时候是不行的，有的奇数节点的相邻节点都是偶数节点，因此放弃的边数要大于这个数。

但是，将放弃的边尽可能首尾相连，它们形成的路径数量应该是n−22\frac{n-2}{2}，并以奇数节点为起终点。

因此将问题转化成：在所有奇数节点间两两配对，使它们之间的最短路径的长度和最短。

算法

算法针对指定起终点的情况。可以合理地认为，重复这一步骤即可变成求任意两点间的最长路径。

寻找除起终点以外，所有的奇数节点。计算这些节点中任意两点间的最短路径长度，形成距离表，并记录所有最短路径。（无向图多源最短路径）根据距离表，求使得总长度最小的配对。（「最优配对问题」）删除与最小配对相对应的路径，使图变成半欧拉图。求欧拉路径。

对于地铁系统来说，第一步可以手动完成。也存在相应的算法。

无向图多源最短路径有很多应用，是被充分研究的问题，不再赘述。

「最优配对问题」在网上被作为动态规划的案例来介绍，如动态规划之最优配对问题 - 师毅的Blog - CSDN博客

最后求欧拉路径可以手动处理。据英文维基也有线性复杂度的算法。

因此至少对于地球上现存的地铁系统，这个问题可以在非常短的时间内完成。

案例

下面以求北京地铁的最长路线为例，展示一下这个算法。

起点设定为苏庄，终点设定为俸伯。可以合理地推测这个组合会产生任意两点间的最长路径。

由于北京地铁系统自2016年起开通的新线没有公布站间距，根据2015年末北京地铁图，及北京地铁官网提供的站间距来计算。

包含机场线，但认为由三元桥经3号航站楼、2号航站楼回到三元桥属于重复路径。认为7号线没有双井站。

一、任意两站之间的最短路径用程序事先求出。

注意既需要长度数字也需要具体路线。

二、对图进行一些不必须的简化。

任何只接了两条边的节点都可以被移除。这其实一点用也没有，主要是为了简化展示。

由于起终点已经确定，那些显然不会进去的「死路」也可以移除。奇数节点总数不会变化，只是会从终点移动到首个换乘站。比如天通苑北（1）是奇数节点，在移除立水桥到天通苑北这个尾巴后立水桥从4变成3，相当于奇数点从天通苑北移动到立水桥，总数没变。这一步唯一的实际意义可能是简化后面删边的时候的人工操作。

三、找出奇数节点

四、列出这些节点所有两两组合间的最短路径长度

在第一步已经求出来了表，取出相应的行和列。

五、求总和最少的配对

本步骤为「最优配对问题」，不能指望人手操作

结果是

站点公主坟大望路西直门海淀黄庄国家图书馆北京南站立水桥宋家庄七里庄三元桥总计站点北京西站金台路南锣鼓巷西二旗慈寿寺角门西奥林匹克公园九龙山西局望京途经线路、、、、、、、、长度站点站点途经线路长度公主坟北京西站1、92750大望路金台路141602西直门南锣鼓巷4、64795海淀黄庄西二旗10、1311266国家图书馆慈寿寺9、63693北京南站角门西42307立水桥奥林匹克公园5、157897宋家庄九龙山10、148987七里庄西局14845三元桥望京10、13、156672总计50634\begin{array}{cccr} \text{站点} & \text{站点} & \text{途经线路} & \text{长度} \\ \hline \text{公主坟} & \text{北京西站} & \text{1、9} & \text{2750} \\ \text{大望路} & \text{金台路} & \text{14} & \text{1602} \\ \text{西直门} & \text{南锣鼓巷} & \text{4、6} & \text{4795} \\ \text{海淀黄庄} & \text{西二旗} & \text{10、13} & \text{11266} \\ \text{国家图书馆} & \text{慈寿寺} & \text{9、6} & \text{3693} \\ \text{北京南站} & \text{角门西} & \text{4} & \text{2307} \\ \text{立水桥} & \text{奥林匹克公园} & \text{5、15} & \text{7897} \\ \text{宋家庄} & \text{九龙山} & \text{10、14} & \text{8987} \\ \text{七里庄} & \text{西局} & \text{14} & \text{845} \\ \text{三元桥} & \text{望京} & \text{10、13、15} & \text{6672} \\ \hline \text{总计} & \text{ } & \text{} & \text{50634} \end{array} \\

把它们标在线路图上

把它们去掉，剩下的就是一个只有两个奇数节点（起终点）的图了~

六、求欧拉路径

文字描述：苏庄—郭公庄—北京西站—九龙山—大望路—军事博物馆—白石桥南—平安里—北京南站—十里河—三元桥（外环，下同）—东直门—东直门（2号线绕一圈）—芍药居—知春路（10号线）—西直门—海淀黄庄—宋家庄—大屯路东—望京西—西二旗—朱辛庄—南锣鼓巷—金台路—望京—俸伯

本路线自苏庄至俸伯总里程是294461m。

当然，由于帝都绘使用的是现在（2017年末开通）的线网，和2015年末相比除了从连通图变成不连通图，和增加了两条无关紧要的尾巴之外，主要变化因素是多了燕房线，使得最长路径的起点从苏庄移动到了燕山。

但是由于从燕山到苏庄的长度是定值，不会影响路线的相对长度大小，所以还是可比的。设为a的话，我的长度是294461m+a，上方帝都绘推送的长度是292611m+a，我的线路比帝都绘的长1850m。

这个结果已经经过帝都绘确认，今天他们发表了新的推送，介绍了这条路线。

帝都绘​mp.weixin.qq.com/s?__biz=MzAwNDkyMjg0Mw==&mid=2247485533&idx=1&sn=2a4c2df756184c8db3846f5d2cb055fc&chk *** =9b25c4e9ac524dff38214fa7a3dd34fcb43e28854b0391815da77dc1d2e93df37f50273133b5&scene=0&xtrack=1#rd

欢迎在评论区：

提供以前别人写过这个算法的线索证明或证伪这个算法在上方案例图中找到更长的路线

所有文字，版权所有 © 2018 hat600

未标注版权信息的图片，署名Ran、hat600，按CC BY-SA 3.0未本地化版本提供。但是，所有内容为表格的图片，均不保留权利。