歡迎來到圖論演算法 II！
在之前的學習中，你已經學會了如何找出兩點之間的最短路徑（Dijkstra 演算法）。但如果你是一位郵差，需要走遍街區內的每一條街道呢？或者是一位外送員，需要走遍每一個住戶並回到起點呢？
在本章中，我們將探討決策數學（Decision Mathematics）中最著名的兩個問題：路線檢查問題（Route Inspection Problem）和旅行推銷員問題（Travelling Salesman Problem）。這些演算法每年能為企業節省數以百萬計的燃料與時間成本！
1. 路線檢查問題
這個問題又稱為中國郵差問題（Chinese Postman Problem），其目標是找出最短的路線，使該路線能走遍網絡中的每一條邊（edge）至少一次，並回到起始頂點。
背後的邏輯
想像一個圖，其中每個頂點的度數（degree）皆為偶數（即連接到該點的邊數為偶數）。這被稱為歐拉圖（Eulerian graph）。在這些圖中，你可以走遍每一條邊剛好一次，最後回到起點。這樣一切都很簡單！
然而，大多數真實世界的地圖都包含奇點（odd nodes）（即連接邊數為奇數的頂點）。為了完成路線，你必須重複走過某些邊。
逐步演算法（適用於最多 4 個奇點的情況）
- 找出奇點：檢查每一個頂點，計算有多少條邊與其相連。列出所有計數為奇數的頂點。
- 識別配對方式：如果你有兩個奇點（A 和 B），只有一種配對方式：AB。如果你有四個奇點（A、B、C、D），則有三種可能的配對方式：
- AB 和 CD
- AC 和 BD
- AD 和 BC
- 尋找最短路徑：計算每一對配對中兩點之間的最短距離。
- 選擇最小值：選擇總權重最低的配對方案。
- 計算最終路線：總長度 = (網絡中所有邊的總和) + (最短配對方案的權重)。
小貼士：如果一開始覺得很棘手，別擔心！只要記住：問題出在奇點。我們透過重複走過它們之間的最短路徑，直到它們在效果上變成偶數，就能「修復」這些奇點。
常見錯誤：忘記將重複路徑的權重加回到圖中所有邊的總和中。務必再次檢查你的加法計算！
重點總結：路線檢查問題的核心是走遍每一條邊。為了將距離最小化，我們重複計算奇點對之間的最短路徑。
2. 旅行推銷員問題 (TSP)
與想要走遍每條街道的郵差不同，旅行推銷員只在乎走遍每一個頂點（城市/住戶）並回到起點，且路徑總長度最短。
傳統 TSP 與 實用 TSP
- 傳統 TSP：每個頂點都直接與其他所有頂點相連（稱為完全圖/完備圖, complete graph），且距離滿足三角不等式（直接路徑永遠是最短的）。
- 實用 TSP：並非所有節點都直接相連。為了解決這個問題，我們會先透過找出每對節點間的最短「距離」路徑，將其轉換為完全圖。
你知道嗎？TSP 在電腦科學中是一個「困難」問題。隨著城市數量增加，可能的路徑數量會以驚人的速度增長，即便世界上最強大的電腦也難以快速找出完美答案！
3. 尋找上下界
由於找出 TSP 的精確最短路徑非常困難，我們轉而尋找答案所在的「範圍」。這個範圍由下界（Lower Bound）和上界（Upper Bound）定義。
上界（「夠好」的路線）
上界是一個我們確定可以達到的距離。它可能不是最好的，但它是一條可行的路線。我們通常使用最近鄰點演算法（Nearest Neighbour Algorithm）：
- 選擇一個起始頂點。
- 前往距離最近且尚未造訪過的頂點。
- 重複上述步驟，直到所有頂點都已造訪。
- 回到起點。
注意：你也可以透過在加倍的最小生成樹（Minimum Spanning Tree）上使用「捷徑」來改善上界。
下界（「最理想」的情境）
下界是一個最佳路線不可能比其更短的值。我們使用MST 方法（最小生成樹法）：
- 刪除一個節點：選擇一個頂點（例如頂點 A），暫時刪除它以及所有與其相連的邊。
- 找出 MST：為剩餘的節點找出最小生成樹（使用 Prim's 或 Kruskal's 演算法）。
- 重新連接：加入連接到已刪除頂點 A 的兩條最短邊的權重。
- 總計：下界 = (MST 的權重) + (連接到頂點 A 的兩條最短邊)。
類比：把下界想像成房間的地板，上界想像成天花板。實際的最佳路線就在兩者之間！
複習小視窗：
- 最近鄰點演算法得出上界。
- 刪除節點 + MST + 兩條最短邊得出下界。
4. 轉換為完全網絡
有時，題目給出的網絡不是「完全」的（某些城市之間沒有直接連接）。要應用 TSP 演算法，你必須先建立一個最短距離表。
這意味著如果你想從 A 到 C，但沒有直接的邊，你可能會發現從 A → B → C 是最短路徑。接著，你就將 A 到 C 的距離視為這兩段步驟的總和。
重點總結：對於 TSP，我們尋找的是哈密頓迴路（Hamiltonian Cycle，走遍每個頂點一次並回到起點）。我們使用界限來縮小可能的最小距離範圍。
檢查清單
✓ 路線檢查：我是否找出了所有奇點以及最便宜的配對方式？
✓ 最近鄰點法：我是否總是選擇最近且未造訪過的節點？
✓ 下界：我是否記得將兩條最短邊加回到 MST 中？
✓ 準確性：我是否正確讀取了表格/矩陣？（這是失分最常見的原因！）
你一定沒問題的！決策數學的關鍵在於細心地遵循步驟。持續練習配對和 MST 方法，很快你就會成為這方面的高手！