带权二分图的最大权匹配问题（Kuhn-Munkres / Hungarian 算法）
字数 5173 2025-12-16 07:32:40

好的，我随机挑选一个你未讲过的图论算法题目。

带权二分图的最大权匹配问题（Kuhn-Munkres / Hungarian 算法）

题目描述

我们有一个带权的完全二分图。也就是说，图的两个顶点集 \(X\) 和 \(Y\) 大小相等（假设为 \(n\)），并且 \(X\) 中的每个顶点与 \(Y\) 中的每个顶点都有一条边相连，每条边 \((i, j)\) 都有一个权重 \(w(i, j)\)（可以是正数、零或负数，但通常我们处理非负值或可以转化为非负值的场景）。目标是从这个二分图中找到一个完美匹配（即每个顶点都恰好被匹配一次），使得这个完美匹配中所有边的权重之和最大。

形式化定义：给定一个 \(n \times n\) 的权重矩阵 \(W\)，其中 \(W_{ij}\) 表示左边第 \(i\) 个顶点与右边第 \(j\) 个顶点之间的权重。寻找一个排列 \(\pi: \{1, ..., n\} \to \{1, ..., n\}\)，使得总和 \(\sum_{i=1}^{n} W_{i, \pi(i)}\) 最大化。

为什么是“算法”而不仅仅是概念？

因为直接穷举所有 \(n!\) 种完美匹配在 \(n\) 较大时是不可行的。Kuhn-Munkres算法（也称为匈牙利算法）能够在多项式时间 \(O(n^3)\) 内精确地解决此问题。

解题思路演进

这个算法的核心思想非常巧妙：它通过不断地调整一组“顶标”和寻找“相等子图”中的最大匹配，最终使得相等子图中存在完美匹配，而这个完美匹配就是原图的最大权匹配。

为了让你彻底理解，我们按以下步骤进行：

第1步：关键概念引入——顶标与相等子图

首先，我们需要定义两个重要的辅助工具：

  1. 顶标：我们为左边每个顶点 \(i\) 分配一个“标杆值” \(labelX[i]\)，为右边每个顶点 \(j\) 分配一个“标杆值” \(labelY[j]\)。初始时，我们可以令 \(labelX[i] = \max_{j} W_{ij}\)（即第 \(i\) 行最大值），\(labelY[j] = 0\)。这个赋值满足一个可行性条件：

\[labelX[i] + labelY[j] \ge W_{ij}, \quad \forall i, j \]

这个条件的直观意思是：我们给左边顶点标了一个很高的“期望值”，给右边顶点标了0，任何一对顶点标杆之和都大于等于它们之间的实际权重。
  1. 相等子图：给定一组顶标，我们定义一个新的图，称为相等子图 \(G_l\)。\(G_l\) 包含原图所有顶点，但只包含那些满足以下等式的边：

\[labelX[i] + labelY[j] = W_{ij} \]

也就是说，在相等子图中，只保留那些“标杆之和刚好等于实际边权”的边。

核心定理：如果我们在某个相等子图 \(G_l\) 中，能够找到一个完美匹配（覆盖所有顶点），那么这个完美匹配就是原带权二分图的最大权完美匹配，并且其总权重等于所有顶标之和 \(\sum(labelX) + \sum(labelY)\)。

为什么？

  • 因为匹配中的每条边 \((i, j)\) 都满足 \(labelX[i] + labelY[j] = W_{ij}\)，所以匹配的总权重等于所有顶标之和。
  • 对于原图中任何其他完美匹配 \(M’\)，其总权重 \(\sum_{(i,j) \in M’} W_{ij} \le \sum_{(i,j) \in M’} (labelX[i] + labelY[j]) = \sum_i labelX[i] + \sum_j labelY[j]\)（因为可行性条件 \(W_{ij} \le labelX[i] + labelY[j]\) 始终成立）。
  • 所以，我们在相等子图中找到的完美匹配 \(M\) 的总权重，等于顶标和，而其他任何匹配的总权重都小于等于这个顶标和。因此 \(M\) 就是最大权匹配。

所以，我们的目标转化为：如何调整顶标，使得其对应的相等子图中包含一个完美匹配？

第2步：算法框架——基于增广路的调整

