「台北捷運路線查詢系統」是我碩一高等演算法的最後一個(第五個)程式作業，這個作業是我認為五個作業裡最有價值的一個，為什麼呢？因為有跟生活產生關係，不只是為了交差而寫，更是為了我的生活而寫，多麼有成就感哪～
事實上我每個作業除了寫完程式之外，還會將實做過程細節給記錄下來，因為我相信未來一定還會用到這些資料，果真這時候的我直接複製貼上到部落格XD～還是要再次感謝過去的我如此有遠見，寫了整整18頁A4的報告，在此我將濃縮報告精華，期許哪天我能把它寫成APP：）
作業問題描述
你要幫捷運局開發一套捷運路線查詢系統，它可讓乘客查詢從某起點站到某終點站搭捷運的最佳路徑。你可能考慮的版本並在報告中說明的項目如下：
- 最簡單的版本一：只將路網視為一個圖，一個站視為一個節點，相鄰的站與站之間視為有一個邊存在，從某起點站到某終點站搭捷運的最佳路徑為經過的總站數最少的一條路徑。那麼應如何表示台北捷運路線網比較好？用adjacency matrix或adjacency list何者較優？其中內容如何安排較適合。可用何種演算法尋找最短路徑？
- 稍為複雜的版本二：再考慮車班（紅線、黃線、藍線、綠線等），最佳路徑為換的車最少，而且經過的總站數較少的一條路徑。那麼資料結構及演算法要如何修改？
- 更複雜的版本三：同時要記錄站與站之間的票價，最佳路徑為花的錢最少、換的車最少，而且經過的總站數較少的一條路徑。那麼資料結構及演算法要如何修改？
- 在實際的應用中，何謂最佳路徑？可用何種演算法實現？需要稍做修改還是大改？
2010年花卉博覽會剛開幕，老師可能也是為了讓作業跟生活產生連結，所以才會設計這樣子的問題。
我綜合版本一、二、三寫一個實用版本，使程式功能可以直接應用在日常生活中，雖然以現在來看並不怎麼實用ＸＤ～
台北捷運路線圖
首先分析「台北捷運路線圖」的整個模樣，捷運於99年11月初啟用「蘆洲線」，整個網路線有89個捷運站，站與站的連結有103條，於是我創造89個node、103條edge。
節點有分「樞紐點」和「邊陲點」，也就是說節點的degree可以代表其重要性。每個節點至少有1 degree，至多目前為4 degree。
- 4 degree：有臺北車站、忠孝復興、民權西路。
- 3 degree：有忠孝新生、西門、中正紀念堂、古亭、北投、七張。
- 2 degree：有……不是4、3、1者皆是，因為太多了，不予列舉。
- 1 degree：有淡水、新店、永寧、動物園、南勢角、蘆洲。
- 特殊點如「南港」和「南港展覽館」，需要公車當接駁車。另一個特殊點如動物園，它連接貓空纜車，然而在此不予討論。
- 4, 3 degree代表樞紐點，1 degree代表終點。
根據我搭捷運的經驗，樞紐點的人潮最多，逐漸往終點駛去，人潮越來越少。特殊線路如「西門－小南門－中正紀念堂」和「七張－碧潭」，西門和中正紀念堂因為位於北車附近，人潮還算多，而七張位於邊陲地帶，人潮有點少。
首先來說明黃色和綠色標號所代表的意義。首先是黃色，它代表每個捷運站的index（從0開始），那為什麼中山國小要設為0呢？其實是因為方便我寫程式XD～因為我想將票價列入查詢資料之一，於是去台北捷運官網下載票價表，以下我節錄前面部份。照著官方的列表從0開始標記，結果就會是上圖所呈現樣。
此外，觀察仔細一點可以發現，我在某些樞紐點上有多一個編號，為什麼呢？因為參考「台北捷運票價表」，從0到92編號，其中有臺北車站、忠孝新生、忠孝復興、民權西路四個站有兩個編號。雖然多了一個編號，但並不會造成程式的複雜度，因為該點的兩個編號有相同的設定。
接著是綠色，我所設計的捷運路線圖有特別的地方，原本站與站之間的權重皆為１，不失一般原則與經驗，在交通樞紐地帶權重有２、３、４、５。說明如下：
- 權重１（未標示者）：為一般路線，多為1 degree點間的邊。
- 權重２：為重要路線，多為3 degree樞紐點的邊。
- 權重３：為權重２的進階，多為4 degree樞紐點的邊，因為接近市區，乘客數眾多。。
- 權重４：為支線，多為3 degree樞紐點的邊，然而因為搭乘人數少，只有單向車道來回。
- 權重５：為銜接路線，因為需要公車來接駁。
- 我倒是沒有考慮到若不轉車，其實就可以忽略權重。
演算法和資料結構
-
使用Floyd–Warshall algorithm當演算法
因為它是All-Pairs Shortest Path，可以計算各個點到其它所有點的最佳路徑，雖然作業要求只需查詢一條路線，然而為了可以重複查詢，一次搞定各個點到其它所有點的關係可謂一勞永逸。
-
使用adjacency matrix作為資料結構
若想要節省空間，當然使用adjacency list會比較恰當，然而在實做方便性上，使用adjacency matrix可以避免操作太多的指標而減少許多技術上的錯誤。再者一方面，在捷運站數固定之下，在執行過程中，記憶體不會不斷地擴張；另一方面，配合演算法，處理陣列資料會比處理串列資料還要快，因為有index資訊。以上，所以使用adjacency會相當適合且實際。
程式的執行
只有簡單的黑底白字介面，未來想寫成人性化介面的APP。
(—————–台北捷運路線查詢系統————–)
! -> Choose the number of menu to perform~
*****************************************************
1 -> 查詢 2 站間的票價（OneToOne）
2 -> 查詢 1 站到其它所有站的票價（OneToAll）
3 -> 查詢 2 站間的路徑（OneToOne無權重）模擬一般時刻
4 -> 查詢 2 站間的路徑（OneToOne有權重）模擬巔峰時刻
5 -> 列印經過最多站資訊：路線、站數、票價、轉乘次數
5 -> 必須先執行 3 或 4 ！
*****************************************************
? ->
程式有以上五個功能，每個都來試驗一遍，深紅粗體字為輸入，深紅字為輸出。
- 查詢 2 站間的票價OneToOne（選擇1）
Starting Station: 公館
Ending Station: 內湖
*OneToOne Fare from 公館 to 內湖: 45
- 查詢 1 站到其它所有站的票價OneToAll（選擇2）
Starting Station: 公館
*OneToAll Fare from 公館 to All:
．中山國中 30
．南京東路 30
．忠孝復興 25
．大安 25
．科技大樓 30
……
……
．三重國小 30
．三和國中 30
．徐匯中學 30
．三民高中 35
．蘆洲 35
- 無權重（選擇3）
請輸入開始站名：善導寺
請輸入結束站名：三重國小
*善導寺 -> 臺北車站 -> 中山 -> 雙連 -> 民權西路 -> 大橋頭 -> 三重國小*
請輸入開始站名：古亭
請輸入結束站名：龍山寺
*古亭 -> 中正紀念堂 -> 小南門 -> 西門 -> 龍山寺*
- 有權重（選擇4）
請輸入開始站名：善導寺
請輸入結束站名：三重國小
*善導寺 -> 忠孝新生 -> 松江南京 -> 行天宮 -> 中山國小 -> 民權西路 -> 大橋頭 -> 三重國小*
請輸入開始站名：古亭
請輸入結束站名：龍山寺
*古亭 -> 中正紀念堂 -> 小南門 -> 西門 -> 龍山寺*
- 查詢捷運經過最多站之路線、站數、票價、轉乘次數（先選3，再選5的結果）
Stationmost: 32
Passmost:
淡水 -> 紅樹林 -> 竹圍 -> 關渡 -> 忠義 -> 復興崗 -> 北投 -> 奇岩 -> 唭哩岸 -> 石牌 -> 明德 -> 芝山 -> 士林 -> 劍潭 -> 圓山 -> 民權西路 -> 中山國小 -> 行天宮 -> 松江南京 -> 忠孝新生 -> 忠孝復興 -> 忠孝敦化 -> 國父紀念館 -> 市政府 -> 永春 -> 後山埤 -> 昆陽 -> 南港 -> 南港展覽館 -> 南港軟體園區 -> 東湖 -> 葫洲 ->
–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>–1>>
Faremost: 31
Turnmost: 3
話說我寫的程式有擴充性（方便程式設計師），只要更新票價表、站與站的連結和站所歸屬的捷運線即可！想要做個高雄捷運查詢系統也不是問題呢～未來寫成APP時，還會加上彈性（方便程式設計師）和使用性（方便使用者）！未來無論台北捷運怎麼加新的捷運線，我的APP依然可以輕易升級～其實最重要的事莫過於使用者經驗，於是將來我所設計的APP一定會先自己把玩，若是自己設計的APP都不想用的話，其他使用者會想要用嗎？呵呵～
可以在此先想像一下未來整個台北捷運路線圖 (Taipei MRT Route Map)的全貌，其實一切都掌握在我手中了：Ｐ
聽說日本、韓國、美國的捷運票價是台灣的五倍以上，生長在台灣真的很幸福！我住在臺北將近四年半，每個禮拜幾乎都會搭捷運或公車，隨身攜帶學生證悠遊卡，就算我沒有自己的交通工具，也能四處旅行和流浪～話說，我大學四年使用悠遊卡次數高達2000次呢！也就是一天至少使用一次（四年約365*4天）。
參考：臺北大眾捷運股份有限公司、WiKi – Floyd–Warshall algorithm。
逍遙文工作室 
Comments on: "台北捷運路線查詢系統 (Taipei MRT Route Query System)" (2)
開始要做App啦～ 😛
讚讚
[…] 乍看這一張圖以為是台北捷運路線圖 (Taipei MRT Route Map)的另一種繪圖表示，然而仔細端詳後，發現各個捷運站上的數字都不太一樣，這讓我想起去年演算法作業所寫的台北捷運路線查詢系統，是以某種順序表示各個捷運站的編號，不過這一張繪圖竟然完全表達出台北捷運週邊的房價！ […]
讚讚