匈牙利算法(Hungarian Algorithm) 是一种在多项式时间内求解的分配问题的组合优化算法, 由 Harold Kuhn 在1955年完善并发表. 算法的命名是因为该算法很大程度上是基于两位匈牙利数学家 Dénes Kőnig and Jenő Egerváry 的工作而来的. James Munkres 在 1957 年证明了该算法的复杂度是(强)多项式时间的, 此后该算法也被称为 Kuhn-Munkres 算法或 Munkres 分配算法. 原始算法的时间复杂度为$O(n^4)$ , Edmonds 和 Karp, 以及 Tomizawa 发现该算法可以优化到$O(n^3)$ .

匈牙利算法是一种在图论中寻找最优匹配的算法。它的目标是在给定的二分图中，找到最大的边数的匹配，使得每个顶点都与一条边相连，且每条边都只被一个顶点连接。
什么是二分图?
二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，且任意两条边不共用一个顶点。

应用场景

例子A

例子B

一个典型场景是任务分配. 举个例子:

现在有三名工人张三, 李四和王五以及三份工作扫地, 浇花和擦窗户. 每名工人做不同工作要求的工资是不同的, 如下表所示
| 姓名 | 扫地 | 浇花 | 擦窗户 |
| :—: | :—: | :—: | :—-: |
| 张三 | 2 | 1 | 3 |
| 李四 | 3 | 3 | 4 |
| 王五 | 3 | 3 | 2 |

每名工人分配一份工作, 问如何分配可以使得所付工资总和最少?
在上面这个例子中我们很容易观察出张三-浇花, 李四-扫地, 王五-擦窗户的成本最低. 但当工人数量和工作数量较大时, 寻找最优分配就变得不这么直观了.

匈牙利算法

我们发现这类分配问题可以用一个矩阵表示(称为效益矩阵), 记为 $C$ 算法如下:

效益矩阵初始化
(1.1) 将矩阵 $C$ 每行减去该行的最小元素, 得新矩阵 $C’$;
(1.2) 将矩阵 $C’$ 每列减去该列的最小元素, 得新矩阵 $C’’$, 以下操作对 $C’’$ 进行;
对当前效益矩阵求可行解
(2.1) 从含零最少的行(或列)开始, 圈出矩阵中的一个 “0”, 并划去其所在的行和列;
(2.2) 重复步骤 (2.1) 直至矩阵中所有的 “0” 均被划去或圈出为止;
(2.3) 若已圈出 n 个 “0”, 它们即对应一最优解, 如不然转步骤 3.
求覆盖当前效益矩阵中所有 “0” 的最少条数直线
(3.1) 对没有圈出 “0” 的行打 √, 对打√ 行上所有 “0” 所在的列打√ , 再对打√ 的列上所有 “0” 被圈出的行打√ , 直至打不出√为止;
(3.2) 将没有打 √的行和打√ 的列划上直线, 这些直线即为所求.
调整效益矩阵
(4.1) 找出没有被直线覆盖的所有元素中最小的数 $\overline{c}$;
(4.2) 将打√ 的行上每个元素减去 $\overline{c}$ , 打√ 的列上每个元素加上 $\overline{c}$ , 得到新的效益矩阵. 返回步骤 2.