匈牙利演算法

匈牙利演算法是一種在多項式時間內求解任務分配問題的組合最佳化演算法，並推動了後來的原始對偶方法（英語：primal-dual methods）。美國數學家哈羅德·W·庫恩於1955年提出該演算法。此演算法之所以被稱作匈牙利演算法，是因為演算法很大一部分是基於以前匈牙利數學家科尼格·德內什（英語：Dénes Kőnig）和艾蓋瓦里·耶內的工作之上建立起來的。^[1][2]

以最低的總成本將任務分配給工人的圖解。

詹姆士·芒克勒斯在1957年回顧了該演算法，並發現它的時間複雜度為（強）多項式時間。^[3] 此後該演算法被稱為庫恩-芒克勒斯演算法或芒克勒斯分配演算法。原始演算法的時間複雜度為${\displaystyle O(n^{4})}$，但傑克·愛德蒙斯（英語：Jack Edmonds）與理察·卡普發現可以修改演算法達到${\displaystyle O(n^{3})}$執行時間。小萊斯特·倫道夫·福特和德爾伯特·雷·富爾克森將該方法推廣到一般運輸問題，稱作福特-富爾克森演算法。2006年發現卡爾·雅可比在19世紀就解決了指派問題，該解法在他死後在1890年以拉丁文發表。^[4]

問題

你有三個工人：吉姆，史提夫和艾倫。 你需要其中一個清潔浴室，另一個打掃地板，第三個洗窗，但他們每個人對各項任務要求不同數目數量的錢。 以最低成本的分配工作的方式是什麼？ 可以用工人做工的成本矩陣來表示該問題。例如：

	清潔浴室	打掃地板	洗窗
吉姆	$2	$3	$3
史提夫	$3	$2	$3
艾倫	$3	$3	$2

當把匈牙利方法應用於上面的表格時，會給出最低成本：為6美元，讓吉姆清潔浴室、史提夫打掃地板、艾倫清洗窗戶就可以達到這一結果。

設定

給定一個 ${\displaystyle n\times n}$ 的非負矩陣，其中第 ${\displaystyle i}$ 行第 ${\displaystyle j}$ 列元素表示把第 ${\displaystyle i}$ 個工人派到第 ${\displaystyle j}$個工作的成本。我們必須找到成本最低的工人工作分配。如果目標是找到最高成本的分配，該問題可以將每個成本都換為最高一個成本減去該成本以適應題目。

如果用二分圖來闡述該問題可以更容易描述這個演算法。對於一個有 ${\displaystyle n}$個工人節點（${\displaystyle S}$）與 ${\displaystyle n}$個工作節點（${\displaystyle T}$）的完全二分圖 ${\displaystyle G=(S\cup T,E)}$，每條邊都有 ${\displaystyle c(i,j)}$ 的非負成本。我們要找到最低成本的完美匹配。

如果函式 ${\displaystyle y:(S\cup T)\mapsto \mathbb {R} }$ 滿足對於每個 ${\displaystyle i\in S,j\in T}$ 都有 ${\displaystyle y(i)+y(j)\leq c(i,j)}$，則把該函式叫做勢。勢 ${\displaystyle y}$ 的值為 ${\displaystyle \sum _{v\in S\cup T}y(v)}$。可以看出，每個完美匹配的成本最低是每個勢的值。匈牙利演算法找出了完美匹配及與之成本/值相等的勢，這證明了兩者的最佳性。實際上它找到了緊邊集的完美匹配：緊邊 ${\displaystyle ij}$ 是指對於勢 ${\displaystyle y}$ 滿足 ${\displaystyle y(i)+y(j)=c(i,j)}$。我們將緊邊子圖表示為 ${\displaystyle G_{y}}$。${\displaystyle G_{y}}$ 中的完美匹配的成本（如果存在）就等於 ${\displaystyle y}$的值。

用二分圖描述此演算法

在演算法中我們維持 ${\displaystyle G_{y}}$ 的勢${\displaystyle y}$和方向（表示為 ${\displaystyle {\overrightarrow {G_{y}}}}$ ），該方向有從 ${\displaystyle T}$到 ${\displaystyle S}$ 的邊構成匹配 ${\displaystyle M}$ 的性質。初始時，${\displaystyle y}$ 處處為 0， 所有邊都由 ${\displaystyle S}$ 指向 ${\displaystyle T}$（因此 ${\displaystyle M}$ 為空）。每一步中，我們或者改變 ${\displaystyle y}$ 使其值增加， 或者改變方向以得到更多的邊。我們保持 ${\displaystyle M}$ 的所有邊都是緊邊不發生改變。當 ${\displaystyle M}$ 為完美匹配時結束。

