匈牙利演算法是一種組合最佳化演算法，可在三次方時間（即 $O(n^3)$ 複雜度）內解決指派問題，方法是化簡一個方型成本矩陣，以找出 $n$ 個工作者與 $n$ 個任務之間精確的最小成本一對一配對。該演算法亦稱為 Kuhn–Munkres 演算法，透過操作行與列的位勢來找出總權重最小的完整二部圖配對。它需要一個完整的、方型的、有限成本的矩陣，其中每個儲存格代表將特定工作者指派給特定任務的數值成本。透過系統性地減去每行與每列的最小值，演算法會暴露出零成本的機會，而這些機會可以用最少數量的線條覆蓋。當覆蓋所有零所需的最小線條數等於矩陣的維度時，就達到了最佳指派。這個確定性的數學模型確保恰好一名工作者與恰好一項任務配對，在最小化整體系統成本的同時避免資源衝突。
二部圖配對的數學基礎
指派問題建立的是一個完整的加權二部圖模型。在此圖中，一側包含工作者、機器、代理人或其他資源，另一側則包含任務、工作、地點或選項。每個矩陣儲存格代表一種可能配對的成本。一個有效的解會從每一行中恰好選取一個儲存格，並從每一列中也恰好選取一個。如 Google OR-Tools — Assignment 所記錄，主要目標是在最小化總指派成本的同時，避免兩名工作者接受同一項任務。
由於匈牙利演算法在 n 乘 n 矩陣上以三次方時間執行，相較於以暴力列舉所有可能排列（其數量以階乘成長）的方式，它極為有效率。這個數學基準雖然用途多元，但在結構上與其他網路最佳化問題有所不同。例如，指派問題是在二部圖上配對離散節點，而最小生成樹則是在一般圖中以最低的總邊權重連接所有節點。如果您正在處理更廣泛的網路設計，可以參考我們的指南如何解決最小生成樹問題來比較這些最佳化技術。
以 3 乘 3 範例手動進行矩陣化簡
為了理解匈牙利方法的運作機制，使用一個標準的 3 乘 3 矩陣進行手動計算非常有幫助。在這個情境中，我們有三名工作者（W1、W2、W3）以及三項任務（任務 A、任務 B、任務 C）。我們的目標是找出能產生絕對最小總成本的配對。
| 工作者 | 任務 A 成本 | 任務 B 成本 | 任務 C 成本 |
|---|---|---|---|
| W1 | 2 | 3 | 3 |
| W2 | 3 | 2 | 3 |
| W3 | 3 | 3 | 1 |
若要手動求解，請遵循經典的矩陣化簡步驟：
步驟 1：行化簡
找出每行中的最小值，並將其從該行的每個元素中減去。此步驟會在每行中至少產生一個零。
- 第 1 行最小值為 2。將每個儲存格減去 2：$[2-2, 3-2, 3-2] = [0, 1, 1]$
- 第 2 行最小值為 2。將每個儲存格減去 2：$[3-2, 2-2, 3-2] = [1, 0, 1]$
- 第 3 行最小值為 1。將每個儲存格減去 1：$[3-1, 3-1, 1-1] = [2, 2, 0]$
步驟 2：列化簡
使用已進行行化簡的矩陣，找出每列中的最小值，並將其從該列的每個元素中減去。這能確保每列也至少包含一個零。
- 第 1 列的值為 $[0, 1, 2]$。最小值為 0。減去 0 後該列維持不變：$[0, 1, 2]$
- 第 2 列的值為 $[1, 0, 2]$。最小值為 0。減去 0 後該列維持不變：$[1, 0, 2]$
- 第 3 列的值為 $[1, 1, 0]$。最小值為 0。減去 0 後該列維持不變：$[1, 1, 0]$
步驟 3：以最少數量的線條覆蓋所有零
嘗試使用最少數量的水平線或垂直線，覆蓋化簡後矩陣中的所有零。在我們化簡後的矩陣中，零位於 (W1，任務 A)、(W2，任務 B) 與 (W3，任務 C)。為了覆蓋這三個獨立的零，我們必須恰好畫出三條線（無論是三行或三列）。
由於覆蓋所有零所需的最小線條數 (3) 等於我們矩陣的維度（$n = 3$），因此已達到最佳狀態。如果線條數小於 3，則必須額外進行一輪迭代：找出最小的未覆蓋元素，將其從所有未覆蓋元素中減去，並將其加到位於線條交叉處的元素上。
步驟 4：決定最佳指派
我們根據完全化簡後矩陣中零成本的儲存格，將工作者指派給對應的任務：
- W1 被指派給任務 A（原始成本 = 2）
- W2 被指派給任務 B（原始成本 = 2）
- W3 被指派給任務 C（原始成本 = 1）
若要找出最小總成本，我們將這些最佳配對的原始值加總：$2 + 2 + 1 = 5$。這與這個標準 3 乘 3 範例的確定性最小成本基準相符。
如何在線上解決指派問題
雖然手動化簡對於 3 乘 3 矩陣而言很簡單，但較大的矩陣很快就會變得繁瑣且容易出現算術錯誤。在線的指派問題求解器會自動化整個流程。它會解析一個包含 1 到 20 個唯一命名的工作者與任務的完整方型矩陣，驗證您的輸入，並套用原始對偶式匈牙利演算法，立即回傳精確的最小成本配對。
- 撰寫以逗號開頭的標頭，後接唯一的工作任務名稱。
- 每行加入一名工作者，每項任務給定恰好一個有限成本，並保持工作者與任務的數量相等。
- 執行匈牙利求解器，檢查每組配對與成本慣例，然後複製精確的最小成本指派結果。
舉例來說，若要解決我們手動計算過的 3 乘 3 問題，您會將以下以逗號分隔的矩陣貼到輸入欄位中：
,Task A,Task B,Task C W1,2,3,3 W2,3,2,3 W3,3,3,1
該工具完全在您的瀏覽器中執行。它會立即顯示每位工作者被指派的任務、個別配對成本，以及最小總成本。您可以將最終的指派表格以純文字格式複製，用於您的報告或作業。
了解模型假設與限制
若要成功地使用匈牙利方法，您的資料必須符合此模型的數學假設。下表概述了手動方法與線上求解工具的功能比較，凸顯了關鍵的結構性限制。
| 功能或限制 | 手動匈牙利方法 | 線上求解工具 |
|---|---|---|
| 實用的矩陣大小上限 | 通常在 4x4 或 5x5 之前，之後手動錯誤會急劇增加。 | 可達 20x20，輕鬆涵蓋課堂與中等規模的排程任務。 |
| 處理位置 | 您的桌面或白板。 | 在本機瀏覽器中執行；不會將任何資料上傳到伺服器。 |
| 輸入驗證 | 容易受到人為疏失影響；很容易漏掉重複的名稱或遺漏的儲存格。 | 會拒絕格式錯誤或非方型的矩陣、重複名稱、空格，以及 NaN。 |
| 平手解決方式 | 由畫線的人任意決定。 | 依自然的行與列順序以確定性方式解決。 |
| 支援的成本類型 | 支援任何實數，但負數會讓手動計算變得複雜。 | 支援正數、零與負數，只要它們是有限的。 |
務必記住這個求解器永遠是在最小化數值總和。如果您的資料包含您想要最大化的利潤或分數，您必須在貼入工具之前刻意地轉換它們。例如，您可以從原始矩陣中的最大值減去每個值，以將最大化問題轉換為最小化問題。請勿直接貼上原始的利潤分數，並假設「最佳」結果自動代表最大的數字。
此外，此實作假設每位工作者都能執行每項任務。不支援以空白儲存格表示禁止配對。如果某個配對在您的真實情境中實體上不可能，您必須為其指派一個極高的虛擬成本（「懲罰成本」），以確保演算法不會選擇它。
最後，此模型所產生的精確最佳解僅涵蓋您所輸入的精確成本。它不會考量真實世界的細微差異，例如技能門檻、工作負載容量、團隊相依性、公平性、交通時間變化、優先順序、每位工作者的多項任務、工作者可用性或不確定性。實際的人力決策往往涉及無法簡化為成本矩陣的法律、倫理與人為因素。請將這個數學結果視為一個透明的基準，而非自動且不可審查的人事決策。對於大規模的工業排程或高度受限的作業，您應該使用經過驗證的混合整數、限制規劃或最小成本流求解器，以明確地表示所有的政策規則。
延伸閱讀：如何找出背包問題中的 Xi。