網絡算法簡介
歡迎來到網絡算法的世界！本章屬於你離散數學課程的一部分。試想像你正嘗試使用 Google Maps 找出前往學校的最快路線，或者身為工程師，正試圖以最少的物料將多個城鎮連接起來。這些都是現實生活中典型的「網絡」問題。
在本章中，我們將學習如何使用特定的分步規則——即算法 (algorithms)——來有效地解決這些問題。剛開始看到步驟很多別擔心；只要掌握當中的模式，這其實就像跟著食譜做菜一樣簡單！
1. 最短路徑：Dijkstra 算法
這裡的目標很簡單：找出網絡中兩點（頂點）之間權重最小的路徑（通常指最短距離或最低成本）。
Dijkstra 算法運作原理
你可以把它想像成一次「受控的爆炸」。我們從起點開始，慢慢地為附近的點標記上它們距離起點的長度，直到抵達目的地為止。
分步流程：
- 為起始頂點加上一個永久標記 (permanent label)，數值為 0。
- 從你剛剛設定為永久標記的頂點開始，觀察所有與之相鄰 (adjacent)（相連）且尚未擁有永久標記的頂點。
- 計算這些鄰點的工作值 (working values)（暫時距離）：\( \text{新數值} = \text{當前永久標記頂點的數值} + \text{邊的權重} \)。
- 如果計算出的新數值比之前的工作值小，則更新它。
- 在整個網絡中，找出具有最小工作值的頂點，並將其設為新的永久標記。
- 重複此過程，直到目的地頂點獲得永久標記為止。
快速回顧： 標記通常包含三個部分：頂點名稱、變為永久標記的順序，以及最終距離。
效率（階數）： Dijkstra 算法具有平方階 (quadratic order)，表示為 \( O(V^2) \)，其中 \( V \) 是頂點的數量。這意味著如果城鎮數量增加一倍，電腦計算所需的時間可能會增加四倍！
常見錯誤提醒： 下一次設定永久標記時，務必從整個網絡中挑選最小的工作值，而不僅僅是與當前點直接相連的那些點！
重點總結
Dijkstra 算法是處理加權網絡中尋找兩點之間絕對最短路徑的首選工具。
2. 最小生成樹 (Minimum Spanning Trees, MST)
有時候，我們的目標不僅是從 A 到 B，而是要將網絡中的每一個點連接起來，並確保總邊權重最小。這被稱為最小連接器 (Minimum Connector) 或最小生成樹 (Minimum Spanning Tree)。
Prim 算法
Prim 算法是「基於頂點」的。你從一個點出發，像植物生長一樣擴展你的樹，過程中總是添加連接到新點且最便宜的分支。
- 圖形法： 選擇一個起始頂點。添加連接到它的最短邊。現在，觀察所有從已擁有的頂點連接到尚未擁有的頂點的邊，選出最短的一條。重複此步驟！
- 列表/矩陣法： 如果題目給出距離表，你可以刪除已選行的數值，並在「已連接」頂點的列中尋找最小值。
Kruskal 算法
Kruskal 算法是「基於邊」的。它甚至更簡單，但需要小心避免出現「迴路 (cycles)」（封閉路徑）。
- 將網絡中所有的邊按長度由短到長排序。
- 挑選最短的邊。
- 挑選下一條最短的邊。如果它會形成迴路（形成閉環），則放棄並跳至下一條。
- 重複此過程，直到所有頂點都被連接起來。
記憶小撇步： Prim 從一個點 (Point) 開始。Kruskal 從一個邊的目錄 (Katalog/List) 開始。
效率： Prim 和 Kruskal 算法都具有立方階 (cubic order)，即 \( O(V^3) \)。對於電腦而言，它們比 Dijkstra 算法稍微「沉重」一點。
重點總結
使用 Prim 或 Kruskal 算法來以最小總權重連接所有節點。Prim 從一點向外生長；Kruskal 從列表中挑選最優邊。
3. 旅行推銷員問題 (Travelling Salesperson Problem, TSP)
在這個問題中，推銷員必須訪問每一個頂點並回到起點，同時最小化總距離。這比 MST 要困難得多，因為我們必須遵循特定的「回路 (cycle)」。
由於對於大型網絡來說，「完美」答案非常難以尋找，我們通常會找出答案所在的範圍（界限）。
上限：最近鄰居法 (Nearest Neighbour Method)
這是一種「貪婪」的方法。從某個頂點開始，總是前往尚未訪問過的最近頂點。當所有點都訪問完後，直接回到起點。
小知識： 如果網絡不是「完全圖」（即並非每個城鎮都有直接通往其他城鎮的路），這種方法可能會「卡住」。你可能需要走更遠的路才能到達遙遠的城鎮或回到家。
下限：MST 方法
要找到下限（我們知道真實答案必然大於或等於的值）：
- 「刪除」一個頂點及其所有相連的邊。
- 找出剩餘頂點的最小生成樹 (MST)。
- 加上被刪除頂點原先連接的兩條最短邊的權重。
- 結果即為一個下限。針對不同的刪除頂點重複此步驟會得到不同的界限；其中最高的數值即為最有用的「最佳」下限。
重點總結
最近鄰居法給出一個上限（一個「足夠好」的路線）。刪除頂點 + MST 方法給出一個下限（數學上的成本「地板」）。
4. 路線檢查：中國郵差問題 (Route Inspection: The Chinese Postman Problem)
想像一位郵差需要走遍社區內的每一條街道（邊）至少一次，並回到郵局。為了高效，他希望將必須重複行走的距離最小化。
度數規則 (Rule of Degrees)
如果網絡中每個頂點的度數都是偶數（匯集在該點的邊的數量為偶數），郵差可以將每一條邊恰好走一遍。這是一個歐拉 (Eulerian) 回路。
如果有奇數點（度數為奇數的頂點），郵差就必須重複走某些邊。
解決奇數點問題
我們必須將奇數點配對，並找出它們之間的最短路徑來進行「重複行走」。
- 2 個奇數點： 找出它們之間的最短路徑（如有需要可使用 Dijkstra），並將該權重加到所有邊的總和中。
- 4 個奇數點： 有 3 種配對方式。例如，若點為 A、B、C、D，你可以配成 (AB, CD)、(AC, BD) 或 (AD, BC)。計算每種配對的「額外」權重總和，並選擇最小的那一組。
- 6 個奇數點： 這會變得更複雜！共有 15 種可能的配對。
重要公式： 對於 \( 2n \) 個奇數點，配對數量為： \( 1 \times 3 \times 5 \times ... \times (2n - 1) \)。
例子： 對於 4 個奇數點 (\( n=2 \))，公式為 \( 1 \times 3 = 3 \) 種配對。對於 6 個奇數點 (\( n=3 \))，則為 \( 1 \times 3 \times 5 = 15 \) 種配對。
重點總結
路線檢查問題的關鍵在於透過重複奇數點對之間的最短路徑，使所有節點都變成「偶數點」。
最終快速回顧箱
Dijkstra： 兩點間的最短路徑。\( O(V^2) \)。
Prim/Kruskal： 連接所有點的最短方式。\( O(V^3) \)。
最近鄰居法： 尋找巡迴 (TSP) 的上限。
縮減網絡上的 MST： 尋找巡迴 (TSP) 的下限。
路線檢查： 遍歷每一條邊；將奇數點兩兩配對。
如果剛開始覺得有點難，別擔心！ 學習這些算法最好的方法就是拿張紙，畫一個小網絡，親自按照算法步驟動手畫一遍。你一定可以做到的！