匈牙利演算法步驟圖解：從矩陣縮減到最佳指派的完整演示

前言

本文以 4×4 成本矩陣為例，逐步圖解匈牙利演算法的四大步驟執行過程，展示矩陣如何從初始狀態經過縮減、覆蓋、調整，最終得到最佳指派方案。

初始成本矩陣

教授\課程  課程1  課程2  課程3  課程4
教授A       2      10     9      7
教授B       15     4      14     8
教授C       13     14     16     11
教授D       4      15     13     9

Step 1：列/行縮減

各列減去最小值

教授A: 0   8   7   5   (減 2)
教授B: 11  0   10  4   (減 4)
教授C: 2   3   5   0   (減 11)
教授D: 0   11  9   5   (減 4)

各行減去最小值

課程1: 0   11  2   0   (減 0)
課程2: 8   0   3   11  (減 0)
課程3: 7   10  5   9   (減 5)
課程4: 5   4   0   5   (減 0)

Step 1 完成矩陣

0   8   2   5
11  0   5   4
2   3   0   0
0   11  4   5

Step 2：嘗試完全指派（標記獨立零）

掃描各行，優先選擇零較少的行：

• 第 1 行：選 (0,0)
• 第 2 行：選 (1,1)
• 第 3 行：有兩個零 (2,2)、(2,3)，選 (2,2)
• 第 4 行：第 0 列已被佔用，無可用零 → 指派失敗

Step 3：最少線覆蓋所有零

貪婪策略：對每個零，比較同行/同列零個數，覆蓋較多者。

覆蓋線標記（紅色）：

[行0] [行1] [行2] [行3]  ← 水平線
[列0] [列1] [列2] [列3]  ← 垂直線

實際覆蓋結果：3 條線（< 4），需進入 Step 4。

Step 4.1：未覆蓋元素減去最小值 K

未覆蓋區域最小值 K = 2。

-2  6   0   3
11  0   5   4
2   3   0   0
0   9   2   3

Step 4.2：負值列加回 K 修正

第 0 列有 -2，整列加 2。

0   6   0   3
13  0   5   4
4   3   0   0
0   9   2   3

回 Step 2：重新嘗試指派

新矩陣可找到 4 個獨立零：

(0,0), (1,1), (2,2), (3,3) → 完全指派成功！

最終指派方案與總成本

總最小準備時間 = 2 + 4 + 11 + 4 = 21

流程圖總結

初始矩陣
    ↓ Step 1: 列/行縮減
縮減矩陣
    ↓ Step 2: 嘗試指派
成功? ──Yes──→ 完成
    ↓ No
Step 3: 最少線覆蓋零
    ↓
Step 4: 找 K → 未覆蓋減 K → 負值列加 K
    ↓
回 Step 2 (循環直到成功)

總結

匈牙利演算法通過矩陣縮減創造零元素，再以「最少線覆蓋零」判斷是否存在完全指派，若無則調整矩陣產生更多零，循環直到成功。本範例展示了 4×4 矩陣完整演化過程，最終得到總成本 21 的最佳指派方案。理解此流程是掌握指派問題求解的關鍵基礎。