KM 算法(Kuhn-Munkres)

KM 算法(Kuhn-Munkres algorithm,库恩-芒克雷斯算法)用于求解带权二分图的最大权完美匹配问题,常被视为无权匈牙利算法在带权情形下的推广,也称指派问题算法。它为二分图两侧顶点各设一个顶标,只在满足顶标之和等于边权的相等子图中寻找完美匹配,并在找不到时按规则调整顶标扩大可用边,直到匹配所有顶点且权和最优。

概述

指派问题要求把 n 个任务分配给 n 个人,使总收益最大或总成本最小,本质是带权二分图的最优匹配。KM 算法基于线性规划对偶思想,用顶标刻画对偶变量,通过反复增广与顶标修正逼近最优,是解决这类分配优化的标准方法。

核心原理

• 顶标初始化:给左部每个顶点赋予其邻接边的最大权作为顶标,右部顶标初始为零。
• 相等子图:只保留满足两端顶标之和恰等于边权的边,在其中寻找完美匹配。
• 增广匹配:用类似匈牙利算法的方式在相等子图中寻找增广路来扩大匹配。
• 顶标调整:当无法增广时,计算交替树中一侧顶点到未访问边的最小松弛量,据此下调左部、上调右部顶标,使新边进入相等子图。
• 收敛:重复增广与调整,直到所有顶点被匹配,此时匹配权和达到最优。

应用场景

KM 算法广泛用于任务指派、人员排班、资源与需求的最优对接、多目标跟踪中的关联匹配、以及运筹学里的运输与分配模型。凡是需要在两组对象间寻找总收益最大或总代价最小的一一对应关系时,它都是首选算法。

常见问题

问:KM 算法要求图是完全二分图吗?答:通常要求存在完美匹配,若原图不完全,可补上权值为零或极小的虚拟边使其成为完全二分图,再求最大权完美匹配。

问:求最小权匹配怎么办?答:可将所有边权取相反数或用一个足够大的常数减去边权,转化为最大权匹配后再求解,结果对应原问题的最小权匹配。