在一般的步驟中，令 ${\displaystyle R_{S}\subseteq S}$ 和 ${\displaystyle R_{T}\subseteq T}$ 為 ${\displaystyle M}$ 未覆蓋的節點 （則 ${\displaystyle R_{S}}$ 包含 ${\displaystyle S}$ 中入度為零的節點，而 ${\displaystyle R_{T}}$ 中包含 ${\displaystyle T}$ 中出度為零的節點）。 令 ${\displaystyle Z}$ 為從 ${\displaystyle R_{S}}$ 只沿緊邊的有向路徑可到達 ${\displaystyle {\overrightarrow {G_{y}}}}$ 的節點。可由廣度優先搜尋求得。

若 ${\displaystyle R_{T}\cap Z}$ 非空，則將 ${\displaystyle {\overrightarrow {G_{y}}}}$ 中從 ${\displaystyle R_{S}}$ 到 ${\displaystyle R_{T}}$ 的有向路徑反向。則相應匹配數增加1。

若 ${\displaystyle R_{T}\cap Z}$ 為空，則令 ${\displaystyle \Delta :=\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}}$。${\displaystyle \Delta }$ 為正，因為 ${\displaystyle Z\cap S}$ 與 ${\displaystyle T\setminus Z}$ 之間沒有緊邊。 在 ${\displaystyle Z\cap T}$ 中的節點將${\displaystyle y}$增加${\displaystyle \Delta }$ 並在 ${\displaystyle Z\cap S}$ 中節點將 ${\displaystyle y}$減小 ${\displaystyle \Delta }$， 得到的${\displaystyle y}$仍然是勢。圖 ${\displaystyle G_{y}}$ 改變了，但它仍包含${\displaystyle M}$。我們把新的邊從${\displaystyle S}$指向${\displaystyle T}$。 由 ${\displaystyle \Delta }$ 的定義，${\displaystyle R_{S}}$ 可達的節點集 ${\displaystyle Z}$ 增大（注意到緊邊的數量不一定增加）。

我們重複這些步驟直到${\displaystyle M}$為完美匹配，該情形下給出的是最小成本（即時間消耗）的匹配。此版本的執行時間為 ${\displaystyle O(n^{4})}$：${\displaystyle M}$ 增廣 ${\displaystyle n}$次， 在 ${\displaystyle M}$ 不改變的一個階段中，勢最多改變 ${\displaystyle n}$ 次（因為 ${\displaystyle Z}$ 每次都增加）。改變勢所需的時間在 ${\displaystyle O(n^{2})}$。

證明：改變勢函式y不改變M

證明改變${\displaystyle y}$後${\displaystyle M}$中每條邊不發生改變，這等價於證明對於${\displaystyle M}$中任意邊，它的兩個頂點要麼都在${\displaystyle Z}$中，要麼都不在${\displaystyle Z}$中。為此，定義${\displaystyle vu}$為${\displaystyle M}$中一條從${\displaystyle T}$到${\displaystyle S}$的邊，則若${\displaystyle v\in Z}$，那麼有${\displaystyle u\in Z}$。（反證）假設${\displaystyle u\in Z}$但${\displaystyle v\notin Z}$；由於${\displaystyle u}$是一個匹配邊的末端點，${\displaystyle u\notin R_{S}}$，因此存在從${\displaystyle R_{S}}$到${\displaystyle u}$的有向路徑。這條路徑必不能經過${\displaystyle v}$（根據假設），因此這條路徑上緊鄰${\displaystyle u}$的點是其他點${\displaystyle v'\in T}$。${\displaystyle v'u}$是一條從${\displaystyle T}$到${\displaystyle S}$的緊邊因此也是${\displaystyle M}$中的一個元素。但因此${\displaystyle M}$包含兩條有共點的邊，與${\displaystyle M}$是匹配的定義矛盾。因此${\displaystyle M}$中每條邊的兩個頂點要麼都在${\displaystyle Z}$中，要麼都不在${\displaystyle Z}$中。

證明：y仍然是勢函式

