歡迎來到圖論算法 II！
在先前的學習中，你已經學會了如何找出兩個特定點之間的最短路徑（Dijkstra 演算法），以及如何用最少的「電纜」連接所有點（Prim 演算法和 Kruskal 演算法）。現在，我們將進一步探討如何有效率地處理整個網絡的導航問題。
無論是郵差要將郵件送到每一條街道的每一戶人家，還是送貨司機需要在一天內走訪多個不同的城市，這些算法都能幫助我們找到最省時、最省錢的路線。如果一開始覺得步驟很多，別擔心——一旦你看出了當中的規律，這就像是一個邏輯分明的「解謎遊戲」！
1. 路線檢查算法（中國郵差問題）
這裡的目標很簡單：沿著網絡中的每一條邊至少走過一次，並回到起點，同時盡可能保持總距離最短。
理解節點度數 (Node Degrees)
在開始之前，請記住「握手定理」的規則：若一個節點連接了奇數條邊，它就是奇點 (odd node)；若連接了偶數條邊，它就是偶點 (even node)。要實現走遍每一條邊且不重複走過任何邊（即一個歐拉迴路 Eulerian circuit），所有的節點都必須是偶點。
運作過程
如果網絡中存在奇點，我們就必須重複走過某些邊。該算法旨在找出需要重複哪些邊，以增加最小的額外距離。
- 識別網絡中的所有奇點。
- 列出這些奇點的所有可能配對方式 (pairings)。
- 針對每一種配對，找出節點之間的最短路徑。
- 選擇總距離最小的配對方案。
- 將這個最小距離加到原網絡所有邊的總和上。
快速複習：配對規則
在 D1 中，你將處理最多包含四個奇點的網絡。如果你有四個奇點（假設為 A、B、C 和 D），它們恰好有三種配對方式：
1. (AB) 和 (CD)
2. (AC) 和 (BD)
3. (AD) 和 (BC)
常見錯誤：學生經常忘記檢查節點間的「最短路徑」。有時從 A 到 B 的最短距離並非直接連線，而是需要經過另一個節點！
重點總結：路線檢查總長度 = (所有邊的總和) + (配對帶來的最小額外距離)。
2. 旅行推銷員問題 (TSP)
如果說路線檢查問題關注的是邊，那麼 TSP 關注的就是頂點。其目標是訪問每一個頂點恰好一次，並回到起點。
實際問題 vs. 經典 TSP
經典 TSP：你需要訪問每個頂點恰好一次。這通常發生在一個「完全圖」中，即每個節點都直接連接到其他所有節點。
實際 TSP：你必須訪問每個頂點，但如果重複經過某個頂點能讓旅程更短，是被允許的。在這種情況下，我們通常會先將網絡轉換為一個最短距離的完全網絡。
三角不等式 (Triangle Inequality)
聽起來很深奧，但道理很簡單！它指出兩點之間的直接路徑，絕對不會比經過第三點的路徑長。
形式上：\( d(A, C) \le d(A, B) + d(B, C) \)。
如果一個網絡滿足此條件，使用「捷徑」總能節省距離。
你知道嗎？ TSP 被稱為「NP-hard」問題。用計算機科學的術語來說，這意味著對於大規模網絡，電腦要找到絕對完美的答案是非常困難的。這就是為什麼我們需要使用界限 (Bounds)。
3. 尋找上限 (Upper Bound)
上限 (Upper Bound) 是一個「保證可行」的距離。我們知道最佳路線的長度最多就是這個距離。
方法 A：最近鄰居算法 (Nearest Neighbour Algorithm)
這是一種「貪婪」算法——你總是選擇距離當前點最近且尚未訪問過的城市。
- 從指定的頂點出發。
- 前往最近且未訪問過的頂點。
- 重複上述步驟，直到訪問完所有頂點。
- 回到起始頂點。
注意：上限的結果可能會因起始頂點的不同而改變。通常考試會指定你從哪裡開始！
方法 B：最小生成樹加倍法 (Doubling the MST)
- 使用 Prim 或 Kruskal 算法找出最小生成樹 (MST)。
- 將 MST 的權重加倍（這相當於將樹中的每條路徑走兩遍以回到起點）。
- 利用捷徑來避免重複訪問節點，並選擇最短的可用路徑以縮短總距離。
快速複習盒
上限檢查清單：
- 我是否訪問了每一個節點？
- 我是否回到了起點？
- 我的計算正確嗎？（一定要檢查加法！）
4. 尋找下限 (Lower Bound)
下限 (Lower Bound) 是一個保證最佳路線長度至少要達到的數值。實際答案必定大於或等於此距離。
刪除頂點法 (Deleted Vertex Method)
- 刪除其中一個頂點及其所有相連的邊。
- 找出剩餘頂點的最小生成樹 (MST)。
- 找出原先與被刪除頂點相連的兩條最短邊。
- 下限 = (MST 的權重) + (那兩條最短邊的和)。
鼓勵一下：如果你通過刪除不同的頂點計算出不同的下限，數值最高的那一個就是「最好」的下限，因為它對最佳解的限制最準確。
重點總結：我們將這些界限結合起來，為最佳解建立一個區間：
下限 \(\le\) 最佳解 \(\le\) 上限
章節總結與小撇步
- 路線檢查 (Route Inspection)：想著邊。重點在於配對所有的奇點。
- TSP：想著頂點。重點在於上限和下限。
- 記憶小幫手：「最近鄰居 (Nearest Neighbour)」是一個想吃最近零食的貪婪朋友（上限）。「刪除頂點 (Deleted Vertex)」是一個需要地基（MST）和兩根支柱（兩條最短邊）的建築師（下限）。
- 考場攻略：對於路線檢查，務必清晰地展示你的配對過程。對於 TSP，如果題目給你一個表格，確保你尋找的是那些尚未被「劃掉」的數值中最小的數字。
你一定做得到的！只要多練習判斷題目是在問路線檢查（走遍所有路）還是 TSP（走遍所有鎮），剩下的就只是按部就班地執行算法而已！