挑战北京地铁17小时 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分钟。我和小谷在分别核算的时候发现按首班车时刻表和按末班车时刻表算出来的总时间不一致,最多相差将近一小时,再深入分析才发现是因为忽略了时刻表分钟后的秒。发现这个问题后,我们决定全部使
挑战北京地铁17小时 来自淘豆网m.daumloan.com转载请标明出处.
