圖論演算法：Further Maths 決策數學指南

你好！歡迎來到決策數學 1 (D1) 的精彩世界。這一章「圖論演算法」或許是 Further Maths 中最實用且直觀的部分。它的核心在於尋找最高效的解決方案——例如最便宜的連接方式、最快的路徑，或是最短的派遞路線。

如果「演算法」聽起來很複雜，別擔心。演算法其實就是一組用於解決特定問題的步驟。你可以把它想像成數學上的「食譜」！讀完這份筆記後，你就能像專業的物流經理和網絡工程師一樣，解決現實中的效率問題。

第一節：網絡基礎（圖論）

在我們執行演算法之前，必須先理解圖論的術語。

什麼是圖（Graph）？

圖（或網絡）由點和連接這些點的線組成。

  • 節點（Nodes）（或頂點 Vertices）：圖中的點。（例如：城市、路口、電腦伺服器）。
  • 弧（Arcs）（或邊 Edges）：連接節點的線。（例如：道路、電纜、航班）。
  • 權重（Weights）：分配給弧的數值，通常代表距離、成本、時間或容量。

關鍵術語

  • 路徑（Path）：從一個節點到另一個節點，沿著弧移動的路線。
  • 圈（Cycle）（或迴路 Circuit）：起點和終點相同的路徑。
  • 節點的度（Degree / Order）：連接到該節點的弧的數量。
  • 連通圖（Connected Graph）：圖中任意兩個節點之間都能通過路徑到達。
  • 簡單圖（Simple Graph）：沒有環（弧的起點和終點相同）且任意兩個節點之間沒有多條弧的圖。
  • 有向圖（Directed Graph / Digraph）：弧具有方向性的圖，表示只能向特定方向行駛（例如：單行道）。

快速回顧：圖只是連接關係的圖示，而權重則告訴我們這些連接有多「昂貴」。

第二節：最小生成樹（Minimum Spanning Trees, MSTs）

想像你正用最便宜的光纖電纜連接五棟辦公大樓。你需要連接所有大樓，但不能有任何多餘的迴路（圈）。這就是 MST 發揮作用的地方。

生成樹（Spanning Tree）是一個連接所有節點且不形成任何圈的子圖。最小生成樹（MST）則是總權重最小的生成樹。

演算法 2.1：克魯斯克爾演算法（Kruskal’s Algorithm，最便宜優先法）

Kruskal 演算法屬於貪婪演算法——它在每一步都專注於選擇當時最便宜的弧。

目標：按照權重遞增的順序添加弧來建立樹，同時確保不會產生圈。

Kruskal 演算法步驟
  1. 將網絡中所有的弧按權重從小到大列出。
  2. 從權重最小的弧開始，選擇它並加入你的樹中。
  3. 查看下一個最小權重的弧，如果它與你已經選擇的弧不會構成圈，則將其加入。
  4. 重複步驟 3，直到所有節點都被連接起來。

常見錯誤提醒！ Kruskal 的絕對原則是：絕對不能構成圈！ 如果添加一條弧會連接兩個已經在當前樹中透過路徑連接的節點，請拒絕這條弧。

Kruskal 重點：從哪裡開始都可以，按權重順序處理，並避開迴路。

演算法 2.2：普林演算法（Prim’s Algorithm，生長樹法）

Prim 演算法同樣是貪婪的，但它專注於從一個起始點向外「生長」樹。

目標：從一個節點開始，持續連接離當前樹最近的未連接節點。

Prim 演算法（網絡法 - 可視化）
  1. 從任意節點開始（選哪個都行，但通常選 A），將其標記為「在樹中」。
  2. 查看所有連接「樹內」節點到「樹外」節點的弧。
  3. 在這些選項中選擇權重最小的弧。
  4. 將選定的弧和新的節點加入樹中。
  5. 重複步驟 2-4，直到所有節點都包含在樹中。
Prim 演算法（矩陣法）

