歡迎來到圖論演算法 II！
在之前的學習中，你已經學過如何找出兩點之間的最短路徑，或是如何以最少的線纜連接所有點。在這個章節，我們要進一步探討更複雜的應用——規劃現實生活中的最佳路徑，例如郵差如何將信件送到街上的每一戶人家，或是推銷員如何走訪多個城市。
這些演算法是現代物流業的基石，像 Amazon 和 FedEx 這樣的公司每天都在使用。如果剛開始覺得這些概念有點抽象，不用擔心！我們會透過簡單的類比，一步步為你拆解！
1. 路線檢查演算法 (Route Inspection Algorithm)
這個演算法又稱為中國郵差問題 (Chinese Postman Problem)，其核心在於找出最短的路線，使該路線能夠走遍每一條邊 (edge) 至少一次，並回到起點。
核心概念：偶點與奇點
在開始之前，請記得一個節點的度數 (degree) 或稱價數 (valency)，是指與該節點相連的邊的數量。
- 偶點 (Even Node)：相連的邊數為偶數 (2, 4, 6...)。
- 奇點 (Odd Node)：相連的邊數為奇數 (1, 3, 5...)。
黃金法則：如果網絡中的所有節點皆為偶點，你便可以走遍每一條邊恰好一次，並回到起點。這稱為歐拉迴路 (Eulerian circuit)。此時的總距離即為網絡中所有權重之和。
如果出現奇點怎麼辦？
如果有奇點存在，你必須重複經過某些邊。因為我們追求「最短」路線，所以我們希望重複經過的邊其總權重越小越好。在考試中，你通常會處理含有兩個或四個奇點的網絡。
步驟拆解：檢查過程
- 找出所有度數為奇數的節點。
- 列出這些奇點所有可能的配對方式。
- 計算每一組配對中，節點之間的最短路徑。
- 選擇總權重最小的那一組配對。
- 將這個最小權重加入網絡中所有邊的總權重。這就是你的最終答案！
4 個奇點 (A, B, C, D) 的範例：
配對方式只有三種：
1. (AB 和 CD)
2. (AC 和 BD)
3. (AD 和 BC)
小撇步：只需固定一個點（例如 A），將它與其他所有點配對，剩下的兩個點會自動形成第二個配對！
重點複習：
- 歐拉圖 (Eulerian)：所有節點皆為偶點。
- 半歐拉圖 (Semi-Eulerian)：有兩個奇點（你將從其中一個起點開始，並在另一個終點結束）。
- 路線檢查：重複經過奇點之間的邊，使路線「有效」變為偶點圖。
2. 旅行推銷員問題 (Travelling Salesman Problem, TSP)
郵差問題是要走遍每一條邊，而旅行推銷員則是要走遍每一個頂點 (vertex) 恰好一次並回到起點。這個問題比前者困難得多！
TSP 的兩種分類
- 經典 TSP：必須走訪每個頂點且不可重複。這通常適用於完全圖 (complete graphs)。
- 實用 TSP：如果重複經過某些頂點能讓總行程更短，則允許重複。我們會透過最短距離表 (table of least distances) 將「實用」問題轉化為「經典」問題來處理。
三角不等式 (Triangle Inequality)
這是一個說明「直線距離最短」的華麗說法。正式定義為：
\( \text{Length } AB \leq \text{Length } AC + \text{Length } CB \)
如果網絡中所有節點皆符合此條件，兩點之間的最短路徑永遠是連接它們的那條邊。
3. 尋找上限 (Upper Bound)
由於 TSP 非常困難，我們通常會尋找一個上限 (Upper Bound)——也就是我們確定可以達成的「足夠好」的路線。主要有兩種方法。
方法 A：最近鄰居演算法 (Nearest Neighbour Algorithm)
這是一個「貪婪」演算法，就像一個懶惰的購物者，總是只去最近的下一家店。
- 選擇一個起點。
- 前往距離最近且尚未造訪的節點。
- 重複此動作直到造訪所有頂點。
- 關鍵步驟：最後必須回到起點！
常見錯誤：學生常忘記最後一步——加上從最後一個節點回到起點的距離。
方法 B：最小生成樹 (MST) x 2
1. 找出整個網絡的 MST（使用 Prim’s 或 Kruskal’s 演算法）。
2. 將 MST 的權重加倍。這是初始的上限。
3. 尋找捷徑（利用最短距離表）來減少權重，以找到更好的上限。
小知識：「上限」是我們願意支付行程的最大值。我們一直在尋找降低這個數值的方法！
4. 尋找下限 (Lower Bound)
下限 (Lower Bound) 是一個值，代表我們能找到的最優路徑不可能短於這個值。它告訴我們：「這趟旅程的時間/距離絕對不可能少於這個數字。」
刪除頂點法 (Deleted Vertex Method)
- 刪除一個頂點以及所有與其相連的邊。
- 找出剩餘節點的最小生成樹 (MST)。
- 找出原先與被刪除頂點相連的兩條最短邊。
- 下限 = (MST 的權重) + (兩條最短邊之和)。
如果覺得複雜也不用擔心！只要記住：下限不一定必須是一條可行的完整路線（它看起來常像「Y」字型，而非封閉的圓圈）。它的功用只是為我們的預期提供一個最低底線。
總結摘要：
- 上限：一條我們「做得到」的路線（通常由最近鄰居法得出）。
- 下限：一條我們「無法超越」的數值（由刪除頂點法得出）。
- 最佳解就在兩者之間！
5. 最終總結與常見陷阱
關鍵術語複習：
- 路徑 (Walk)：邊的序列。
- 巡迴 (Tour)：走訪每一個頂點並回到起點的路線。
- 捷徑 (Shortcuts)：在 TSP 中用來跳過已造訪的頂點，以改善上限。
常見錯誤：
- 路線檢查：忘記將「額外」重複的邊加回圖的原始總權重中。
- 最近鄰居法：忘記加上最後回到起點的那條邊。
- 下限計算：從整個圖中選擇兩條最短邊，而不是選擇與被刪除的頂點相連的兩條最短邊。
繼續練習這些步驟吧！決策數學的核心就是完美地遵循「食譜」（演算法）。你一定做得到的！