匈牙利算法

定义

匈牙利算法(Hungarian Algorithm)泛指基于增广路径求二分图最大匹配的方法,以及 Harold Kuhn 于 1955 年提出、纪念匈牙利数学家 Kőnig 与 Egerváry 的 Kuhn-Munkres(KM)算法,后者求解带权二分图的最优指派问题。

原理

无权版本反复为左侧未匹配点寻找交错增广路径:路径上未匹配边与已匹配边交替出现,找到后将其取反即可使匹配数加一,直到不存在增广路径。复杂度 O(VE)。KM 算法则在顶标与相等子图上运行同样的增广过程,求最大权完美匹配。

应用

任务与人员指派、订单与骑手调度、多目标跟踪中的检测框关联(如 SORT 跟踪器)、资源配对等。

说明

更快的二分图最大匹配可用 Hopcroft-Karp 算法(O(E√V));一般图匹配则需 Edmonds 的开花算法。