指派問題,要找的是兩個大小相同的集合之間,成本最低的一對一配對——一邊是工人,另一邊是任務——在每一組工人對任務的成本都已知的前提下,而確定性的匈牙利演算法,能在任何 n×n 有限成本矩陣上,以三次方時間精確解出這個問題。一個線上的assignment problem solver,會讀取你貼進單一文字區域的一份帶標籤成本矩陣,在你的瀏覽器本機執行匈牙利演算法,並回傳每個工人恰好對應的一項任務,連同確切的最小總成本。因為一切都在用戶端執行,沒有任何資料會離開你的裝置,這讓同一個頁面,適合用來檢查作業、核對手動計算的匈牙利演算法結果,或在把一個小型機器對工作的配置定案、放進試算表之前先草擬一版。結果是確定性的:相同的輸入,永遠會產生相同的配對,並用列與欄的自然順序來打破平手,因此一份儲存的矩陣與一份儲存的答案,在多次執行、以及不同使用者之間,都能乾淨地對得上。
指派問題實際上在建模什麼
經典的指派問題,描述的是一個完整的加權二部圖。一邊列出工人、機器、代理人,或其他資源;另一邊列出任務、工作、地點,或選項。每一組可能的工人對任務配對,都有一個數值成本,寫在一個方陣中的一格裡。一個有效的解答,會從每一列中恰好選出一格、從每一欄中恰好選出一格——每個工人一項任務,每項任務一個工人——目標是把所選各格的總和最小化。
這種結構,出現在作業研究課程中,名稱像是「線性指派問題」與「最小成本完美配對」。Google OR-Tools describes it將其描述為在防止兩個工人拿到同一項任務的同時,把總指派成本最小化,這正是瀏覽器求解器所強制執行的同一個限制。這個問題的定義性要求,是矩陣必須是方形且完整的:工人數與任務數相同,而且每一組配對都有一個有限的成本,沒有任何被禁止的格子留白。
貼上一份矩陣,取得最低成本配對
- 輸入一行標題,以一個逗號開頭,接著每一欄放一個獨一無二的任務名稱,例如 ,Task A,Task B,Task C。
- 每個工人加一列,第一欄放工人名稱,後面每一項任務都恰好放一個有限的成本。工人名稱必須是唯一的,任務名稱也必須是唯一的,而且工人數必須等於任務數。
- 把整個區塊貼進 Assignment Problem Solver,執行匈牙利求解器,檢視每一組配對與總計,再用複製按鈕,把確切的最低成本指派結果匯出成文字。
一個可以直接貼上的三任務範例:
,Task A,Task B,Task CWorker 1,4,1,3Worker 2,2,0,5Worker 3,3,2,2
針對這個矩陣,唯一的最小指派結果是:Worker 1 → Task B、Worker 2 → Task A、Worker 3 → Task C,總成本為 1 + 2 + 2 = 5。只要是有限值,0 與負數的成本都能接受,因此一個小額獎金、退款,或零成本選項,都可以放進一格裡,不會破壞計算結果。
匈牙利演算法如何求得最優解
這個頁面實作的是匈牙利演算法,也稱為 Kuhn–Munkres 方法。它維護一組列與欄的位能值,並反覆擴增一個最小簡化成本配對,直到每一列工人都被配對為止。一旦每一列都被納入,每一欄任務,就會恰好指向一個工人,這正是針對輸入成本的最優指派結果。
對一個 n×n 矩陣而言,這在三次方時間內完成,這正是為什麼瀏覽器能針對課堂規模的輸入,立即回傳一個精確答案。實務上有兩個重要的結果。第一,答案是精確的:它不是一個啟發式的近似解,而且除了確定性的平手打破機制之外,它不取決於工人或任務被列出的順序。第二,平手會依列與欄的自然順序解決,因此如果兩組配對共享同一個最小總和,同樣的輸入永遠會回傳同一組配對——當你想拿一份答案卷,對照學生的作業,或在幾個月後重現一個已發表的範例時,這一點很有用。
這個求解器什麼時候適用,什麼時候不適用
| 情境 | 求解器會做什麼你實際上需要什麼 | |
|---|---|---|
| 在瀏覽器中回傳精確的最低成本配對 | —— | |
| 在求解器執行前就明顯被拒絕 | 用虛擬列或虛擬欄補齊,其成本正確表達「讓某個工人或任務未配對」 | |
| 只有在你先刻意轉換數值之後才可以 | 一個原生就能做最大化的模型,或對矩陣做一個有依據的正負號或位移轉換 | |
| 矩陣中並未表達 | 一個經過驗證的混合整數規劃、限制式規劃,或最小成本流求解器 | |
| 超出目前瀏覽器的邊界 | 一個具備同樣匈牙利保證的伺服器端線性指派程式庫 |
解讀結果並複製匯出
輸出結果會列出每個工人對應的任務、每組配對的成本,以及最小總計。因為這是一對一的指派,結果中的任務名稱全部唯一,而且每個工人都恰好出現一次。針對格式不正確的輸入——矩形矩陣、重複名稱、空白、NaN,或無限大的成本——會顯示一則明顯的拒絕訊息。複製按鈕會把配對結果與總計,以純文字形式匯出,因此這個答案可以直接放進一份實驗報告、一則聊天回覆,或一則筆記中,不需要重新打字。
如果你的資料含有利潤或分數,請不要直接貼上,並假設「最好」自動就等於最大的數字。這個求解器永遠是把數值總和最小化;一個利潤矩陣,需要一個明確的轉換——舉例來說,用一個較大的常數,減去每一格的值,好讓最大的利潤變成最小的成本——或者改用一個專門設計來做最大化的不同模型,才能信任回傳的配對結果。
測試過的案例,以及檢查過的內容
在開發過程中,有八個矩陣,獨立對照完整排列列舉的結果做過驗證。這組矩陣包括 1×1 與 2×2 的邊界情況、一個總成本最小值為 5 的標準 3×3 範例、每組配對共享同一個總和的完全平手情況,以及一個循環結構的 4×4 零成本組態。每項測試,都會斷言回傳的任務是唯一的、每個工人都有被指派,而且回報的總計與暴力列舉的結果相符。列與欄的自然順序,會以確定性的方式解決成本相等的選擇,因此對同一個矩陣執行兩次,不可能悄悄地產生不一致的結果。
值得知道的拒絕清單也一樣:一個 20 列、30 欄的矩陣、一列中含有空白格、一列含有文字「NaN」、一個與任務名稱重複的工人名稱,以及一格含有「Infinity」——這些都會在演算法開始執行之前就被擋下。如果你看到一則拒絕訊息,請修正矩陣的形狀或有問題的那一格,再重新執行——這個求解器不會靜默地平均一個缺失的成本、把一個無限值換成零,或挑一個任意的預設值。對於更大規模或有更多限制的排程,請改用一個經過驗證、能明確表達所有規則的混合整數規劃、限制式規劃,或最小成本流求解器,並在依此行動之前,獨立審查最終的指派結果。
如果你還在權衡選項,How to Calculate the Knapsack Problem Step by Step這篇文章有詳細說明。
如果你還在權衡選項,24 Game Solver App: Solve 24 in Your Browser這篇文章有詳細說明。