论文部分内容阅读
2013年1月13日，小来和小谷将筹划已久的一项地铁极客行动付诸实践：买一张两元钱的地铁通票，不出站，计划17个小时内通过北京所有的地铁站点（除机场线）。他们于当天清晨5点15分出发，晚上10点40分结束，历经319站次，560公里，用17个小时25分钟完成了这次挑战，比数学建模预计的时间仅仅多了25分钟。
数学建模画出路线
小来是中科院的在读博士生，专攻计算机软件。有一次，小来在微博上看到一道好玩的面试题，要求在尽可能短的时间内走一遍北京的地铁站，并且只在地铁内换乘，不出站。这个题目也引起了很多计算机算法控迷们的讨论。
小来觉得这个题目很有意思。2012年年底，他找了几个朋友，在计算机编程的圈子里搞了一个“算法控”马拉松程序设计竞赛，以微博上的那道面试题为蓝本，提供相邻站之间的行驶时间，以及各换乘站之间的换乘时间，要求结果给出一条能经过所有站点的最优线路。
为了让更多的人参与，小来和朋友们安排了两个组，一个是提交算法代码的，另一个是手工安排路线。结果参与的高手还真不少。算法组冠军提交的代码是欧拉图（通过无向图或有向图中所有边，一次且仅一次行遍图中所有顶点的通路称为欧拉通路（回路），具有欧拉回路的图称为欧拉图）的模型，把欧拉图遍历一遍，在某个路口如有多重走法，按照不换乘，换乘时间少的走法的顺序选择。由于算法有一定的随机性，把它循环运行n遍后，再选择用时最短的输出。
根据这个模型，小来对照地铁线路图估算了一下，觉得可以在一天之内走完北京全部地铁站点，于是更坚定了他亲身实践的信心：“以前坐地铁只是为了抵达目的地，这次换种方式坐地铁，本身就很好玩。更重要的是，通过实地体验，还可以衡量出算法模型的精准度，给比赛留一个完美的纪念。”
小来的同学小谷对这个行动也非常感兴趣，于是加入了进来。他们最终规划的线路是直接使用比赛冠军的代码计算出来的。“是不是最优我也不确定，但是至少看起来重复路线特别少，应该很接近最优路线。在预算2元的限制下，我们的路线将经过北京地铁除机场线外（票价25元，所以不作考虑）的所有站点。”
出发前，小来和小谷又花了好几天，对计划时间表和路线图进行了反复的核算，这可是保证这次行动成功的关键。他们先在网上查到之前地铁粉丝做出的换乘时间的统计，然后打算按地铁发车班次的先后顺序进行，从5时15分坐上房山线开始，每条线路坐几站，在哪里换乘，行车换乘各用多久时间，都精确到了分钟。比如9点12分，乘坐10号线从西局出发朝六里桥方向坐到公主坟；10时42分，乘坐1号线从苹果园出发向古城方向坐到四惠东；17点30分，乘坐8号线从回龙观东大街出发朝霍营方向坐到鼓楼大街，并计划在21时55分到达亦庄线终点站次渠，赶上末班车结束挑战，整一圈走下来接近17个小时，将总共经过319站次，换乘19次，其中重复经过的站点有99个。
但精确到分钟还不够，就在出发前两天，他们发现了一个很大的失误。“在估算列车行驶时间时，我们是通过首末班车来估计的。比如一号线首班车复兴门5：15，西单5：17，这两站之间的行驶时间就是2分钟。但是看末班车时间表时发现复兴门23：24，西单23：27，行驶时间要3分钟。我和小谷在分别核算的时候发现按首班车时刻表和按末班车时刻表算出来的总时间不一致，最多相差将近一小时，再深入分析才发现是因为忽略了时刻表分钟后的秒。发现这个问题后，我们决定全部使用末班车的时间表，这样一来估算就更准确了。”
仅仅多了25分钟
2013年1月12日晚，小来和小谷在房山线苏庄站附近的一个旅馆提前安顿了下来。1月13日，天还没亮，他们就收拾好背包，带着手机、资料出发了。
5时15分，挑战开始了。要完成理论上17个小时走完全程的目标，还是相当有难度的。由于每站留给他们的时间都很紧迫，小来和小谷既要拿着路线图和时间表保证不出错，还要拍照发微博，喝点水上个厕所什么的，为了尽可能节省时间，一路上，他们都是以“快步走”的速度换乘。除了记录下各个地铁站的特色文化，他们还忠实地记录下每个地铁站换乘花费的时间，希望为其他的乘客提供参考。“6号线呼家楼站，换乘10号线用时1分20秒；5号线宋家庄站，换乘亦庄线需1分24秒；10号线公主坟站，换乘1号线需要2分10秒。”
八九点后，人流渐渐多了起来，两人的步伐也加快了。正当小来和小谷庆幸挑战还算顺利的时候，突然出了状况，6号线临时停车5分钟。9点多时，又等来了10号线的区间车。10号线在开通后一直采用区间车和全线车并存的运营模式，区间车的终点站是车道沟站，两人只好在车道沟下车等候下一班车，这样就相当于多等了一次车。“为了将这些计划外多花的时间补回来，我们不得不绷紧神经，在换乘时停止拍照发微博，也停止了交谈，各自在车厢内整理、记录好站点的资料，下车就加快脚步赶路。就连上洗手间，也是在等车和换乘间隙，分秒必争地到车站的卫生间完成的。”
上午，他们总共换乘了8条地铁线。紧凑的行程让小来和小谷忘了时间，直到肚子咕咕叫起来。下午1点半，他们利用在天宫院等车的时间吃了巧克力和面包，算是中餐了。
直到21时55分顺利到达终点站次渠，两人这才松了口气。简单估算一下，最终完成时间大约比预计时间多了半小时。“除去因为车辆临时停车、坐了10号线区间车、临时更换移动电源多花费的15分钟，我们这次所用时间和预测模型的误差约为10分钟，还是比较精确的。
想要成功挑战地铁，需要具备一定的数学功底和计算机编程、计算能力，如果你同样也是地铁迷，那也不妨一试哦！小来建议：“如果以后有人还想挑战的话，建议尽量避免上下班高峰、预留就餐和上洗手间时间、带足移动电源。”
责任编辑：曹晓晨
Tips：地铁挑战
地铁挑战是从国外兴起的一项运动，最早始于纽约地铁，甚至为此纽约还成立了一个名为Amateur New York Subway Riding Committee的部门，专门规范地铁挑战。他们规定的挑战有三种：A.所有区间、所有站点都乘遍；B.所有站点都去遍；C.所有站点都经过（包括不停车的经过）。吉尼斯纪录对挑战纽约地铁也有定义，他们在规则B的基础上，允许挑战者乘坐公共地面交通（不包括的士）摆渡。按这套规则看来，小来和同学小谷挑战的是B项。
在国内也有类似的挑战。对上海地铁的挑战，早在2009年就已经有了。上海八号线南段开通后，有两位学生在一天内乘完了所有区间，花费了13小时9分18秒。2011年有挑战者耗时18小时26分11秒成功乘遍包括新开通的7号线北延伸段在内的上海地铁全网所有区间、所有车站。由于上海地铁郊区线特别多，挑战者都使用了公交车或者的士作为中间过渡。
就在小来挑战北京的地铁的第二天，华南理工大学电子商务大四学生陆松万购买了“广州地铁一日票”，从大学城南进站，历经204个站点、335公里，总用时12小时13分，完成了“一日票走遍羊角”的挑战计划。网友笑笑卡乐猫也预告即将尝试坐遍广州地铁的所有区间和站。
数学建模画出路线
小来是中科院的在读博士生，专攻计算机软件。有一次，小来在微博上看到一道好玩的面试题，要求在尽可能短的时间内走一遍北京的地铁站，并且只在地铁内换乘，不出站。这个题目也引起了很多计算机算法控迷们的讨论。
小来觉得这个题目很有意思。2012年年底，他找了几个朋友，在计算机编程的圈子里搞了一个“算法控”马拉松程序设计竞赛，以微博上的那道面试题为蓝本，提供相邻站之间的行驶时间，以及各换乘站之间的换乘时间，要求结果给出一条能经过所有站点的最优线路。
为了让更多的人参与，小来和朋友们安排了两个组，一个是提交算法代码的，另一个是手工安排路线。结果参与的高手还真不少。算法组冠军提交的代码是欧拉图（通过无向图或有向图中所有边，一次且仅一次行遍图中所有顶点的通路称为欧拉通路（回路），具有欧拉回路的图称为欧拉图）的模型，把欧拉图遍历一遍，在某个路口如有多重走法，按照不换乘，换乘时间少的走法的顺序选择。由于算法有一定的随机性，把它循环运行n遍后，再选择用时最短的输出。
根据这个模型，小来对照地铁线路图估算了一下，觉得可以在一天之内走完北京全部地铁站点，于是更坚定了他亲身实践的信心：“以前坐地铁只是为了抵达目的地，这次换种方式坐地铁，本身就很好玩。更重要的是，通过实地体验，还可以衡量出算法模型的精准度，给比赛留一个完美的纪念。”
小来的同学小谷对这个行动也非常感兴趣，于是加入了进来。他们最终规划的线路是直接使用比赛冠军的代码计算出来的。“是不是最优我也不确定，但是至少看起来重复路线特别少，应该很接近最优路线。在预算2元的限制下，我们的路线将经过北京地铁除机场线外（票价25元，所以不作考虑）的所有站点。”
出发前，小来和小谷又花了好几天，对计划时间表和路线图进行了反复的核算，这可是保证这次行动成功的关键。他们先在网上查到之前地铁粉丝做出的换乘时间的统计，然后打算按地铁发车班次的先后顺序进行，从5时15分坐上房山线开始，每条线路坐几站，在哪里换乘，行车换乘各用多久时间，都精确到了分钟。比如9点12分，乘坐10号线从西局出发朝六里桥方向坐到公主坟；10时42分，乘坐1号线从苹果园出发向古城方向坐到四惠东；17点30分，乘坐8号线从回龙观东大街出发朝霍营方向坐到鼓楼大街，并计划在21时55分到达亦庄线终点站次渠，赶上末班车结束挑战，整一圈走下来接近17个小时，将总共经过319站次，换乘19次，其中重复经过的站点有99个。
但精确到分钟还不够，就在出发前两天，他们发现了一个很大的失误。“在估算列车行驶时间时，我们是通过首末班车来估计的。比如一号线首班车复兴门5：15，西单5：17，这两站之间的行驶时间就是2分钟。但是看末班车时间表时发现复兴门23：24，西单23：27，行驶时间要3分钟。我和小谷在分别核算的时候发现按首班车时刻表和按末班车时刻表算出来的总时间不一致，最多相差将近一小时，再深入分析才发现是因为忽略了时刻表分钟后的秒。发现这个问题后，我们决定全部使用末班车的时间表，这样一来估算就更准确了。”
仅仅多了25分钟
2013年1月12日晚，小来和小谷在房山线苏庄站附近的一个旅馆提前安顿了下来。1月13日，天还没亮，他们就收拾好背包，带着手机、资料出发了。
5时15分，挑战开始了。要完成理论上17个小时走完全程的目标，还是相当有难度的。由于每站留给他们的时间都很紧迫，小来和小谷既要拿着路线图和时间表保证不出错，还要拍照发微博，喝点水上个厕所什么的，为了尽可能节省时间，一路上，他们都是以“快步走”的速度换乘。除了记录下各个地铁站的特色文化，他们还忠实地记录下每个地铁站换乘花费的时间，希望为其他的乘客提供参考。“6号线呼家楼站，换乘10号线用时1分20秒；5号线宋家庄站，换乘亦庄线需1分24秒；10号线公主坟站，换乘1号线需要2分10秒。”
八九点后，人流渐渐多了起来，两人的步伐也加快了。正当小来和小谷庆幸挑战还算顺利的时候，突然出了状况，6号线临时停车5分钟。9点多时，又等来了10号线的区间车。10号线在开通后一直采用区间车和全线车并存的运营模式，区间车的终点站是车道沟站，两人只好在车道沟下车等候下一班车，这样就相当于多等了一次车。“为了将这些计划外多花的时间补回来，我们不得不绷紧神经，在换乘时停止拍照发微博，也停止了交谈，各自在车厢内整理、记录好站点的资料，下车就加快脚步赶路。就连上洗手间，也是在等车和换乘间隙，分秒必争地到车站的卫生间完成的。”
上午，他们总共换乘了8条地铁线。紧凑的行程让小来和小谷忘了时间，直到肚子咕咕叫起来。下午1点半，他们利用在天宫院等车的时间吃了巧克力和面包，算是中餐了。
直到21时55分顺利到达终点站次渠，两人这才松了口气。简单估算一下，最终完成时间大约比预计时间多了半小时。“除去因为车辆临时停车、坐了10号线区间车、临时更换移动电源多花费的15分钟，我们这次所用时间和预测模型的误差约为10分钟，还是比较精确的。
想要成功挑战地铁，需要具备一定的数学功底和计算机编程、计算能力，如果你同样也是地铁迷，那也不妨一试哦！小来建议：“如果以后有人还想挑战的话，建议尽量避免上下班高峰、预留就餐和上洗手间时间、带足移动电源。”
责任编辑：曹晓晨
Tips：地铁挑战
地铁挑战是从国外兴起的一项运动，最早始于纽约地铁，甚至为此纽约还成立了一个名为Amateur New York Subway Riding Committee的部门，专门规范地铁挑战。他们规定的挑战有三种：A.所有区间、所有站点都乘遍；B.所有站点都去遍；C.所有站点都经过（包括不停车的经过）。吉尼斯纪录对挑战纽约地铁也有定义，他们在规则B的基础上，允许挑战者乘坐公共地面交通（不包括的士）摆渡。按这套规则看来，小来和同学小谷挑战的是B项。
在国内也有类似的挑战。对上海地铁的挑战，早在2009年就已经有了。上海八号线南段开通后，有两位学生在一天内乘完了所有区间，花费了13小时9分18秒。2011年有挑战者耗时18小时26分11秒成功乘遍包括新开通的7号线北延伸段在内的上海地铁全网所有区间、所有车站。由于上海地铁郊区线特别多，挑战者都使用了公交车或者的士作为中间过渡。
就在小来挑战北京的地铁的第二天，华南理工大学电子商务大四学生陆松万购买了“广州地铁一日票”，从大学城南进站，历经204个站点、335公里，总用时12小时13分，完成了“一日票走遍羊角”的挑战计划。网友笑笑卡乐猫也预告即将尝试坐遍广州地铁的所有区间和站。