二分图的最大权完美匹配（Kuhn-Munkres 算法 / 匈牙利算法扩展）
字数 3269 2025-12-05 13:03:31

二分图的最大权完美匹配（Kuhn-Munkres 算法 / 匈牙利算法扩展）

题目描述
给定一个完全二分图 \(G = (X, Y, E)\)，其中 \(|X| = |Y| = n\)，每条边 \((i, j)\) 有一个权重 \(w_{ij}\)。目标是找到一个完美匹配（每个顶点恰好与另一部的一个顶点匹配），使得匹配中所有边的权重之和最大（或最小）。这个问题也称为指派问题。我们将讨论其求解的经典算法——Kuhn-Munkres 算法（又称匈牙利算法），并聚焦于最大权版本。

解题过程循序渐进讲解

步骤1：问题转换
若原问题是最小权完美匹配，可将所有权重取负，转化为最大权问题。因此我们只需讨论最大权版本。
Kuhn-Munkres 算法的核心思想是：通过维护顶点标号（顶标）和等价子图，将最大权匹配转化为等价子图上的最大基数匹配。

步骤2：概念定义

  • 顶标（label）：为每个顶点 \(u\) 分配一个数值 \(label(u)\)。在算法中，我们维护两组顶标 \(lx[i]\)（对 \(X\) 部顶点）和 \(ly[j]\)（对 \(Y\) 部顶点），满足对于任意边 \((i, j)\)，有

\[ lx[i] + ly[j] \ge w_{ij} \]

这称为可行性条件。

  • 相等子图（equality subgraph）：由所有满足 \(lx[i] + ly[j] = w_{ij}\) 的边 \((i, j)\) 组成的子图。在相等子图中，我们尝试寻找完美匹配。

关键定理：若在某个可行顶标下，相等子图存在完美匹配，则该匹配即为原图的一个最大权完美匹配。

步骤3：算法框架
算法迭代改进顶标，并不断在相等子图中寻找更大匹配，直到找到完美匹配。步骤如下：

  1. 初始化顶标：
    对 \(X\) 部顶点，令 \(lx[i] = \max_{j} w_{ij}\)（即每行最大值）。
    对 \(Y\) 部顶点，令 \(ly[j] = 0\)。
    这样，可行性条件 \(lx[i] + ly[j] \ge w_{ij}\) 成立（因为 \(lx[i]\) 至少等于该边的权重）。

  2. 在相等子图中，尝试寻找完美匹配（使用类似匈牙利算法寻找最大匹配）。
    设当前匹配为 \(M\)。若 \(M\) 已是完美匹配，算法结束。

  3. 若未找到完美匹配，则选择 \(X\) 部一个未匹配点 \(u\) 作为起点，尝试在相等子图中寻找增广路。
    搜索过程中，标记访问过的顶点集合：
    \(S \subseteq X\)（从 \(u\) 出发能通过交错路到达的 \(X\) 部顶点），
    \(T \subseteq Y\)（从 \(u\) 出发能到达的 \(Y\) 部顶点）。

  4. 若找到增广路，则沿增广路扩充匹配，返回步骤2。

  5. 若未找到增广路，则调整顶标以扩大相等子图：
    计算松弛量

\[ \alpha = \min_{i \in S, j \notin T} \{ lx[i] + ly[j] - w_{ij} \} \]

注意，由可行性条件，\(\alpha > 0\)。
然后更新顶标：

  • 对 \(i \in S\)，\(lx[i] := lx[i] - \alpha\)
  • 对 \(j \in T\)，\(ly[j] := ly[j] + \alpha\)
    这个调整保持可行性条件，且至少将一条新边（满足 \(i \in S, j \notin T\) 且 \(lx[i] + ly[j] - w_{ij} = \alpha\)）加入相等子图，同时不破坏已有相等子图中的边（因为对 \(i \in S, j \in T\) 的边，\(lx[i] + ly[j]\) 不变）。
  1. 重复步骤3~5，直到匹配包含 \(n\) 条边。

