最近在看 DETR 和 MaskFormer 的时候, 遇到两个集合最优匹配的问题. 其中用到的算法便是匈牙利算法.
匈牙利算法(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)\).
1. 引子
匈牙利算法的一个典型场景是任务分配. 举个例子:
现在有三名工人张三, 李四和王五以及三份工作扫地, 浇花和擦窗户. 每名工人做不同工作要求的工资是不同的, 如下表所示
| 扫地 | 浇花 | 擦窗户 | |
|---|---|---|---|
| 张三 | 2 | 1 | 3 |
| 李四 | 3 | 3 | 4 |
| 王五 | 3 | 3 | 2 |
每名工人分配一份工作, 问如何分配可以使得所付工资总和最少?
在上面这个例子中我们很容易观察出 张三-浇花, 李四-扫地, 王五-擦窗户 的成本最低. 但当工人数量和工作数量较大时, 寻找最优分配就变得不这么直观了.
2. 匈牙利算法
我们发现这类分配问题可以用一个矩阵表示(称为效益矩阵), 记为 \(\mathbf{C}\). 算法如下:
- 效益矩阵初始化
- (1.1) 将矩阵 \(\mathbf{C}\) 每行减去该行的最小元素, 得新矩阵 \(\mathbf{C}'\);
- (1.2) 将矩阵 \(\mathbf{C}'\) 每列减去该列的最小元素, 得新矩阵 \(\mathbf{C}''\), 以下操作对 \(\mathbf{C}''\) 进行;
- 对当前效益矩阵求可行解
- (2.1) 从含零最少的行(或列)开始, 圈出矩阵中的一个 “0”, 并划去其所在的行和列;
- (2.2) 重复步骤 (2.1) 直至矩阵中所有的 “0” 均被划去或圈出为止;
- (2.3) 若已圈出 \(n\) 个 “0”, 它们即对应一最优解, 如不然转步骤 3.
- 求覆盖当前效益矩阵中所有 “0” 的最少条数直线
- (3.1) 对没有圈出 “0” 的行打 \(\checkmark\), 对打 \(\checkmark\) 行上所有 “0” 所在的列打 \(\checkmark\), 再对打 \(\checkmark\) 的列上所有有 “0” 被圈出的行打 \(\checkmark\), 直至打不出 \(\checkmark\) 为止;
- (3.2) 将没有打 \(\checkmark\) 的行和打 \(\checkmark\) 的列划上直线, 这些直线即为所求.
- 调整效益矩阵
- (4.1) 找出没有被直线覆盖的所有元素中最小的数 \(\bar{c}\);
- (4.2) 将打 \(\checkmark\) 的行上每个元素减去 \(\bar{c}\), 打 \(\checkmark\) 的列上每个元素加上 \(\bar{c}\), 得到新的效益矩阵. 返回步骤 2.
3. 一个稍复杂的例子
一个 \(n=5\) 的例子如下图所示.
图 1. 匈牙利算法例子