这是一个迭代过程，结合了无权二分图最大匹配（增广路算法）的思想：

  1. 初始化顶标，构造初始相等子图 \(G_l\)。
  2. 在当前的相等子图 \(G_l\) 中，尝试寻找一个完美匹配（例如使用DFS/BFS寻找增广路，就像无权二分图匹配那样）。
  3. 如果找到了完美匹配，算法结束，这就是答案。
  4. 如果没找到完美匹配，说明当前相等子图 \(G_l\) 的“连接”不够紧密，没有足够的边来形成完美匹配。这时，我们就需要调整顶标，在不破坏可行性条件的前提下，往相等子图中添加新的边。
  5. 调整顶标后，回到步骤2。

问题的关键就在于第4步：如何智能地调整顶标？

第3步：顶标调整的精细过程

假设我们在当前相等子图 \(G_l\) 中，执行了一次标准的匈牙利算法（寻找增广路），但没有为左边所有顶点都找到匹配。此时，我们会得到一个交错森林（类似于寻找增广路时访问过的顶点集合）。

让我们定义：

  • \(S\)：在交错森林中，左边已经访问过的顶点集合。
  • \(T\)：在交错森林中，右边已经访问过的顶点集合。
  • \(N(S)\)：集合 \(S\) 在相等子图 \(G_l\) 中的邻居集合（即所有通过相等子图的边与 \(S\) 中顶点相连的右边顶点）。注意，在我们执行匈牙利算法寻找增广路失败时，一定有 \(T = N(S)\)，并且 \(|T| < |S|\)（这是霍尔婚姻定理的体现：匹配失败的原因）。

我们需要添加新的边来“扩大” \(N(S)\)。我们需要找到一些“接近相等”的边，它们连接 \(S\) 和不在 \(T\) 中的右边顶点（即 \(Y \setminus T\)）。

考虑所有从 \(S\) 到 \(Y \setminus T\) 的边 \((i, j)\)。对于这些边，因为不在相等子图中，所以有：

\[labelX[i] + labelY[j] > W_{ij} \]

我们找出所有这些边中，\((labelX[i] + labelY[j]) - W_{ij}\) 的最小值，记作 \(delta\)。

\[delta = \min_{i \in S, j \notin T} \{labelX[i] + labelY[j] - W_{ij}\} \]

现在进行顶标调整：

  • 将所有左边顶点 \(i \in S\) 的顶标 \(labelX[i]\) 减去 \(delta\)。
  • 将所有右边顶点 \(j \in T\) 的顶标 \(labelY[j]\) 加上 \(delta\)。

这个调整的妙处：

  1. 保持可行性：
    • 对于边 \((i, j)\)，其中 \(i \in S, j \in T\)：\(labelX[i]\) 减 \(delta\)，\(labelY[j]\) 加 \(delta\)，总和不变，原来相等的仍然相等。
    • 对于边 \((i, j)\)，其中 \(i \notin S, j \notin T\)：顶标都没变，关系不变。
    • 对于边 \((i, j)\)，其中 \(i \notin S, j \in T\)：\(labelY[j]\) 增加了，不等式 \(labelX[i] + labelY[j] \ge W_{ij}\) 更可能成立，但不会破坏（因为原来就成立，右边变大更成立）。
    • 对于边 \((i, j)\)，其中 \(i \in S, j \notin T\)：这正是我们瞄准的边。调整后，新的顶标和为 \((labelX[i] - delta) + labelY[j] = (labelX[i] + labelY[j]) - delta\)。因为我们选的 \(delta\) 是这些边差距的最小值，所以调整后，至少有一条这样的边 \((i, j)\) 满足了等式 \(labelX[i] + labelY[j] = W_{ij}\)！也就是说，至少有一条新边被加入了相等子图，而且这条边连接了 \(S\) 和 \(Y \setminus T\)，从而可能扩大我们的交错森林，为找到新的增广路创造了条件。
  2. 优化目标：所有顶标的总和减少了 \(|S| * delta\)，增加了 \(|T| * delta\)。因为 \(|S| > |T|\)，所以总顶标和减少了 \((|S| - |T|) * delta\)。这意味着我们每次调整都在向最优解（最大权匹配的总权重）逼近，因为最终找到的完美匹配总权重等于最终顶标和，而我们每一步都在降低这个顶标和的上界。

