匈牙利演算法能在立方時間內找出 n 位工作者與 n 項任務之間的精確最低成本一對一配對，而 指派問題求解器可直接將其套用至任何最大 20 乘 20 的已標記方陣成本矩陣。您貼上一個以逗號分隔的網格,其首列以一個前置逗號開頭並列出任務名稱,接下來的每一列以工作者名稱開頭,後面接著每項任務的一個有限成本,然後讀回每位工作者的唯一任務、每組配對的成本,以及最低總成本。所有運算都在瀏覽器內進行,求解器強制執行確定性的列與欄平手規則,使相同的成本在每次執行時都以同樣的方式解決,完成的指派可複製為純文字以用於作業、人工檢查或小型排程草稿。實作遵循 Harold W. Kuhn 於 1955 年提出的原始對偶法,此方法也是 Google OR-Tools 將其文件化為完整加權雙重指派標準所依據的演算法。
用白話解釋指派問題
指派問題為一個完整的加權雙重圖建立模型:一邊為工作者、機器、代理人或其他資源,另一邊則為任務、工作、地點或選擇。每個矩陣格代表將一位工作者與一項任務配對的成本,而一個有效的解會從每一列與每一欄中各恰選一格,以使沒有任何工作者承擔兩項任務,也沒有任何任務被指派給兩個工作者。目標是最小化所選格的總和,這也是為何教科書中的問題以成本矩陣而非利潤表來呈現。
同樣的結構以許多不同的名稱出現。將技術員指派給工作、駕駛指派給路線、教室指派給時段、包裹指派給車輛,在每個選項都被賦予一個單一數字後,都會化約為同一個問題。紀律在於讓模型保持誠實:每個格子都必須真實代表執行該單一配對的成本,且矩陣必須維持方形,使每位工作者都能被配對,不會有任何一列懸而未決。
匈牙利演算法如何達到最小值
此求解器執行原始對偶的匈牙利演算法,亦稱為 Kuhn–Munkres 法。它維護列與欄位勢——作為每列與每欄陰影價格的輔助值——並反覆擴充一個最小簡化成本的配對,直到所有列都被納入。當最後一列加入後,每個任務欄位都恰指向一位工作者,給出您所想要的唯一一對一配對。
有兩個特性讓此演算法適合計算機所承諾的「逐步」呈現。首先,演算法在 n 乘 n 矩陣上以立方時間執行,這對工具所暴露的 20 乘 20 瀏覽器上限而言已足夠快速,且對於 3 乘 3 或 4 乘 4 的人工計算範例也游刃有餘。其次,此程序是精確的:它會回傳您所輸入矩陣的最低成本配對,而非近似值。同樣低廉配對之間的平手會依自然的列與欄順序解決,因此相同的輸入永遠產生相同的輸出——這正是您在驗證人工化約或比較兩份草稿時想要的特性。
若想更深入地了解潛在變數背後的搜尋與其角色,Google OR-Tools 指派指南會詳細說明簡化成本圖與擴充路徑邏輯。
建立求解器能接受的成本矩陣
- 開啟指派問題求解器,並清除預設矩陣,使輸入欄位為空白。
- 撰寫標題列,使其以逗號開頭,然後以逗號分隔列出每個唯一任務名稱,例如「,Task A,Task B,Task C」。前置的逗號會讓左上角的儲存格保持空白,並符合解析器的預期。
- 為每位工作者新增一列。每一行以工作者名稱開頭,接著對每項任務包含恰好一個有限的數值成本,以逗號分隔。請保持工作者與任務的數量相等,使矩陣維持方形。
- 檢查每個成本都是有限的(沒有空白、沒有 NaN、沒有無限大),且每個標籤都是唯一的。當符號慣例確實符合您的模型時,成本可以是正數、零或負數。
- 將矩陣貼到輸入方塊中,執行求解器,然後讀取配對表、每組配對的成本,以及最低總成本。如有需要,將指派複製為文字,以便貼到報告或聊天回覆中。
一個 3×3 計算範例
求解器所能接受的最簡單情況,是每位工作者對應一項任務,各有三個選項。使用下方的矩陣,具有最小總成本的指派其總和為 5。
| Worker | Task 1 | Task 2 | Task 3 |
|---|---|---|---|
| Worker A | 4 | 1 | 3 |
| Worker B | 2 | 0 | 5 |
| Worker C | 3 | 2 | 2 |
列舉六種有效排列,結果與求解器所顯示的一致。Worker A 至 Task 2(成本 1)、Worker B 至 Task 1(成本 2)、Worker C 至 Task 3(成本 2)得出 1 + 2 + 2 = 5,且沒有其他有效配對能再降低——次佳的候選解分別為 6 與 7。確定性的平手規則意味著,若您重新執行此矩陣,計算機會重現相同的配對,這正是您在逐列交叉檢查人工匈牙利化約時所需要的行為。
執行求解器並讀取輸出
結果面板會為每次執行回傳三項資訊。首先,一份配對清單,為每位工作者命名恰好一項任務,並為每項任務命名恰好一位工作者,因此不會重複使用任何列或欄。其次,每組配對的成本,依您在矩陣中所輸入的相同符號與單位讀取。第三,最低總成本,即每組配對成本的總和,也是您應該用來與人工計算或其他求解器比較的數值。
矩陣解析器刻意設計為嚴格。矩形矩陣、重複名稱、列中的空白、NaN 值及無限大的成本會以可見的訊息加以拒絕,而不是悄悄強制轉換。若您看到拒絕訊息,請修正輸入而非嘗試規避,因為匈牙利程序假設每個儲存格都是有限的,且每列與每欄都有唯一標籤。
| 輸入條件 | 狀態 | 原因 |
|---|---|---|
| 具有唯一名稱與有限成本的方形矩陣 | 接受 | 符合演算法所預期的完整加權雙重模型 |
| 矩形矩陣(工作者多於任務,或反之) | 拒絕 | 求解器為每位工作者配對一項任務;填補應由您的輸入負責,而非求解器 |
| 空白、NaN 或無限大的成本 | 拒絕 | 演算法需要每個儲存格都是有限數字 |
| 重複的工作者或任務名稱 | 拒絕 | 標籤必須識別唯一的列或欄 |
當成本矩陣不夠用時
匈牙利程序只會最小化您所輸入各儲存格的數值總和,除此之外什麼也不會處理。它無法辨識技能門檻、工作量容量、團隊相依性、公平性、依造訪順序而定的旅行時間、任務間的優先順序、每位工作者的多項任務、工作者的可用時段,或不確定性,除非這些影響已編碼於成本之中。現實中的人力配置決策還涉及法律、倫理與人文層面的考量,這些都無法化約為單一數字。請將此求解器視為一個透明的數學基準,然後在依其結果行動之前,將您自己的規則疊加在答案之上。
有兩個實用的陷阱值得特別提醒。首先,求解器永遠進行最小化,因此若您的資料為利潤或要最大化的分數,請刻意進行轉換——例如,將每個分數從一個大常數中減去——或選擇專為最大化設計的模型。貼上分數並假設「最佳」自動等同於「最大」,將會悄悄地回傳錯誤的答案。其次,此版本不支援空白或禁止的配對;每個矩陣儲存格都必須包含一個有限成本,因此禁止的配對必須以一個能真實代表允許該配對之成本的大型罰分來輸入。
何時升級至更大的求解器
20 乘 20 的瀏覽器上限已足以應付課堂範例、人工匈牙利檢查與適度的排程草稿,而立方時間演算法在該規模下能立即回傳最佳解。超過此範圍,相同的最低成本配對結構可在混合整數規劃、約束程序,或最小成本流網路中表示為線性指派問題,在此您可加入上述真實世界的規則,同時仍讓經驗證的求解器搜尋最佳解。若您需要明確編碼容量、技能等級或禁止指派,請改用上述其中一種工具,而非將規則偷偷塞進單一成本格中。
對於作業檢查、對 5 乘 5 工作指派進行快速健全性測試,或一份能在一個螢幕內顯示的草擬排程,指派問題求解器可在一次貼上與執行中給您精確的最佳解。對於更大或更受限的問題,請將同一矩陣建立為更豐富模型的成本區塊,並讓專屬的求解器承擔額外的規則。
若想深入了解,請參閱 0/1 背包問題計算機:取得最佳子集。
若想深入了解,請參閱 如何解決最小生成根樹問題。