匈牙利算法小结 | 莫叶何竹🍀

type

status

date

slug

summary

0 引出

最近看DETR论文，发现其通过匈牙利算法来进行预测和ground truth匹配，从而实现set prediction。这个思路很有意思，并且该匹配算法能适用多种问题，因此，对其进行详细记录，便于后续回顾。

首先来看，匈牙利算法能够解决什么问题。不妨以宝可梦作为例子引入。

现在有五个工作（搬砖、送快递、洗衣服、打扫、做饭）需要安排给有5个宝可梦（皮卡丘、杰尼龟、喷火龙、小拳石、妙蛙草）。每个宝可梦对每一项工作收费标准不同。如何安排工作使得成本最低。

（注：①每个宝可梦只能做一项工作；②每项工作只能分配给一个宝可梦做；③所有工作都要安排完。

表1 不同宝可梦对每一项工作收费表

ㅤ	搬砖	送快递	洗衣服	打扫	做饭
皮卡丘	12	7	9	7	9
杰尼龟	8	9	6	6	6
喷火龙	7	17	12	14	9
小拳石	15	14	6	6	10
妙蛙草	4	10	10	10	9

下面来看，匈牙利算法如何解决这种指派问题。

1 模型建立与求解

1.1 符号规定

对上述问题进行抽象，首先进行如下符号定义

符号	含义
	宝可梦的成本矩阵
	宝可梦对工作的收费.
	是否将工作配给宝可梦，若是则为，若否则为
	宝可梦的数量
	工作的数量

1.2 模型建立

通过上述符号定义，宝可梦的指派问题可进行如下抽象。

目标函数：

设计合适的指派策略使得用最低的成本完成工作。

约束条件

每个宝可梦只能做一件工作

每项工作只能分配给一个宝可梦

所有工作都要被分配

综上所述，上述对宝可梦指派问题的模型可以表述为：

1.3 模型求解

为了求解上述模型，最直接的方法是穷举法。不难得出共有种可能的组合，为的时间复杂度。匈牙利算法可以将上述的时间复杂度从降低到多项式的时间复杂度。下面来看匈牙利算法是如何进行的。

前置知识：指派问题的最优解有这样一个性质，若从系数矩阵的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵，那么以新矩阵为系数矩阵求得的最优解和用原矩阵求得的最优解相同．利用这个性质，可使原系数矩阵变换为含有很多0元素的新矩阵，而最优解保持不变。

归约

step1: 行归约（使得每行至少有一个零）

step2 列归约（使得每列至少有一个零）此处由于每列恰好最小值已为零，故列规约后结果不变。

试指派（找到归约后的成本矩阵中独立的零）

step1: 找到含0数目最少的行或列(不妨取行) 随后将该行第一个零置为“T0”,随后将“T0”所在行和列中其他的零置“F0”。依次类推，完成归约矩阵所有行的操作。

以上述的归约矩阵为例

step2: 用最少的直线来覆盖矩阵中所有的零。具体方法：

① 对没有T0的行用★进行标

② 对★所标记的行中存在的F0所在的列索引进行标记（同样标记★）

③ 对★所标记的列中，对T0所在的行索引进行标记（同样标记★）

④ 重复2、3步骤，直至找不到可以标记的行和列

①~④步骤以上述试指派为例

⑤ 对没有标记的行画横线表示去掉这一行，对标记的列画横线表示去掉这一列，这样就得到能覆盖所有0最小横线。

step3 变换试指派矩阵，增加其中的0元素。具体方法：

① 在未被直线覆盖的所有元素中找到min

② 在被★标记的所有行中减去这个元素；

③ 在被★标记的所有列中加上这个元素（保证原来的零不变）；

④ 得到新的归约矩阵。返回step1。直至满足约束条件

2 python程序实现

scipy中已实现匈牙利算法，可直接调用

为了深入理解计算过程，使用python进行实现