證明${\displaystyle y}$在更改之後是勢函式，等價於證明不存在總勢超過成本的邊。這已經在之前的論述中已經為${\displaystyle M}$中的邊建立這個概念，因此我們考慮任意從${\displaystyle S}$到${\displaystyle T}$的邊${\displaystyle uv}$。如果${\displaystyle y(u)}$升高了${\displaystyle \Delta }$，那麼：(1)${\displaystyle v\in Z\cap T}$，在這種情況下，${\displaystyle y(v)}$減小了${\displaystyle \Delta }$，使總體的勢未發生改變；(2)${\displaystyle v\in T\setminus Z}$，這種情況下${\displaystyle \Delta }$的定義保證了${\displaystyle y(u)+y(v)+\Delta \leq c(u,v)}$。因此${\displaystyle y}$仍然是勢函式。

矩陣解釋

給定 ${\displaystyle n}$ 個工人和任務，以及一個包含分配給每個工人一個任務的成本的 ${\displaystyle n\times n}$矩陣，尋找成本最小化分配。

首先把問題寫成下面的矩陣形式

${\displaystyle {\begin{bmatrix}a_{1}&a_{2}&a_{3}&a_{4}\\b_{1}&b_{2}&b_{3}&b_{4}\\c_{1}&c_{2}&c_{3}&c_{4}\\d_{1}&d_{2}&d_{3}&d_{4}\end{bmatrix}}}$

其中 ${\displaystyle a,b,c,d}$是執行任務 1, 2, 3, 4 的工人。${\displaystyle a_{1},a_{2},a_{3},a_{4}}$ 分別表示當工人 ${\displaystyle a}$ 做任務 1, 2, 3, 4 時的時間損失（成本）。對於其他符號也同樣適用。該矩陣是方陣，所以每個工人只能執行一個任務。

第 1 步

接下來我們對矩陣的行進行操作。將所有 ${\displaystyle a_{i}}$ （${\displaystyle i}$ 從 1 到 4）中最小的元素取走，並將該行每個元素都減去剛剛取走的元素。這會讓該行至少出現一個零（當一行有兩個相等的最小元素時會得到多個零）。對此過程為所有行重複。我們現在得到一個每行至少有一個零的矩陣。現在我們嘗試給工人指派任務，以使每個工人只做一項任務，並且每個情況的耗散都為零。說明如下。

