簡介：規劃決策之路

歡迎來到充滿挑戰的圖論演算法 (Algorithms on Graphs) 世界！這一章是決策數學的核心。雖然「圖」看起來只是簡單的圖表，但我們在這裡學習的演算法卻是導航系統 (如 GPS)、物流管理、網絡規劃和社交媒體連接背後的基本工具。

簡單來說，演算法就是一組為了解決特定問題而設計的步驟。 在這一章中，我們將學習兩類主要問題：尋找兩點之間的最短路徑，以及尋找連接所有點的最經濟方案。

如果剛開始覺得有些棘手，不用擔心；我們會將每個過程拆解成簡單的步驟。要熟練掌握這些技巧，關鍵在於有條理的思考並仔細記錄你的工作步驟。

快速溫習：圖論術語 (前置知識)

  • 節點 (Node 或 Vertex)： 圖上的一個點 (例如：城市、路口)。
  • 邊 (Edge 或 Arc)： 連接兩個節點的線 (例如：道路、管道)。
  • 權重 (Weight)： 與邊相關的數值 (例如：距離、時間、成本)。
  • 網絡 (Network)： 一種邊帶有權重的圖。
  • 路徑 (Path)： 沿著邊所走的路線。
  • 樹 (Tree)： 一種連通且沒有環 (迴路) 的圖。

第一節：尋找最短路徑 - Dijkstra 演算法

Dijkstra 演算法的目標

Dijkstra 演算法用於找出從起點節點到網絡中每一個其他節點的最短 (或最快、最便宜) 路徑。

類比：這就像從中央倉庫 (起點節點) 出發，規劃一條送貨路線，確保能以最快方式到達市內每一位客戶手中。

Dijkstra 演算法的分步指南

該演算法為每個節點使用兩種類型的標籤：

  1. 永久標籤 (Permanent Labels)： 到該節點目前為止確定的最短距離。一旦成為永久標籤 (或被「圈起來」)，它就不會再改變。
  2. 臨時標籤 (Temporary Labels)： 通過某條潛在路徑計算出的距離。如果發現了更短的路徑，這些標籤可以更新 (擦掉並替換)。

步驟流程：

  1. 開始： 為起點節點加上一個永久標籤 \(0\)，並將這個數字圈起來。
  2. 掃描： 查看所有與剛被圈起來的節點直接相連且尚未被圈起來的節點。
  3. 計算臨時標籤： 對於每個相連且未圈起的節點，計算其通過目前被圈起來的節點到達起點的距離：
    • 新標籤 = (當前節點的永久標籤) + (連接邊的權重)
    如果計算出的新距離比節點現有的臨時標籤短 (或者該節點尚未有標籤)，則用新標籤替換舊標籤。
  4. 選擇並圈選： 在網絡中所有未被圈起來的節點中，選擇最小的臨時標籤，並將其轉為永久標籤 (圈起來)。
  5. 重複： 重複步驟 2 至 4，直到目的地節點 (或所有節點) 都獲得了永久標籤。

如何追溯最短路徑

完成演算法後，若要找出從起點到特定目的地節點的實際路徑，必須從目的地反向推導：

  • 從目的地節點開始。
  • 查看其被圈起來的標籤 \(L\)。尋找一個前導節點 \(P\)，使得 \((\text{節點 } P \text{ 的標籤}) + (\text{邊 } P \to D \text{ 的權重}) = L\)。
  • 最短路徑僅包含那些其權重貢獻了永久標籤總和的邊。

⚠ 應避免的常見錯誤

一個非常常見的錯誤是僅僅根據起點節點來計算臨時標籤。請記住，必須始終根據最近被圈起來的節點來更新臨時標籤。此外，一旦標籤變為永久 (被圈起來)，你可以用它來掃描其他點，但其數值本身不可再更改。

Dijkstra 的重點小貼士： Dijkstra 的方法是通過不斷地將當前可用的最短路徑永久化，從而逐步向外找出最短路徑。


第二節：連接所有節點 - 最小生成樹 (MST)

什麼是生成樹？

想像你有幾個地點 (節點) 需要用電纜或道路 (邊) 連接起來。生成樹 (Spanning Tree) 是一組連接網絡中所有節點的邊的集合，它使用的邊數量最少，且關鍵在於不會形成任何環 (迴路)。

什麼是最小生成樹 (MST)？

最小生成樹 (Minimum Spanning Tree, MST) 是指所有邊的總權重之和為最小的生成樹。

類比：如果你要在幾個城鎮之間建立電話網絡，你希望確保每個城鎮都連通，但同時要最小化舖設電纜的總長度 (即成本)。

我們使用兩種強大的演算法來尋找 MST：Prim 演算法和 Kruskal 演算法。它們最終得到的最小總權重是一樣的，但切入問題的角度不同。


第三節：Prim 演算法 (節點導向方法)

Prim 演算法通過從一個起點節點開始向外擴展來構建 MST，這是一種節點導向 (node-based) 的方法。

記憶法：P 代表 Prim's，P 也代表 Proximity (鄰近) —— 我們總是選擇距離當前生成樹最近的邊。