步骤4：例子演示
考虑一个2×2的例子，权重矩阵：

\[\begin{bmatrix} 3 & 1 \\ 2 & 4 \\ \end{bmatrix} \]

求最大权完美匹配。

  1. 初始化：
    \(lx = [3, 4]\)（每行最大值），\(ly = [0, 0]\)。
    相等子图包含边：
    (1,1)：3+0=3 ✅
    (2,2)：4+0=4 ✅
    其他边不满足等式。
    匹配：空。

  2. 从未匹配点 \(X1\) 开始搜索：
    \(S = \{X1\}\)，看 \(Y1\)（边(1,1)在相等子图中），将 \(Y1\) 加入 \(T = \{Y1\}\)，\(Y1\) 未匹配，找到增广路 \(X1 - Y1\)，匹配 \(M = \{(X1,Y1)\}\)。

  3. 从未匹配点 \(X2\) 开始搜索：
    \(S = \{X2\}\)，看 \(Y2\)（边(2,2)在相等子图中），将 \(Y2\) 加入 \(T = \{Y2\}\)，\(Y2\) 未匹配，找到增广路 \(X2 - Y2\)，匹配 \(M = \{(X1,Y1),(X2,Y2)\}\)，已是完美匹配，权重和=3+4=7（最大）。

但为演示顶标调整，假设第一步匹配了 \((X1,Y1)\) 后，从 \(X2\) 搜索时，若相等子图中 \((X2, Y2)\) 不在相等子图（假设权重矩阵不同），则需要调整顶标。我们换一个需要调整的例子。

换例：矩阵

\[\begin{bmatrix} 2 & 1 \\ 1 & 2 \\ \end{bmatrix} \]

  1. 初始化：\(lx = [2, 2]\)，\(ly = [0,0]\)。
    相等子图：边(1,1)：2+0=2 ✅，(2,2)：2+0=2 ✅。
    匹配 \((X1,Y1)\)。

  2. 从 \(X2\) 搜索：
    \(S = \{X2\}\)，看 \(Y2\)（在相等子图），\(T = \{Y2\}\)，\(Y2\) 未匹配，匹配 \((X2,Y2)\)，得到完美匹配，权重和=2+2=4。

若矩阵为：

\[\begin{bmatrix} 1 & 2 \\ 2 & 1 \\ \end{bmatrix} \]

  1. 初始化：\(lx = [2, 2]\)，\(ly = [0,0]\)。
    相等子图：边(1,2)：2+0=2 ✅，(2,1)：2+0=2 ✅。
    从 \(X1\) 出发匹配 \((X1,Y2)\)。

  2. 从 \(X2\) 搜索：
    \(S = \{X2\}\)，看 \(Y1\)（在相等子图），将 \(Y1\) 加入 \(T\)，\(Y1\) 未匹配，匹配 \((X2,Y1)\)，得到完美匹配，权重和=2+2=4。

可见初始化后相等子图已包含完美匹配。

步骤5：算法复杂度与注意事项

  • 每次顶标调整至少将一个 \(Y\) 部顶点加入 \(T\)，因此最多调整 \(O(n)\) 次顶标。
  • 每次调整后重新搜索增广路，可用 BFS/DFS 实现，单次 \(O(n^2)\)。
  • 总复杂度 \(O(n^3)\)。
  • 对于非完全二分图，可补权重为0的边（对最大权）或权重为 \(-\infty\) 的边（对最小权，但需特殊处理）。
  • 实际实现常用“松弛 Slack” 数组优化 \(\alpha\) 的计算，将复杂度优化到 \(O(n^3)\)。

总结
Kuhn-Munkres 算法通过可行顶标和相等子图，将最大权完美匹配问题转化为一系列最大基数匹配问题，通过顶标调整逐步引入新边，最终找到最优解。这个算法是组合优化中指派问题的经典解法，也可用于解决许多任务分配、资源调度的实际问题。