第4步：算法步骤总结

我们可以把上述过程整理成一个清晰的 \(O(n^3)\) 算法步骤：

  1. 初始化：

    • \(labelX[i] = \max_{j} W_{ij}\), for \(i = 1...n\).
    • \(labelY[j] = 0\), for \(j = 1...n\).
    • 初始化匹配：\(matchX[i] = -1\)（左边\(i\)的配偶），\(matchY[j] = -1\)（右边\(j\)的配偶）。

  2. 对于左边每一个尚未匹配的顶点 \(u\)，执行标准的匈牙利算法尝试寻找增广路，但在相等子图 \(G_l\) 中进行：

    • \(visitedX\), \(visitedY\) 数组标记本轮搜索访问过的顶点。
    • 用DFS/BFS从 \(u\) 出发，在相等子图中寻找增广路。判断边 \((i, j)\) 是否在相等子图中的条件是 \(labelX[i] + labelY[j] == W_{ij}\)。

  3. 如果为 \(u\) 找到了增广路：更新匹配，然后继续处理下一个未匹配的左边顶点。

  4. 如果没找到：这意味着我们遇到了瓶颈，需要调整顶标。

    • 根据本次DFS/BFS访问到的顶点，确定集合 \(S\)（访问过的左边点）和 \(T\)（访问过的右边点）。
    • 计算 \(delta = \min_{i \in S, j \notin T} \{labelX[i] + labelY[j] - W_{ij}\}\)。
    • 调整顶标：
      • \(\forall i \in S, labelX[i] -= delta\).
      • \(\forall j \in T, labelY[j] += delta\).
    • 关键优化：调整顶标后，相等子图扩大了，但交错森林的结构（\(S\) 和 \(T\) 中的顶点）并没有被破坏，而且新加入的边可能让我们在当前轮次（针对同一个 \(u\)）的DFS/BFS中继续扩展。因此，我们不需要重置搜索，而是可以继续以当前的 \(visited\) 状态和交错森林为基础，重新尝试为 \(u\) 寻找增广路。这一步的优化保证了每轮外循环（处理一个左边顶点 \(u\)）的复杂度是 \(O(n^2)\)。

  5. 重复步骤2-4，直到所有左边顶点都被匹配，我们就得到了最大权完美匹配。

一个微型例子

假设权重矩阵为：

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

左边顶点 \(X_1, X_2\)，右边 \(Y_1, Y_2\)。

  1. 初始化：\(labelX = [2, 4]\), \(labelY = [0, 0]\)。
  2. 相等子图边：满足 \(labelX[i]+labelY[j]=W_{ij}\)。
    • \(X_1\): \(2+0=2\) (边 \(X_1-Y_1\))，\(2+0 \neq 1\)。所以边 \((X_1, Y_1)\) 在相等子图。
    • \(X_2\): \(4+0 \neq 3\), \(4+0=4\) (边 \(X_2-Y_2\))。所以边 \((X_2, Y_2)\) 在相等子图。
  3. 找匹配：先匹配 \(X_1 \to Y_1\)。尝试匹配 \(X_2 \to Y_2\)，成功。完美匹配已经找到！匹配是 \((X_1, Y_1)\) 和 \((X_2, Y_2)\)，总权重 \(2+4=6\)。
  4. 验证：另一个完美匹配 \((X_1, Y_2)\) 和 \((X_2, Y_1)\) 总权重 \(1+3=4 < 6\)。所以确实是最大权匹配。

这个例子太简单，一次成功。更复杂的例子会经历顶标调整过程。

总结

Kuhn-Munkres算法的精髓在于：

  • 通过引入可行性顶标，将最大权问题与在特定子图（相等子图）中寻找完美匹配的问题联系起来。
  • 利用无权二分图匹配的增广路算法作为子过程。
  • 当增广失败时，通过计算最小差值 \(delta\) 并调整顶标，智能地向相等子图中添加必要的新边，同时保证算法朝着最优解的方向前进。
  • 利用调整后搜索状态可继承的优化，将总复杂度控制在 \(O(n^3)\)。

