Kuhn-Munkres算法（二分图最大权匹配）
字数 1970 2025-11-30 04:25:05
Kuhn-Munkres算法（二分图最大权匹配）
题目描述
给定一个完全二分图 \(G = (X \cup Y, E)\)，其中 \(|X| = |Y| = n\)，每条边 \((x_i, y_j)\) 有一个权重 \(w_{ij}\)。目标是找到一个完美匹配（每个顶点恰好匹配一次），使得匹配边的权重之和最大。
解题过程
1. 问题转换：最大权匹配 → 最小权匹配
通过将权重取负（\(w_{ij} \leftarrow -w_{ij}\)），可将最大权匹配问题转化为最小权匹配问题。但更常见的做法是使用顶标（Vertex Labeling）直接求解最大权匹配：
- 为每个顶点 \(u\) 分配一个顶标 \(l(u)\)，满足对于任意边 \((x_i, y_j)\) 有 \(l(x_i) + l(y_j) \geq w_{ij}\)。
- 相等子图 \(G_l\) 包含所有满足 \(l(x_i) + l(y_j) = w_{ij}\) 的边。
关键定理：若相等子图 \(G_l\) 存在完美匹配，则该匹配即为原图的最大权匹配。
2. 算法流程
步骤1：初始化顶标
- 对 \(X\) 中的顶点 \(x_i\)，令 \(l(x_i) = \max_{j} w_{ij}\)（即每行最大值）。
- 对 \(Y\) 中的顶点 \(y_j\)，令 \(l(y_j) = 0\)。
此时所有边满足 \(l(x_i) + l(y_j) \geq w_{ij}\)。
步骤2：在相等子图中寻找匹配
- 在相等子图 \(G_l\) 中尝试找到完美匹配（例如用匈牙利算法求最大匹配）。
- 若找到完美匹配，算法结束；否则进入步骤3。
步骤3：调整顶标以扩展相等子图
- 设当前匹配为 \(M\)，未匹配的 \(x_i\) 为起点，用类似匈牙利算法的方式标记交替路径（从 \(X\) 到 \(Y\) 的未匹配边，再从 \(Y\) 到 \(X\) 的匹配边）。
- 标记后得到两个集合：
- \(S \subseteq X\)：已访问的 \(X\) 顶点。
- \(T \subseteq Y\)：已访问的 \(Y\) 顶点。
- 计算调整量 \(\delta = \min\{ l(x_i) + l(y_j) - w_{ij} \mid x_i \in S, y_j \notin T \}\)。
- 调整顶标：
- 对 \(x_i \in S\)，令 \(l(x_i) \leftarrow l(x_i) - \delta\)。
- 对 \(y_j \in T\)，令 \(l(y_j) \leftarrow l(y_j) + \delta\)。
- 调整后，相等子图会加入新边（至少一条），同时保持已匹配边不变。
步骤4：重复步骤2-3直到找到完美匹配
3. 举例说明
考虑二分图（最大权匹配）：
权重矩阵：
y1 y2 y3
x1 2 3 1
x2 4 2 5
x3 3 7 2
初始化顶标：
- \(l(x1)=3, l(x2)=5, l(x3)=7\)
- \(l(y1)=l(y2)=l(y3)=0\)
第一次相等子图：包含边满足 \(l(x_i)+l(y_j)=w_{ij}\)：
- 检查边：
- (x1,y2): 3+0=3 ✓
- (x2,y3): 5+0=5 ✓
- (x3,y2): 7+0=7 ✓
初始匹配尝试：可能找到匹配 \(M=\{(x1,y2), (x3,y2)\}\) 冲突（y2重复），需调整。
调整过程：
- 从未匹配的 x2 开始标记交替路径，计算 \(\delta = \min\{ l(x_i)+l(y_j)-w_{ij} \mid x_i \in S, y_j \notin T \}\)
- 假设 S={x2}, T={}，则 δ=min(5+0-4=1, 5+0-2=3, 5+0-5=0) → δ=0（直接找到可行边）。
实际执行需完整模拟交替路径，此处简化为：通过调整顶标逐步扩展相等子图，最终得到完美匹配 \(\{(x1,y1), (x2,y3), (x3,y2)\}\)，权重和=2+5+7=14。
4. 复杂度分析
- 每次顶标调整至少加入一条新边到相等子图，最多调整 \(O(n^2)\) 次。
- 每次尝试匹配（匈牙利算法）需要 \(O(n^2)\)。
- 总复杂度 \(O(n^4)\)，但通过精细实现（如使用松弛操作）可优化到 \(O(n^3)\)。
总结：Kuhn-Munkres算法通过顶标构造相等子图，逐步调整顶标扩大相等子图，直到找到完美匹配，从而解决二分图最大权匹配问题。