Jarvis' Blog 总有美丽的风景让人流连

匈牙利算法 (Hungarian Algorithm)

2022-05-23
Jarvis
Post

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

3. 一个稍复杂的例子

一个 \(n=5\) 的例子如下图所示.

图 1: 匈牙利算法例子


Content