來一篇純興趣者跟公司無關的個人作品演算法改進文了
不同於底子深、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 上除了面試能當作品外，想賺外快也還是有機會的