${\displaystyle 0}$	${\displaystyle a_{2}'}$	${\displaystyle a_{3}'}$	${\displaystyle a_{4}'}$
${\displaystyle b_{1}'}$	${\displaystyle b_{2}'}$	${\displaystyle b_{3}'}$	${\displaystyle 0}$
${\displaystyle c_{1}'}$	${\displaystyle 0}$	${\displaystyle c_{3}'}$	${\displaystyle c_{4}'}$
${\displaystyle d_{1}'}$	${\displaystyle d_{2}'}$	${\displaystyle 0}$	${\displaystyle d_{4}'}$

每一行的 0 的個數可以超過 1。

若有出現行中 0 的個數超過 1，在最壞的情況下，會需要在 ${\displaystyle n!}$ 的組合中找到一個成本最小的配對。

第 2 步

有時此階段的該矩陣不能符合指派的要求，例如下面所示矩陣。

${\displaystyle 0}$	${\displaystyle a_{2}'}$	${\displaystyle a_{3}'}$	${\displaystyle a_{4}'}$
${\displaystyle b_{1}'}$	${\displaystyle b_{2}'}$	${\displaystyle b_{3}'}$	${\displaystyle 0}$
${\displaystyle 0}$	${\displaystyle c_{2}'}$	${\displaystyle c_{3}'}$	${\displaystyle c_{4}'}$
${\displaystyle d_{1}'}$	${\displaystyle 0}$	${\displaystyle d_{3}'}$	${\displaystyle d_{4}'}$

在上述情形下，不能做出指派。注意到任務 1 由工人 ${\displaystyle a}$ 和 ${\displaystyle c}$ 做都很高效 (${\displaystyle a_{1}'}$ 和 ${\displaystyle c_{1}'}$ 為 0 )。但兩個工人無法分配到同一個任務。

還注意到，沒有任何一個工人能有效地做任務 3 (${\displaystyle a_{3}'}$、${\displaystyle b_{3}'}$、${\displaystyle c_{3}'}$、${\displaystyle d_{3}'}$ 皆不為 0)。 為了克服這個問題，我們對所有列重複上述流程（即每一列所有元素都減去該列最小元素）並檢查是否可以完成分配。

大多數情況下，這都會給出結果，但如果仍然是不可行，那麼我們需要繼續下去。

第 3 步

必須用儘可能少的列或行標記來覆蓋矩陣中的所有零。下面的過程是完成這個要求的一種方法：

首先，儘可能多地分配任務，用 0' 表示的零為已指派的任務，

• 第 1 行有一個零，所以用 0' 表示為分配。第 3 行的 0 由於處於同一列而被劃掉。
• 第 2 行有一個零，所以用 0' 表示為分配。
• 第 3 行只有一個已經劃掉的零，所以不能分配。
• 第 4 行有兩個未劃掉的零。可以分配任何一個（都是最佳） ，並將另一個零划去。

(在此階斷任何合法的分配都可以接受，因此若一開始分配的是第 3 行的 0，就會使第 1 行的 0 被劃掉。)

${\displaystyle 0'}$	${\displaystyle a_{2}'}$	${\displaystyle a_{3}'}$	${\displaystyle a_{4}'}$
${\displaystyle b_{1}'}$	${\displaystyle b_{2}'}$	${\displaystyle b_{3}'}$	${\displaystyle 0'}$
${\displaystyle 0}$	${\displaystyle c_{2}'}$	${\displaystyle c_{3}'}$	${\displaystyle c_{4}'}$
${\displaystyle d_{1}'}$	${\displaystyle 0'}$	${\displaystyle 0}$	${\displaystyle d_{4}'}$

現在到了畫圖的部分。

• 標記所有未分配的行（第 3 行）。
• 標記所有新標記的行中 0所在（且未標記）的對應列（第 1 列）。
• 標記所有在新標記的列中有分配的行（第 1 行）。
• 對所有未分配的行重複上述過程。

×
${\displaystyle 0'}$	${\displaystyle a_{2}'}$	${\displaystyle a_{3}'}$	${\displaystyle a_{4}'}$	×
${\displaystyle b_{1}'}$	${\displaystyle b_{2}'}$	${\displaystyle b_{3}'}$	${\displaystyle 0'}$
${\displaystyle 0}$	${\displaystyle c_{2}'}$	${\displaystyle c_{3}'}$	${\displaystyle c_{4}'}$	×
${\displaystyle d_{1}'}$	${\displaystyle 0'}$	${\displaystyle 0}$	${\displaystyle d_{4}'}$

現在劃掉所有已標記的列和未標記的行（第 1 列和第 2, 4 行）。

×
${\displaystyle 0'}$	${\displaystyle a_{2}'}$	${\displaystyle a_{3}'}$	${\displaystyle a_{4}'}$	×
${\displaystyle b_{1}'}$	${\displaystyle b_{2}'}$	${\displaystyle b_{3}'}$	${\displaystyle 0'}$
${\displaystyle 0}$	${\displaystyle c_{2}'}$	${\displaystyle c_{3}'}$	${\displaystyle c_{4}'}$	×
${\displaystyle d_{1}'}$	${\displaystyle 0'}$	${\displaystyle 0}$	${\displaystyle d_{4}'}$

上述詳細的描述只是畫出覆蓋所有 0 的（直、行）線的一種方法。也可以使用其他方法。

第 4 步

現在刪除已畫線的行和列。這將留下一個矩陣如下：

${\displaystyle {\begin{bmatrix}a_{2}&a_{3}&a_{4}\\c_{2}&c_{3}&c_{4}\end{bmatrix}}}$

返回到步驟 1，然後重複這個過程，直到矩陣是空的；當矩陣為空時，意即畫出的覆蓋所有 0 的（直、行）線的個數等於原本矩陣的行數(或列數) ${\displaystyle n}$，在上述的例子中 ${\displaystyle n=4}$，此時代表有一個分配的最佳解存在於這些 0 的組合之中，我們可以在步驟 1 中從所有分配的組合中找到成本最小的解。

參考書目

• R.E. Burkard, M. Dell'Amico, S. Martello: Assignment Problems (Revised reprint). SIAM, Philadelphia (PA.) 2012. ISBN 978-1-61197-222-1
• M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italia, 1995.
• R. Ahuja, T. Magnanti, J. Orlin, "Network Flows", Prentice Hall, 1993.
• S. Martello, "Jeno Egerváry: from the origins of the Hungarian algorithm to satellite communication". Central European Journal of Operations Research 18, 47–58, 2010