# 匈牙利算法

## 用二分图描述此算法

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

 ${\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 行有一个零，所以分配了。第 3 行的 0 由于处于同一列而被划掉。
• 第 2 行有一个零，所以分配了。
• 第 3 行只有一个已经划掉的零，所以不能分配。
• 第 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}'}$

• 标记所有未分配的行（第 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}'}$

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

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

## 参考书目

• 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

## 参考文献

1. ^ Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955. Kuhn's original publication.
2. ^ Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistics Quarterly, 3: 253–258, 1956.
3. ^ J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.
4. ^ JACOBI'S BOUND

## 外部链接

### 实现

（请注意，并非所有这些都满足 ${\displaystyle O(n^{3})}$  时间约束。）