来一篇纯兴趣者跟公司无关的个人作品算法改进文了
不同于底子深、LeetCode 刷得勤的人，我是从兴趣与实作导向中遇到困难点才去做
算法改进的人，而且也不是说效能改良，而是因为太麻烦才改良的
先谈一下作品背景
程式名称: 接轨时刻、公共运输整合资讯 library ROCPTX
超连结: https://melixyen.github.io/railtime
library: https://github.com/melixyen/rocptx
这个作品是参考日本的转乘案内网站后设计的
因为台北捷运环状线今年通车，今年过年刚好是我的作品很重要的一个改版
所以年假几乎都在写这两支程式，加入环状线的转乘资讯
这是目前版本所使用给予环状线转乘资料的一次 github commit
https://tinyurl.com/wwvvmn3
原网址 https://github.com/melixyen/railtime/commit/17a9fcb9762cbf82b5fde708aac57f8a81f4179e
其中 ttlib/data.js 是目前版本转乘路由规则的基础资料
当选择两个站点让程式自动查找转乘路线时所依据的就是这些资料连结起来的路由匹配
并透过一些 regexp 过滤掉不适合走该路线的起迄站 id
例如中和新芦线跟淡水信义线有两个转乘站东门与民权西路，中和到世贸可以跳过
先搭到民权西路才换淡水线去台北 101 方向重复经过东门的走法
困难点
当台北的轨道运输路网越来越复杂后，像环状线加入后转乘路由暴增
以人工方式建立资料将来路网更多元后会更困难，要预想一个自动爬路径算法
改进方式
不预先建立转乘资料，自起站开始往路线两端各开一个路由搜寻
碰到转乘站就再开分支路由递回搜寻，爬过每一个节点，如果遇到重复站就放弃路线
直到所有路线都被放弃或有爬到目标车站为止
将有爬到的路线全部纪录下来，并计算经过多少车站、耗时几分钟
效能调整
车站太多，要爬的次数太多，但有些情况可以直接跳过
例如板南线在忠孝敦化到南港间没有任何转乘站，我从市政府出发不需要每一次都先
爬永春跟国父纪念馆站，应该可以直接跳到忠孝复兴跟南港展览馆站
所以在爬之前先把路网 block 切出来，转乘站与转乘站间没有经过任何可以转车之
车站的路段就统一成一个 block，比如淡水开始一直到北投才切成第二个 block
不用爬红树林、竹围、关渡.....这样要爬的次数就少很多了
结果
https://github.com/melixyen/rocptx/blob/master/src/router.v2.js
新的算法放在这个 library 内，如果从接轨时刻的网站打开 console
可以下 rocptx.router.v2.trtc.getAllLineRoute('BL10','R04')
就能找出龙山寺到信义安和所有不重复的转乘路由
也许搭到台北车站只转一趟，也许搭到西门就叫你转新店线到中正纪念堂接信义线
或者搭到忠孝复兴再爬上文湖线到大安再换信义线....都帮你列出来
把 BL10 和 R04 换成你要查的起迄捷运站代码即可
以这个为基础，当交通部更新路网资料后，让程式自动去爬就好
剩下的只是过滤掉所有不重复转乘路线，转太多次、经过车站太多的放弃掉
可能只取前三或前五给使用者参考就好
心得
我面试没刷 LeetCode 过，会跟我要 github 我就丢这个小作品
有些面试官会觉得有趣，就稍微讲解一下程式内容跟当初写算法的想法
星星数很少，不过这本来就算满冷门的应用，纯粹是个人兴趣
没有公司是因为先看到 github 而找我去面试软件工程师的
但有几次是因为 github 被其他公司请去讲解原理或 library 需要技术支援而拿到钱的
不多，一次大概几千元到几万元之间，视需求跟时数
所以在 github 上除了面试能当作品外，想赚外快也还是有机会的