匈牙利演算法原理圖解：教授指派課程問題的完整步驟演示

前言

本文以「四位教授指派四門課程，最小化總準備時間」為例，完整圖解匈牙利演算法 Step 1 與 Step 2 的手工執行過程，建立演算法直觀理解。

問題定義

目標：每位教授指派一門不同課程，總成本最小。

Step 1：列縮減 → 行縮減

1.1 各列 (教授) 減去該列最小值

教授A: min=2  → 0   8   7   5
教授B: min=4  → 11  0   10  4
教授C: min=11 → 2   3   5   0
教授D: min=4  → 0   11  9   5

1.2 各行 (課程) 減去該行最小值

課程1: min=0  → 0   11  2   0
課程2: min=0  → 8   0   3   11
課程3: min=5  → 2   5   0   4  (7-5, 10-5, 5-5, 9-5)
課程4: min=0  → 5   4   0   5

Step 1 完成矩陣

     課1  課2  課3  課4
教A   0    8    2    5
教B   11   0    5    4
教C   2    3    0    0
教D   0    11   4    5

Step 2：嘗試完全指派 (標記獨立零)

規則

1. 掃描各行，找到第一個零標記為 ★ (指派)
2. 同行、同列其他零標記為 × (排除)
3. 優先處理零較少的行

執行過程

1. 第 1 行 (教A)：唯一零在 (0,0) → ★，同列 (2,0)、(3,0) 標 ×
2. 第 2 行 (教B)：唯一零在 (1,1) → ★，同列無其他零
3. 第 3 行 (教C)：有兩個零 (2,2)、(2,3) → 選第一個 (2,2) ★，同列 (3,2) 標 ×
4. 第 4 行 (教D)：第 0 列已被佔用 (×)，第 3 列已被佔用 (×)，無可用零 → 指派失敗

Step 2 結束狀態

     課1  課2  課3  課4
教A   ★    8    2    5
教B   11   ★    5    4
教C   2    3    ★    ×
教D   ×    11   ×    5

僅找到 3 個獨立零 (< 4)，需進入 Step 3 (覆蓋零) 與 Step 4 (調整矩陣)。

後續步驟預告 (參考前文完整代碼)

• Step 3：用最少線覆蓋所有零 (本例需 3 條線)
• Step 4：找未覆蓋最小值 K=2，未覆蓋行減 2，覆蓋列加 2
• 回 Step 2：新矩陣可找到 4 個獨立零，完成最佳指派

教學重點總結

1. 縮減不改變最優解：每行/列減去常數，總成本僅差常數項，最優指派不變。
2. 零代表「零機會成本」：縮減後為零的格子，代表該指派在當前矩陣下無額外成本。
3. 獨立零集合 = 可行指派：N 個互不相同行列的零即為一個完整指派方案。
4. 覆蓋線數 < N 代表尚未最優：需調整矩陣製造更多零，直到能選出 N 個獨立零。

總結

本文詳細演示了匈牙利演算法前兩步在 4×4 教授指派問題上的手工執行過程。Step 1 透過雙重縮減建立零元素基礎，Step 2 嘗試貪婪選取獨立零，失敗則觸發 Step 3/4 迭代優化。理解此過程是掌握指派問題最佳化求解的核心基礎。