希望这个从动机、概念、定理到具体步骤的讲解，能帮助你完全掌握这个经典且优美的组合优化算法。

好的，我随机挑选一个你未讲过的图论算法题目。 带权二分图的最大权匹配问题（Kuhn-Munkres / Hungarian 算法） 题目描述 我们有一个 带权的完全二分图 。也就是说，图的两个顶点集 $X$ 和 $Y$ 大小相等（假设为 $n$），并且 $X$ 中的每个顶点与 $Y$ 中的每个顶点都有一条边相连，每条边 $(i, j)$ 都有一个权重 $w(i, j)$（可以是正数、零或负数，但通常我们处理非负值或可以转化为非负值的场景）。目标是从这个二分图中找到一个 完美匹配 （即每个顶点都恰好被匹配一次），使得这个完美匹配中所有边的权重之和 最大 。 形式化定义 ：给定一个 $n \times n$ 的权重矩阵 $W$，其中 $W_ {ij}$ 表示左边第 $i$ 个顶点与右边第 $j$ 个顶点之间的权重。寻找一个排列 $\pi: \{1, ..., n\} \to \{1, ..., n\}$，使得总和 $\sum_ {i=1}^{n} W_ {i, \pi(i)}$ 最大化。 为什么是“算法”而不仅仅是概念？ 因为直接穷举所有 $n !$ 种完美匹配在 $n$ 较大时是不可行的。Kuhn-Munkres算法（也称为匈牙利算法）能够在多项式时间 $O(n^3)$ 内精确地解决此问题。 解题思路演进 这个算法的核心思想非常巧妙：它通过不断地调整一组“顶标”和寻找“相等子图”中的最大匹配，最终使得相等子图中存在完美匹配，而这个完美匹配就是原图的最大权匹配。 为了让你彻底理解，我们按以下步骤进行： 第1步：关键概念引入——顶标与相等子图 首先，我们需要定义两个重要的辅助工具： 顶标 ：我们为左边每个顶点 $i$ 分配一个“标杆值” $labelX[ i]$，为右边每个顶点 $j$ 分配一个“标杆值” $labelY[ j]$。初始时，我们可以令 $labelX[ i] = \max_ {j} W_ {ij}$（即第 $i$ 行最大值），$labelY[ j] = 0$。这个赋值满足一个 可行性条件 ： $$labelX[ i] + labelY[ j] \ge W_ {ij}, \quad \forall i, j$$ 这个条件的直观意思是：我们给左边顶点标了一个很高的“期望值”，给右边顶点标了0，任何一对顶点标杆之和都大于等于它们之间的实际权重。 相等子图 ：给定一组顶标，我们定义一个新的图，称为相等子图 $G_ l$。$G_ l$ 包含原图所有顶点，但只包含那些满足以下等式的边： $$labelX[ i] + labelY[ j] = W_ {ij}$$ 也就是说，在相等子图中，只保留那些“标杆之和刚好等于实际边权”的边。 核心定理 ：如果我们在某个相等子图 $G_ l$ 中，能够找到一个 完美匹配 （覆盖所有顶点），那么这个完美匹配就是原带权二分图的 最大权完美匹配 ，并且其总权重等于所有顶标之和 $\sum(labelX) + \sum(labelY)$。 为什么？ 因为匹配中的每条边 $(i, j)$ 都满足 $labelX[ i] + labelY[ j] = W_ {ij}$，所以匹配的总权重等于所有顶标之和。 对于原图中 任何其他 完美匹配 $M’$，其总权重 $\sum_ {(i,j) \in M’} W_ {ij} \le \sum_ {(i,j) \in M’} (labelX[ i] + labelY[ j]) = \sum_ i labelX[ i] + \sum_ j labelY[ j]$（因为可行性条件 $W_ {ij} \le labelX[ i] + labelY[ j ]$ 始终成立）。 所以，我们在相等子图中找到的完美匹配 $M$ 的总权重，等于顶标和，而其他任何匹配的总权重都 小于等于 这个顶标和。因此 $M$ 就是最大权匹配。 所以，我们的目标转化为： 如何调整顶标，使得其对应的相等子图中包含一个完美匹配？ 第2步：算法框架——基于增广路的调整 这是一个迭代过程，结合了无权二分图最大匹配（增广路算法）的思想： 初始化顶标 ，构造初始相等子图 $G_ l$。 在当前的相等子图 $G_ l$ 中，尝试寻找一个完美匹配（例如使用DFS/BFS寻找增广路，就像无权二分图匹配那样）。 如果找到了完美匹配，算法结束，这就是答案。 如果没找到完美匹配，说明当前相等子图 $G_ l$ 的“连接”不够紧密，没有足够的边来形成完美匹配。这时，我们就需要 调整顶标 ，在不破坏可行性条件的前提下，往相等子图中 添加新的边 。 调整顶标后，回到步骤2。 问题的关键就在于第4步： 如何智能地调整顶标？ 第3步：顶标调整的精细过程 假设我们在当前相等子图 $G_ l$ 中，执行了一次标准的匈牙利算法（寻找增广路），但没有为左边所有顶点都找到匹配。此时，我们会得到一个 交错森林 （类似于寻找增广路时访问过的顶点集合）。 让我们定义： $S$：在交错森林中，左边 已经访问过 的顶点集合。 $T$：在交错森林中，右边 已经访问过 的顶点集合。 $N(S)$：集合 $S$ 在相等子图 $G_ l$ 中的邻居集合（即所有通过相等子图的边与 $S$ 中顶点相连的右边顶点）。注意，在我们执行匈牙利算法寻找增广路失败时，一定有 $T = N(S)$，并且 $|T| < |S|$（这是霍尔婚姻定理的体现：匹配失败的原因）。 我们需要添加新的边来“扩大” $N(S)$。我们需要找到一些“接近相等”的边，它们连接 $S$ 和不在 $T$ 中的右边顶点（即 $Y \setminus T$）。 考虑所有从 $S$ 到 $Y \setminus T$ 的边 $(i, j)$。对于这些边，因为不在相等子图中，所以有： $$labelX[ i] + labelY[ j] > W_ {ij}$$ 我们找出所有这些边中，$(labelX[ i] + labelY[ j]) - W_ {ij}$ 的最小值，记作 $delta$。 $$ delta = \min_ {i \in S, j \notin T} \{labelX[ i] + labelY[ j] - W_ {ij}\} $$ 现在进行顶标调整 ： 将所有左边顶点 $i \in S$ 的顶标 $labelX[ i]$ 减去 $delta$。 将所有右边顶点 $j \in T$ 的顶标 $labelY[ j]$ 加上 $delta$。 这个调整的妙处 ： 保持可行性 ： 对于边 $(i, j)$，其中 $i \in S, j \in T$：$labelX[ i]$ 减 $delta$，$labelY[ j ]$ 加 $delta$，总和不变，原来相等的仍然相等。 对于边 $(i, j)$，其中 $i \notin S, j \notin T$：顶标都没变，关系不变。 对于边 $(i, j)$，其中 $i \notin S, j \in T$：$labelY[ j]$ 增加了，不等式 $labelX[ i] + labelY[ j] \ge W_ {ij}$ 更可能成立，但不会破坏（因为原来就成立，右边变大更成立）。 对于边 $(i, j)$，其中 $i \in S, j \notin T$：这正是我们瞄准的边。调整后，新的顶标和为 $(labelX[ i] - delta) + labelY[ j] = (labelX[ i] + labelY[ j]) - delta$。因为我们选的 $delta$ 是这些边差距的最小值，所以调整后，至少有一条这样的边 $(i, j)$ 满足了等式 $labelX[ i] + labelY[ j] = W_ {ij}$！也就是说， 至少有一条新边被加入了相等子图 ，而且这条边连接了 $S$ 和 $Y \setminus T$，从而可能扩大我们的交错森林，为找到新的增广路创造了条件。 优化目标 ：所有顶标的总和减少了 $|S| * delta$，增加了 $|T| * delta$。因为 $|S| > |T|$，所以总顶标和减少了 $(|S| - |T|) * delta$。这意味着我们每次调整都在向最优解（最大权匹配的总权重） 逼近 ，因为最终找到的完美匹配总权重等于最终顶标和，而我们每一步都在降低这个顶标和的上界。 第4步：算法步骤总结 我们可以把上述过程整理成一个清晰的 $O(n^3)$ 算法步骤： 初始化 ： $labelX[ i] = \max_ {j} W_ {ij}$, for $i = 1...n$. $labelY[ j ] = 0$, for $j = 1...n$. 初始化匹配：$matchX[ i] = -1$（左边$i$的配偶），$matchY[ j ] = -1$（右边$j$的配偶）。 对于左边每一个尚未匹配的顶点 $u$，执行 标准的匈牙利算法尝试寻找增广路 ，但在相等子图 $G_ l$ 中进行： $visitedX$, $visitedY$ 数组标记本轮搜索访问过的顶点。 用DFS/BFS从 $u$ 出发，在相等子图中寻找增广路。判断边 $(i, j)$ 是否在相等子图中的条件是 $labelX[ i] + labelY[ j] == W_ {ij}$。 如果为 $u$ 找到了增广路 ：更新匹配，然后继续处理下一个未匹配的左边顶点。 如果没找到 ：这意味着我们遇到了瓶颈，需要调整顶标。 根据本次DFS/BFS访问到的顶点，确定集合 $S$（访问过的左边点）和 $T$（访问过的右边点）。 计算 $delta = \min_ {i \in S, j \notin T} \{labelX[ i] + labelY[ j] - W_ {ij}\}$。 调整顶标： $\forall i \in S, labelX[ i ] -= delta$. $\forall j \in T, labelY[ j ] += delta$. 关键优化 ：调整顶标后，相等子图扩大了， 但交错森林的结构（$S$ 和 $T$ 中的顶点）并没有被破坏 ，而且新加入的边可能让我们在当前轮次（针对同一个 $u$）的DFS/BFS中继续扩展。因此，我们 不需要重置搜索 ，而是可以继续以当前的 $visited$ 状态和交错森林为基础，重新尝试为 $u$ 寻找增广路。这一步的优化保证了每轮外循环（处理一个左边顶点 $u$）的复杂度是 $O(n^2)$。 重复步骤2-4，直到所有左边顶点都被匹配，我们就得到了最大权完美匹配。 一个微型例子 假设权重矩阵为： $$ W = \begin{bmatrix} 2 & 1 \\ 3 & 4 \end{bmatrix} $$ 左边顶点 $X_ 1, X_ 2$，右边 $Y_ 1, Y_ 2$。 初始化：$labelX = [ 2, 4]$, $labelY = [ 0, 0 ]$。 相等子图边：满足 $labelX[ i]+labelY[ j]=W_ {ij}$。 $X_ 1$: $2+0=2$ (边 $X_ 1-Y_ 1$)，$2+0 \neq 1$。所以边 $(X_ 1, Y_ 1)$ 在相等子图。 $X_ 2$: $4+0 \neq 3$, $4+0=4$ (边 $X_ 2-Y_ 2$)。所以边 $(X_ 2, Y_ 2)$ 在相等子图。 找匹配：先匹配 $X_ 1 \to Y_ 1$。尝试匹配 $X_ 2 \to Y_ 2$，成功。 完美匹配已经找到 ！匹配是 $(X_ 1, Y_ 1)$ 和 $(X_ 2, Y_ 2)$，总权重 $2+4=6$。 验证：另一个完美匹配 $(X_ 1, Y_ 2)$ 和 $(X_ 2, Y_ 1)$ 总权重 $1+3=4 < 6$。所以确实是最大权匹配。 这个例子太简单，一次成功。更复杂的例子会经历顶标调整过程。 总结 Kuhn-Munkres算法的精髓在于： 通过引入 可行性顶标 ，将最大权问题与在特定子图（ 相等子图 ）中寻找完美匹配的问题联系起来。 利用无权二分图匹配的 增广路算法 作为子过程。 当增广失败时，通过计算最小差值 $delta$ 并 调整顶标 ，智能地向相等子图中添加必要的新边，同时保证算法朝着最优解的方向前进。 利用调整后搜索状态可继承的 优化 ，将总复杂度控制在 $O(n^3)$。 希望这个从动机、概念、定理到具体步骤的讲解，能帮助你完全掌握这个经典且优美的组合优化算法。