當圖以距離矩陣形式給出時，此方法非常有用。

  1. 選擇任意行/列（例如 A），將該列標記為「已包含」。
  2. 在已包含的行/列中，找到最小的非零數值，這是第一條弧。
  3. 圈出該數值並劃掉對應的行（它現在已成為樹的一部分）。
  4. 新加入的節點決定了你下一個要包含的列。
  5. 重複步驟 2-4，直到選擇了 \(n-1\) 條弧（\(n\) 為節點總數）。

類比：如果 Kruskal 像是工程隊在全國範圍內尋找最便宜的道路，Prim 則像是一個施工團隊從基地向外擴展建設工地。

第三節：最短路徑 – 戴克斯特拉演算法（Dijkstra’s Algorithm）

最小生成樹是為了便宜地連接所有節點，而 Dijkstra 演算法解決的是另一個問題：在兩個特定點（起點和終點）之間尋找最快、最短或最便宜的路線。

Dijkstra 演算法透過系統地為節點分配和更新標籤（距離），直到確定最短路徑為止。

Dijkstra 的關鍵概念

  • 標籤（Labeling）：我們為每個節點分配標籤 \((d, p)\)，其中 \(d\) 是從起點開始的距離，\(p\) 是到達 \(d\) 前的一個節點。
  • 暫時性標籤（Temporary Labels）：如果發現了更短的路徑，這些標籤可能會改變。
  • 永久性標籤（Permanent Labels）：已經最終確定為到達該節點的最短距離。一旦標籤成為永久性，就絕不再更改。
Dijkstra 演算法步驟
  1. 起點：為起點分配一個永久性標籤 \((0, -)\)。所有其他節點初始標籤設為暫時性，通常記為 \((\infty, -)\) 或留空。
  2. 掃描節點：選擇具有最小距離值 (\(d\)) 的永久性標籤節點。這就是你目前「身處」的節點。
  3. 更新鄰居：查看所有連接到當前節點的暫時性節點。計算潛在的總距離（當前永久距離 + 弧權重）。
  4. 重新標記：如果新的總距離小於該節點當前的暫時性距離，則用新距離更新標籤，並將當前節點設為前一個節點。
  5. 設定永久性：掃描完當前的永久性節點後，查看剩餘的所有暫時性標籤。選擇距離最小的一個並將其設為永久性（圈出該標籤）。
  6. 重複：回到步驟 2，掃描新產生的永久性節點，直到終點節點變為永久性為止。

記憶小撇步：永遠尋找最小的暫時性標籤來設為下一個永久性標籤。這非常關鍵！

常見錯誤提醒！ 學生常會忘記在過程後期發現更短路徑時更新暫時性標籤。一定要將潛在的新路徑與現有的暫時性標籤進行比較！

Dijkstra 重點：系統地確定到每個節點的最短路徑，由起點向外逐一進行。

第四節：路線檢查（中國郵差問題 - CPP）

想像一位郵差或掃雪車司機，必須走過每一條街道至少一次並回到起點，同時使行駛的總距離最小化。

中國郵差問題 (CPP) 的要求是找到一條經過網絡中每一條弧的最短閉合路徑（Trail）。

偶數與奇數節點規則

如果圖中每個節點的度數都是偶數（連接的弧數量為偶數），郵差就可以完成路線而無需重複任何弧。總長度即為所有弧權重的總和。

如果有節點的度數是奇數，郵差必須重複某些弧，才能使整個網絡變得可通行（歐拉路徑）。

CPP 解決方案步驟
  1. 找出奇數節點：列出所有度數為奇數的節點。因為弧總是成對出現的，所以奇數節點的總數一定是偶數（2, 4, 6 等）。
  2. 配對奇數節點：必須將奇數節點配對，並找出每對之間的最短路徑。透過重複這些最短路徑中的弧，我們有效地將奇數節點轉變為「偶數」。
  3. 計算最短配對：
    • 如果有 2 個奇數節點（A 和 B），找出 A 和 B 之間的最短路徑。
    • 如果有 4 個奇數節點（A, B, C, D），你必須測試所有三種配對組合：
      (i) (A 配 B) 且 (C 配 D)
      (ii) (A 配 C) 且 (B 配 D)
      (iii) (A 配 D) 且 (B 配 C)
    • 使用 Dijkstra 演算法或直接觀察，找出每種配對的最短路徑長度。
  4. 選擇最小配對：選擇總路徑長度增加最少的組合。
  5. 計算總路線長度：
    總長度 = (原始網絡所有弧權重之和) + (最小增加的路徑長度)。
  6. 列出需重複的弧：列出必須走兩次的弧。

