Categories
程式開發

設計一個地鐵路線規劃小工具



{“ type”:“ doc”,“ content”:[{“type”:”heading”,”attrs”:{“align”:null,”level”:2},”content”:[{“type”:”text”,”text”:”概述”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”最近在找房子,因为想找一个去几个地方都相对方便的位置,自己去地图上看还挺麻烦的,所以想做个小工具,本文就简单介绍一下实现过程。目前的功能还比较简单,主体方法就是根据一个输入的始发站,列出其他所有站点到这个地方的站数最少路线。”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ paragraph” ,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ heading”,“ attrs”:{“ align”: null,“ level”:2},“ content”:[{“type”:”link”,”attrs”:{“href”:”http://lichuanyang.top/posts/13793/#%E6%95%B0%E6%8D%AE%E8%8E%B7%E5%8F%96″,”title”:”数据获取”}},{“type”:”text”,”text”:”数据获取”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”从网上找了高德地图的接口数据: “},{“type”:”link”,”attrs”:{“href”:”http://map.amap.com/service/subway?_1469083453978&srhdata=1100_drw_beijing.json”,”title”:null},”content”:[{“type”:”text”,”text”:”http://map.amap.com/service/subway?_1469083453978&srhdata=1100_drw_beijing.json”}]},{“ type”:“ text”,“ text”:“。對拿到的json串進行解析,其中包含每條地鐵線路的信息,並依次列出線路上的每個站點。”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ paragraph” ,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”通过解析数据,要得到的主要就是各个站点的信息,站点定义的数据结构如下:”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ paragraph” ,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ codeblock”,“ attrs”:{“ lang”: null},“內容”:[{“type”:”text”,”text”:”private String id;”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ codeblock” ,“ attrs”:{“ lang”:null},“ content”:[{“type”:”text”,”text”:”private String name;”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ codeblock” ,“ attrs”:{“ lang”:null},“ content”:[{“type”:”text”,”text”:”private Set lines = new HashSet(); //所在线路”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ codeblock” ,“ attrs”:{“ lang”:null},“ content”:[{“type”:”text”,”text”:”private String position;”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ codeblock” ,“ attrs”:{“ lang”:null},“ content”:[{“type”:”text”,”text”:”private String pinyin;”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ codeblock” ,“ attrs”:{“ lang”:null},“ content”:[{“type”:”text”,”text”:”private Set nextStations = new HashSet(); //相邻站点”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ paragraph” ,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”所有站点汇总后可以看做一张图,nextStations字段就是用来表示边的信息。”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ heading” ,“ attrs”:{“ align”:null,“ level”:2},“ content”:[{“type”:”link”,”attrs”:{“href”:”http://lichuanyang.top/posts/13793/#%E8%B7%AF%E7%BA%BF%E8%A7%84%E5%88%92″,”title”:”路线规划”}},{“type”:”text”,”text”:”路线规划”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”路线规划算法可以参考Dijkstra算法,由于现有的表现形式下,只是一个无向无权重的图,实现起来还要简单一些。”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ paragraph” ,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”实现过程描述如下:”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ numberedlist” ,“ attrs”:{“ start”:null,“ normalizeStart”:1},“ content”:[{“type”:”listitem”,”content”:[{“type”:”paragraph”,”attrs”:{“indent”:0,”number”:1,”align”:null,”origin”:null},”content”:[{“type”:”text”,”text”:”新建两个map, knownPath和waitingPath,分别用来表示已经确定了最短路径的站点列表,和待处理的站点列表。初始化时,knownPath中只包含指定的起点,waitingPath中包含其他所有站点,并将距离设置成无穷大(用MAX = 20000表示)”}]}]},{“ type”:“ listitem”,“ content”:[{“type”:”paragraph”,”attrs”:{“indent”:0,”number”:2,”align”:null,”origin”:null},”content”:[{“type”:”text”,”text”:”指定起点为当前节点”}]}]},{“ type”:“ listitem”,“ content”:[{“type”:”paragraph”,”attrs”:{“indent”:0,”number”:3,”align”:null,”origin”:null},”content”:[{“type”:”text”,”text”:”依次处理当前的相邻节点,更新每个节点的最短距离”}]}]},{“ type”:“ listitem”,“ content”:[{“type”:”paragraph”,”attrs”:{“indent”:0,”number”:4,”align”:null,”origin”:null},”content”:[{“type”:”text”,”text”:”从waitingPath中找到距离最短的节点,作为当前节点,重复第3步,并从waitingPath转移到knownPath”}]}]}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”整个过程结束之后,会得到每个节点到起点的最短距离以及路线详情,然后可以根据这些数据计算路线详情的换乘情况。”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ paragraph” ,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”对于换乘,主体判断逻辑是,如果一个站点的上一站和下一站所在路线不重合,就可以确定在这一站进行了换乘,比如灯市口-东四-朝阳门,灯市口在5号线上,朝阳门在2,6号线上,可以断定在东四肯定作了换乘。不过还有一些特殊情况要处理,比如说西直门到平安里,中间那站如果是车公庄(虽然现实中没人会这么干),实际就是作了换乘的,但是按刚才的逻辑就会判断成未换乘。”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ paragraph” ,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”最终得到的路线信息中包含以下信息:”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ codeblock” ,“ attrs”:{“ lang”:null},“ content”:[{“type”:”text”,”text”:”private String stationId;”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ codeblock” ,“ attrs”:{“ lang”:null},“ content”:[{“type”:”text”,”text”:”private int length;”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ codeblock” ,“ attrs”:{“ lang”:null},“ content”:[{“type”:”text”,”text”:”private int transferNum; //换乘数”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ codeblock” ,“ attrs”:{“ lang”:null},“ content”:[{“type”:”text”,”text”:”private List detail = new ArrayList(); //详细路径”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ heading” ,“ attrs”:{“ align”:null,“ level”:2},“ content”:[{“type”:”link”,”attrs”:{“href”:”http://lichuanyang.top/posts/13793/#%E7%94%A8%E9%80%94″,”title”:”用途”}},{“type”:”text”,”text”:”用途”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”主体功能在上面已经完成,后边就可以根据需要再去自定义处理了。比如,加入我现在需要找到”距奥林匹克公园站15站以内且距天安门东站7站以内的位置”,就可以分别输入奥林匹克公园和天安门东,然后在结果中作相应的过滤,再取交集。”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ heading” ,“ attrs”:{“ align”:null,“ level”:2},“ content”:[{“type”:”link”,”attrs”:{“href”:”http://lichuanyang.top/posts/13793/#%E5%90%8E%E7%BB%AD%E8%AE%A1%E5%88%92″,”title”:”后续计划”}},{“type”:”text”,”text”:”后续计划”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”目前做的还比较简单,只是简单考虑站数,但是实际上,不同站点的距离、耗时相差会比较大,再一个不同地方的换乘开销差别也很大。所以后续会试试能不能找到换乘站的详情数据,还有两站之间耗时的数据,并应用到算法中。”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ paragraph” ,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”再一个是要找一个合适的方法做个界面出来,因为一直做的是纯后台,还没考虑清楚用什么合适。”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ paragraph” ,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”其他的,还在考虑爬一下房价信息。”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ heading” ,“ attrs”:{“ align”:null,“ level”:2},“ content”:[{“type”:”link”,”attrs”:{“href”:”http://lichuanyang.top/posts/13793/#%E4%BB%A3%E7%A0%81″,”title”:”代码”}},{“type”:”text”,”text”:”代码”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”link”,”attrs”:{“href”:”https://github.com/lcy362/FoxSubway”,”title”:null},”content”:[{“type”:”text”,”text”:”https://github.com/lcy362/fox-subway”}]}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”欢迎提意见。”}]},{“ type”:“ paragraph”,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null}},{“ type”:“ paragraph” ,“ attrs”:{“ indent”:0,“ number”:0,“ align”:null,“ origin”:null},“ content”:[{“type”:”text”,”text”:”原文地址: “},{“type”:”link”,”attrs”:{“href”:”https://lcy362.github.io/posts/13793″,”title”:null},”content”:[{“type”:”text”,”text”:”https://lichuanyang.top/posts/13793/”}]}]}]}