KM算法

**匈牙利演算法**是一種在多項式時間內求解任務分配問題的組合最佳化演算法，並推動了後來的原始對偶方法。美國數學家哈羅德・庫恩於 1955 年提出該演算法。此演算法之所以被稱作匈牙利演算法，是因為演算法很大一部分是基於以前匈牙利數學家科尼格・德內什和艾蓋瓦里・耶內的工作之上建立起來的。

詹姆士・芒克勒斯在 1957 年回顧了該演算法，並發現它的時間複雜度為（強）多項式時間。 此後該演算法被稱為 **Kuhn–Munkres 演算法**或 **Munkres 分配演算法**。原始演算法的時間複雜度為 $O(n^{4})$ ，但傑克・愛德蒙斯與卡普發現可以修改演算法達到 $O(n^{3})$ 執行時間，富澤也獨立發現了這一點。L・R・福特和 D・R・福爾克森將該方法推廣到了一般運輸問題。2006 年發現卡爾・雅可比在 19 世紀就解決了指派問題，該解法在他死後在 1890 年以拉丁文發表。

## Layman 對指派問題的解釋

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

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

## 設定

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

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

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

## 用二分圖描述此演算法

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

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

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

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

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

### 證明：改變勢函式 _y_ 不改變 _M_

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

### 證明：_y_ 仍然是勢函式

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

## 矩陣解釋

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

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

　
: ${\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}}$

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

**第 1 步**

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

用 0' 表示的零為已指派的任務。

**第 2 步**

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

在上述情形下，不能做出指派。注意到任務 1 由工人 $a$ 和 $c$ 做都很高效。只是不能把兩個工人分配到同一個任務中去。還注意到，沒有任何一個工人能有效地做任務 3。
為了克服這個問題，我們對所有列重複上述流程（即每一列所有元素都減去該列最小元素）並檢查是否可以完成分配。

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

**第 3 步**

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

首先，儘可能多地分配任務。

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

或者，分配的是第 3 行的 0，就會使第 1 行的 0 被劃掉。

現在到了畫圖的部分。

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

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

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

**第 4 步**

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

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

返回到步驟 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

## 參考文獻

## 外部連結

* Bruff, Derek, "The Assignment Problem and the Hungarian Method", [1] （頁面存檔備份，存於網際網路檔案館）
* Mordecai J. Golin, Bipartite Matching and the Hungarian Method, Course Notes, Hong Kong University of Science and Technology.
* R. A. Pilgrim, _Munkres' Assignment Algorithm. Modified for Rectangular Matrices （頁面存檔備份，存於網際網路檔案館）_ , Course notes, Murray State University.
* Mike Dawes, _The Optimal Assignment Problem_, Course notes, University of Western Ontario.
* On Kuhn's Hungarian Method – A tribute from Hungary （頁面存檔備份，存於網際網路檔案館）, András Frank, Egervary Research Group, Pazmany P. setany 1/C, H1117, Budapest, Hungary.
* Lecture: Fundamentals of Operations Research - Assignment Problem - Hungarian Algorithm （頁面存檔備份，存於網際網路檔案館）, Prof. G. Srinivasan, Department of Management Studies, IIT Madras.
* Extension: Assignment sensitivity analysis (with O (n^4) time complexity) （頁面存檔備份，存於網際網路檔案館）, Liu, Shell.
* Solve any Assignment Problem online （頁面存檔備份，存於網際網路檔案館）, provides a step by step explanation of the Hungarian Algorithm.

### 實現

（請注意，並非所有這些都滿足 $O(n^{3})$ 時間約束。）

* C implementation with $O(n^{3})$ time complexity （頁面存檔備份，存於網際網路檔案館）
* Java implementation of $O(n^{3})$ time variant （頁面存檔備份，存於網際網路檔案館）
* Python implementation （頁面存檔備份，存於網際網路檔案館） (see also here)
* Ruby implementation with unit tests （頁面存檔備份，存於網際網路檔案館）
* C# implementation （頁面存檔備份，存於網際網路檔案館）
* D implementation with unit tests (port of the Java $O(n^{3})$ version) （頁面存檔備份，存於網際網路檔案館）
* Online interactive implementation （頁面存檔備份，存於網際網路檔案館） Please note that this implements a variant of the algorithm as described above.
* Graphical implementation with options (Java applet)
* Serial and parallel implementations. （頁面存檔備份，存於網際網路檔案館）
* Implementation in Matlab and C （頁面存檔備份，存於網際網路檔案館）
* Perl implementation
* Lisp implementation
* C++ (STL) implementation (multi-functional bipartite graph version) （頁面存檔備份，存於網際網路檔案館）
* C++ implementation （頁面存檔備份，存於網際網路檔案館）
* C++ implementation of the $O(n^{3})$ algorithm （頁面存檔備份，存於網際網路檔案館） (BSD style open source licensed)
* Another C++ implementation with unit tests （頁面存檔備份，存於網際網路檔案館）
* Another Java implementation with JUnit tests (Apache 2.0)
* MATLAB implementation
* C implementation （頁面存檔備份，存於網際網路檔案館）
* Javascript implementation （頁面存檔備份，存於網際網路檔案館）
* The clue R package proposes an implementation, solve\_LSAP （頁面存檔備份，存於網際網路檔案館）