你知道嗎？ 這個演算法是以中國數學家管梅谷（Mei Ko Kwan）命名的，他在 1962 年為了解決郵差的最佳路線問題而開發了此演算法。

CPP 重點：挑戰在於透過增加最少的額外距離，將奇數節點轉變為偶數節點。

第五節：旅行推銷員問題（TSP）

旅行推銷員問題 (TSP) 問的是：走訪每個節點（城市）恰好一次並回到起點的最短路線是什麼？

所要求的路線是一個權重最小的哈密頓迴路 (Hamiltonian Cycle)。

與我們之前研究的演算法不同，目前沒有簡單且保證能快速找到絕對最小解（最佳巡迴）的演算法。對於節點數量龐大的圖，找出最佳解在計算上負擔過重。

因此，我們使用近似方法來找出上限（Upper Bound）（一個我們已知可行的巡迴）和下限（Lower Bound）（我們已知最佳巡迴距離必大於或等於的值）。

近似法 5.1：尋找上限

上限就是任何有效哈密頓迴路的長度。尋找上限最簡單的方法是使用最近鄰點演算法 (Nearest Neighbour Algorithm)。

最近鄰點演算法
  1. 從指定的節點開始（如果沒有指定，可以嘗試所有節點）。
  2. 從當前節點出發，選擇指向最近（尚未訪問）節點的弧。
  3. 重複步驟 2，直到所有節點都已訪問過。
  4. 直接返回起點以完成巡迴。
  5. 此迴路的總權重即為你的上限。

路線調整：有時，進行微小的調整（交換兩條弧）可以縮短路線，從而得到更緊密的（更低的）上限。

近似法 5.2：尋找下限

下限是我們已知最佳巡迴成本必然達到或超過的值。我們使用最小生成樹 (MST) 或刪除節點分析法來尋找下限。

使用最小生成樹 (MST) 尋找下限

如果你從網絡中刪除任意節點及其連接的弧，剩餘的圖仍需透過生成樹連接。這是尋找下限的常用方法。

  1. 選擇任意節點（例如 A）將其「刪除」，並移除所有與它連接的弧。
  2. 使用 Prim 或 Kruskal 演算法為剩餘節點找到最小生成樹 (MST)，並計算其總權重。
  3. 找出原本連接到已刪除節點（A）的兩條最短弧。
  4. 計算下限：
    $$ \text{下限} = (\text{剩餘節點的 MST 權重}) + (\text{連接 A 的兩條最短弧權重}) $$

邏輯：最佳巡迴必須離開 A 並返回 A。它至少要用到兩條連接 A 的弧，並且必須連接其餘節點——連接其餘節點最便宜的方法就是透過 MST。

TSP 重點：由於找到精確答案太困難，我們建立一個範圍（從上限到下限），最佳解必定落在此區間內。

總結檢查清單與學習技巧

掌握演算法
  • MST (Kruskal/Prim)：專注於以低成本連接所有節點，避免迴路。矩陣題用 Prim，快速視覺分類題用 Kruskal。
  • 最短路徑 (Dijkstra)：標籤處理要細心。永遠讓最小的暫時性標籤下一個變成永久性。
  • CPP：找出奇數節點並計算配對它們所需的最小總權重。
  • TSP：理解上限（一個可行的巡迴）與下限（理論最小總權重）之間的區別。

鼓勵的話：決策數學非常講究流程。多練習每個演算法，從簡單的網絡開始，直到處理過程成為你的直覺。你一定沒問題的！