二分图的最大权完美匹配（Kuhn-Munkres 算法 / 匈牙利算法扩展） 题目描述 给定一个完全二分图 \( G = (X, Y, E) \)，其中 \( |X| = |Y| = n \)，每条边 \( (i, j) \) 有一个权重 \( w_ {ij} \)。目标是找到一个 完美匹配 （每个顶点恰好与另一部的一个顶点匹配），使得匹配中所有边的权重之和最大（或最小）。这个问题也称为 指派问题 。我们将讨论其求解的经典算法——Kuhn-Munkres 算法（又称匈牙利算法），并聚焦于最大权版本。 解题过程循序渐进讲解 步骤1：问题转换 若原问题是最小权完美匹配，可将所有权重取负，转化为最大权问题。因此我们只需讨论最大权版本。 Kuhn-Munkres 算法的核心思想是：通过维护顶点标号（顶标）和等价子图，将最大权匹配转化为等价子图上的最大基数匹配。 步骤2：概念定义 顶标（label） ：为每个顶点 \( u \) 分配一个数值 \( label(u) \)。在算法中，我们维护两组顶标 \( lx[ i] \)（对 \( X \) 部顶点）和 \( ly[ j ] \)（对 \( Y \) 部顶点），满足对于任意边 \( (i, j) \)，有 \[ lx[ i] + ly[ j] \ge w_ {ij} \] 这称为 可行性条件 。 相等子图（equality subgraph） ：由所有满足 \( lx[ i] + ly[ j] = w_ {ij} \) 的边 \( (i, j) \) 组成的子图。在相等子图中，我们尝试寻找完美匹配。 关键定理 ：若在某个可行顶标下，相等子图存在完美匹配，则该匹配即为原图的一个 最大权完美匹配 。 步骤3：算法框架 算法迭代改进顶标，并不断在相等子图中寻找更大匹配，直到找到完美匹配。步骤如下： 初始化顶标： 对 \( X \) 部顶点，令 \( lx[ i] = \max_ {j} w_ {ij} \)（即每行最大值）。 对 \( Y \) 部顶点，令 \( ly[ j ] = 0 \)。 这样，可行性条件 \( lx[ i] + ly[ j] \ge w_ {ij} \) 成立（因为 \( lx[ i ] \) 至少等于该边的权重）。 在相等子图中，尝试寻找完美匹配（使用类似匈牙利算法寻找最大匹配）。 设当前匹配为 \( M \)。若 \( M \) 已是完美匹配，算法结束。 若未找到完美匹配，则选择 \( X \) 部一个未匹配点 \( u \) 作为起点，尝试在相等子图中寻找增广路。 搜索过程中，标记访问过的顶点集合： \( S \subseteq X \)（从 \( u \) 出发能通过交错路到达的 \( X \) 部顶点）， \( T \subseteq Y \)（从 \( u \) 出发能到达的 \( Y \) 部顶点）。 若找到增广路，则沿增广路扩充匹配，返回步骤2。 若未找到增广路，则调整顶标以扩大相等子图： 计算松弛量 \[ \alpha = \min_ {i \in S, j \notin T} \{ lx[ i] + ly[ j] - w_ {ij} \} \] 注意，由可行性条件，\( \alpha > 0 \)。 然后更新顶标： 对 \( i \in S \)，\( lx[ i] := lx[ i ] - \alpha \) 对 \( j \in T \)，\( ly[ j] := ly[ j ] + \alpha \) 这个调整保持可行性条件，且至少将一条新边（满足 \( i \in S, j \notin T \) 且 \( lx[ i] + ly[ j] - w_ {ij} = \alpha \)）加入相等子图，同时不破坏已有相等子图中的边（因为对 \( i \in S, j \in T \) 的边，\( lx[ i] + ly[ j ] \) 不变）。 重复步骤3~5，直到匹配包含 \( n \) 条边。 步骤4：例子演示 考虑一个2×2的例子，权重矩阵： \[ \begin{bmatrix} 3 & 1 \\ 2 & 4 \\ \end{bmatrix} \] 求最大权完美匹配。 初始化： \( lx = [ 3, 4] \)（每行最大值），\( ly = [ 0, 0 ] \)。 相等子图包含边： (1,1)：3+0=3 ✅ (2,2)：4+0=4 ✅ 其他边不满足等式。 匹配：空。 从未匹配点 \( X1 \) 开始搜索： \( S = \{X1\} \)，看 \( Y1 \)（边(1,1)在相等子图中），将 \( Y1 \) 加入 \( T = \{Y1\} \)，\( Y1 \) 未匹配，找到增广路 \( X1 - Y1 \)，匹配 \( M = \{(X1,Y1)\} \)。 从未匹配点 \( X2 \) 开始搜索： \( S = \{X2\} \)，看 \( Y2 \)（边(2,2)在相等子图中），将 \( Y2 \) 加入 \( T = \{Y2\} \)，\( Y2 \) 未匹配，找到增广路 \( X2 - Y2 \)，匹配 \( M = \{(X1,Y1),(X2,Y2)\} \)，已是完美匹配，权重和=3+4=7（最大）。 但为演示顶标调整，假设第一步匹配了 \( (X1,Y1) \) 后，从 \( X2 \) 搜索时，若相等子图中 \( (X2, Y2) \) 不在相等子图（假设权重矩阵不同），则需要调整顶标。我们换一个需要调整的例子。 换例 ：矩阵 \[ \begin{bmatrix} 2 & 1 \\ 1 & 2 \\ \end{bmatrix} \] 初始化：\( lx = [ 2, 2] \)，\( ly = [ 0,0 ] \)。 相等子图：边(1,1)：2+0=2 ✅，(2,2)：2+0=2 ✅。 匹配 \( (X1,Y1) \)。 从 \( X2 \) 搜索： \( S = \{X2\} \)，看 \( Y2 \)（在相等子图），\( T = \{Y2\} \)，\( Y2 \) 未匹配，匹配 \( (X2,Y2) \)，得到完美匹配，权重和=2+2=4。 若矩阵为： \[ \begin{bmatrix} 1 & 2 \\ 2 & 1 \\ \end{bmatrix} \] 初始化：\( lx = [ 2, 2] \)，\( ly = [ 0,0 ] \)。 相等子图：边(1,2)：2+0=2 ✅，(2,1)：2+0=2 ✅。 从 \( X1 \) 出发匹配 \( (X1,Y2) \)。 从 \( X2 \) 搜索： \( S = \{X2\} \)，看 \( Y1 \)（在相等子图），将 \( Y1 \) 加入 \( T \)，\( Y1 \) 未匹配，匹配 \( (X2,Y1) \)，得到完美匹配，权重和=2+2=4。 可见初始化后相等子图已包含完美匹配。 步骤5：算法复杂度与注意事项 每次顶标调整至少将一个 \( Y \) 部顶点加入 \( T \)，因此最多调整 \( O(n) \) 次顶标。 每次调整后重新搜索增广路，可用 BFS/DFS 实现，单次 \( O(n^2) \)。 总复杂度 \( O(n^3) \)。 对于非完全二分图，可补权重为0的边（对最大权）或权重为 \(-\infty\) 的边（对最小权，但需特殊处理）。 实际实现常用“松弛 Slack” 数组优化 \( \alpha \) 的计算，将复杂度优化到 \( O(n^3) \)。 总结 Kuhn-Munkres 算法通过可行顶标和相等子图，将最大权完美匹配问题转化为一系列最大基数匹配问题，通过顶标调整逐步引入新边，最终找到最优解。这个算法是组合优化中指派问题的经典解法，也可用于解决许多任务分配、资源调度的实际问题。