方法 1：在圖表上執行 Prim 演算法

步驟流程：

  1. 開始： 選擇任何一個節點作為起點，將該節點標記為「已在樹中」(通常可以通過高亮顯示節點或相連的邊來標記)。
  2. 掃描： 查看所有與已在樹中的節點相連的邊。
  3. 選擇： 從這些掃描到的邊中選擇權重最小的一條，並確保這條邊連接到一個尚未在樹中的節點。
  4. 加入： 將這條最小權重的邊以及它所連接的新節點加入樹中。
  5. 重複： 重複步驟 2 至 4，直到所有節點都包含在樹中。
  6. 總權重： 將所有選擇的邊的權重相加，即得到最小總權重。

⚠ Prim 的關鍵規則

你只能考慮與已經選擇的節點相連的邊。一旦某條邊會與樹中已有的邊形成環，你必須忽略它，即使它的權重是最小的。

方法 2：使用矩陣 (表格) 執行 Prim 演算法

當網絡較複雜時，使用成本矩陣進行 Prim 演算法會非常高效。

  1. 開始： 選擇一個起始行/節點 (例如：節點 A)。將該行標記為「已訪問」(例如：劃掉該行)。
  2. 掃描行： 查看所選行，找出最小的非零數值。高亮該數值並記錄下對應的邊。
  3. 選擇列： 你所高亮的數值對應一個新節點 (列標題)。劃掉該新節點對應的行和列。
  4. 重新掃描： 現在，僅查看尚未被劃掉的節點列。在所有活躍行 (已在樹中的節點行) 中找出權重最小的值。
  5. 重複： 持續選擇最小且未被劃掉的值，直到選出 \(n-1\) 條邊 (其中 \(n\) 為節點數量)。

Prim 的重點小貼士： Prim 演算法是一種貪婪的局部化方法，它總是從目前已連接到樹中的節點中，選擇最便宜的邊。


第四節：Kruskal 演算法 (邊導向方法)

Kruskal 演算法通過查看整個網絡並根據邊的權重進行選擇來構建 MST，而不考慮它們的位置，前提是所選的邊不能構成環。

記憶法：K 代表 Kruskal's，K 也代表 Kicking out Cycles (踢走迴路)。這個演算法的核心是按順序選擇邊，並拒絕任何會構成閉合迴路的邊。

Kruskal 演算法的步驟流程

  1. 列出並排序： 列出網絡中所有的邊，並按權重從小到大進行排序。
  2. 選擇邊： 沿著排序後的列表向下，逐一選擇邊。
  3. 檢查迴路： 在選擇一條邊之前，先檢查加入它是否會與已選的邊構成迴路 (閉合圈)。
    • 如果該邊不會構成迴路，則選擇它 (加入 MST)。
    • 如果該邊會構成迴路，則拒絕它，並移動到列表中的下一條邊。
  4. 結束條件： 當選出了 \(n-1\) 條邊後停止，其中 \(n\) 為網絡中節點的總數。此時所有節點必須是連通的。
  5. 總權重： 將所有選擇的邊的權重相加。

Kruskal 選擇範例

想像你的列表開頭是：邊 AB (權重 2), 邊 CD (權重 3), 邊 AC (權重 4), 邊 BC (權重 5)...

1. 選擇 AB (2)。樹開始建立。

2. 選擇 CD (3)。可以，它與 AB 不相連。

3. 選擇 AC (4)。可以，連接了 A 和 C。

4. 考慮 BC (5)。如果選擇 BC，會形成迴路：A-B-C-A。因此，拒絕邊 BC。

比較：Prim 演算法 vs. Kruskal 演算法

兩種演算法都能達到相同的結果 (MST)，但在實際應用中：

  • 若網絡以矩陣 (距離表) 形式呈現，Prim 演算法通常較容易使用。
  • 若網絡以長邊列表形式呈現，Kruskal 演算法通常較容易使用。

Kruskal 的重點小貼士： Kruskal 演算法追求的是全局優化。先將所有邊排序，再根據成本逐一添加，過程中務必嚴格檢查，確保從未形成閉合迴路。


總結與鼓勵

恭喜！你已經掌握了決策數學 1 的三大基礎演算法：

  1. Dijkstra 演算法： 找出從一個節點到所有其他節點的最短路徑 (節點-永久標籤法)。
  2. Prim 演算法： 通過增加最接近的未訪問節點來建立最小生成樹 (節點導向)。
  3. Kruskal 演算法： 通過按成本順序選擇邊來建立最小生成樹，同時避免迴路 (邊導向)。

本章成功的關鍵在於練習。每個演算法都是一個結構化的程序。堅持按照步驟操作，在標記和檢查時保持嚴謹，你一定能精通這些重要的技巧！


你知道嗎？

Edsger Dijkstra 於 1956 年與妻子喝咖啡時發明了他的最短路徑演算法，並且僅用了約 20 分鐘就解決了這個問題！這說明了即使是最著名的演算法，也能從簡單的邏輯步驟中推導出來。