基于线性规划的图最小成本最大匹配问题的原始-对偶近似算法求解示例
字数 3736 2025-12-19 23:00:08

基于线性规划的图最小成本最大匹配问题的原始-对偶近似算法求解示例

题目描述

考虑一个无向二分图 \(G = (U, V, E)\)，其中 \(U\) 和 \(V\) 是两个不相交的顶点集，\(E \subseteq U \times V\) 是边集。每条边 \(e = (u, v)\) 关联一个非负成本 \(c_e\)。目标是找到一个最大基数匹配（即匹配尽可能多的顶点对），且在所有最大基数匹配中，使得匹配边的总成本最小。这是一个经典的组合优化问题，称为最小成本最大匹配问题。我们将设计一个基于线性规划的原始-对偶近似算法来求解它，并解释其工作原理。

解题过程

步骤1：建立整数线性规划模型

我们引入决策变量 \(x_e\) 表示边 \(e\) 是否被选入匹配：

\[x_e = \begin{cases} 1 & \text{如果边 } e \text{ 在匹配中} \\ 0 & \text{否则} \end{cases} \]

目标是最小化总成本 \(\sum_{e \in E} c_e x_e\)，同时满足匹配约束：每个顶点最多与一条匹配边相连。对于顶点 \(u \in U\) 和 \(v \in V\)，约束为：

\[\sum_{v \in V} x_{uv} \leq 1 \quad \forall u \in U, \quad \sum_{u \in U} x_{uv} \leq 1 \quad \forall v \in V \]

并且要求匹配是最大基数的。为了强制最大基数，我们需要一个额外的约束：匹配的边数等于最大可能匹配数 \(M^*\)。但 \(M^*\) 是未知的，因此我们改为分两步处理：先找到一个最大基数匹配（不关心成本），然后在此基础上优化成本。更优雅的方法是使用原始-对偶框架，它同时考虑最大基数和最小成本。

步骤2：线性规划松弛及其对偶

将整数约束 \(x_e \in \{0,1\}\) 松弛为 \(0 \leq x_e \leq 1\)，得到线性规划（原始问题）：

\[\begin{aligned} \text{最小化} \quad & \sum_{e \in E} c_e x_e \\ \text{满足} \quad & \sum_{v \in V} x_{uv} \leq 1 \quad \forall u \in U \\ & \sum_{u \in U} x_{uv} \leq 1 \quad \forall v \in V \\ & x_e \geq 0 \quad \forall e \in E \end{aligned} \]

注意：我们省略了 \(x_e \leq 1\)，因为它已被度数约束隐含（每个 \(x_e\) 最多出现在两个约束中，且每个约束右端为1）。

对偶问题引入变量 \(y_u\)（对应 \(U\) 中顶点约束）和 \(y_v\)（对应 \(V\) 中顶点约束），对偶线性规划为：

\[\begin{aligned} \text{最大化} \quad & \sum_{u \in U} y_u + \sum_{v \in V} y_v \\ \text{满足} \quad & y_u + y_v \leq c_e \quad \forall e = (u,v) \in E \\ & y_u \geq 0, \quad y_v \geq 0 \quad \forall u \in U, v \in V \end{aligned} \]

根据对偶理论，任何原始可行解的目标值至少等于任何对偶可行解的目标值（弱对偶性）。

步骤3：原始-对偶算法框架

原始-对偶算法通常从对偶可行解开始，逐步改进对偶变量，同时构建原始整数解（匹配）。该算法的核心思想是：

  1. 初始化对偶变量 \(y_u = y_v = 0\)，所有边都是“紧”的候选（即满足 \(y_u + y_v = c_e\) 的边）。
  2. 逐步增加对偶变量，使得更多边变紧（进入候选集），同时利用紧边构造匹配。
  3. 当构造出一个最大基数匹配时停止，并确保其成本接近最优。

但这里有一个挑战：我们需要同时保证匹配的最大基数和低成本。经典算法（如匈牙利算法）可以精确求解，但为了展示原始-对偶近似算法的思路，我们考虑一个变体：假设图中存在完美匹配（即 \(|U| = |V|\) 且存在匹配覆盖所有顶点），我们寻找最小成本的完美匹配。

步骤4：算法详细步骤（针对完美匹配情形）

假设 \(|U| = |V| = n\)，且存在完美匹配。算法步骤如下：

初始化：

  • 设对偶变量 \(y_u = y_v = 0\)。
  • 设匹配 \(M = \emptyset\)。
  • 定义紧边集合 \(E_t = \{ e = (u,v) \in E \mid y_u + y_v = c_e \}\)。

迭代过程：

  1. 在当前紧边子图 \(G_t = (U, V, E_t)\) 中寻找一个最大匹配 \(M'\)（使用任意多项式时间算法，如Hopcroft-Karp算法）。
  2. 如果 \(M'\) 是完美匹配（大小为 \(n\)），则转到步骤4。
  3. 否则，存在未匹配的顶点。设 \(U' \subseteq U\) 和 \(V' \subseteq V\) 分别是在 \(G_t\) 中未匹配的顶点集合（根据最大匹配定理，存在一个顶点覆盖使得未匹配顶点至少一端在覆盖中）。增加对偶变量以引入新的紧边：
    • 计算增量 \(\delta = \min\{ c_e - (y_u + y_v) \mid e = (u,v) \in E, u \notin U' \text{ 或 } v \notin V' \}\)（即连接已覆盖顶点和未覆盖顶点的边中，最小的“松弛”值）。
    • 对于所有 \(u \in U'\)，令 \(y_u \leftarrow y_u + \delta\)。
    • 对于所有 \(v \in V'\)，令 \(y_v \leftarrow y_v + \delta\)。
    • 更新紧边集合 \(E_t\)（现在包含更多边）。
  4. 重复步骤1-3直到找到完美匹配 \(M'\)。

输出：最终的完美匹配 \(M'\) 即为最小成本完美匹配。

步骤5：算法正确性与最优性说明

该算法本质上是匈牙利算法的对偶形式，对于二分图最小成本完美匹配问题是精确算法（不是近似算法）。为什么？

  • 每一步保持对偶可行性：增量 \(\delta\) 的选择确保对所有边 \(e = (u,v)\)，不等式 \(y_u + y_v \leq c_e\) 仍然成立。
  • 算法终止时，我们得到一个完美匹配 \(M'\) 和一组对偶变量 \(y\)。
  • 对于匹配 \(M'\) 中的每条边 \(e = (u,v)\)，由构造知它是紧边，即 \(y_u + y_v = c_e\)。
  • 因此，匹配的总成本 \(\sum_{e \in M'} c_e = \sum_{u \in U} y_u + \sum_{v \in V} y_v\)（因为每个顶点恰好被匹配一次）。
  • 根据对偶理论，对偶目标值 \(\sum_{u \in U} y_u + \sum_{v \in V} y_v\) 是原始成本的下界，而匹配成本等于该下界，所以匹配是最优的。

步骤6：扩展到最大基数最小成本匹配（近似算法版本）

如果不需要完美匹配，而是要求最大基数匹配中的最小成本，我们可以修改算法：

  1. 先忽略成本，找到一个最大基数匹配 \(M_{\text{max}}\)（基数 \(k\)）。
  2. 然后，在原图中仅考虑顶点子集：被 \(M_{\text{max}}\) 覆盖的顶点（共 \(2k\) 个顶点），以及它们之间的边。在这个子图上寻找最小成本完美匹配（因为子图中存在完美匹配，即 \(M_{\text{max}}\) 本身）。
  3. 在子图上运行上述原始-对偶算法，得到最小成本完美匹配，它也就是原图的最小成本最大基数匹配。

为什么这是精确的？：因为任何最大基数匹配都恰好覆盖这 \(2k\) 个顶点，所以我们只需在这些顶点上优化成本，问题归结为子图上的最小成本完美匹配。

总结

我们基于线性规划和对偶理论，设计了求解二分图最小成本最大匹配的原始-对偶算法。算法通过逐步调整对偶变量，在紧边子图中搜索最大匹配，直至找到完美匹配（或最大基数匹配）。该算法实际上是匈牙利算法的对偶视角，能够给出精确最优解，而不是近似解。这个例子展示了原始-对偶方法如何将组合优化问题与线性规划松弛紧密结合，通过巧妙维护对偶可行性来构造原始整数解。

基于线性规划的图最小成本最大匹配问题的原始-对偶近似算法求解示例 题目描述 考虑一个无向二分图 \( G = (U, V, E) \)，其中 \( U \) 和 \( V \) 是两个不相交的顶点集，\( E \subseteq U \times V \) 是边集。每条边 \( e = (u, v) \) 关联一个非负成本 \( c_ e \)。目标是找到一个 最大基数匹配 （即匹配尽可能多的顶点对），且在所有最大基数匹配中，使得匹配边的总成本最小。这是一个经典的组合优化问题，称为 最小成本最大匹配问题 。我们将设计一个基于线性规划的原始-对偶近似算法来求解它，并解释其工作原理。 解题过程 步骤1：建立整数线性规划模型 我们引入决策变量 \( x_ e \) 表示边 \( e \) 是否被选入匹配： \[ x_ e = \begin{cases} 1 & \text{如果边 } e \text{ 在匹配中} \\ 0 & \text{否则} \end{cases} \] 目标是最小化总成本 \(\sum_ {e \in E} c_ e x_ e\)，同时满足匹配约束：每个顶点最多与一条匹配边相连。对于顶点 \( u \in U \) 和 \( v \in V \)，约束为： \[ \sum_ {v \in V} x_ {uv} \leq 1 \quad \forall u \in U, \quad \sum_ {u \in U} x_ {uv} \leq 1 \quad \forall v \in V \] 并且要求匹配是 最大基数 的。为了强制最大基数，我们需要一个额外的约束：匹配的边数等于最大可能匹配数 \( M^* \)。但 \( M^* \) 是未知的，因此我们改为分两步处理：先找到一个最大基数匹配（不关心成本），然后在此基础上优化成本。更优雅的方法是使用原始-对偶框架，它同时考虑最大基数和最小成本。 步骤2：线性规划松弛及其对偶 将整数约束 \( x_ e \in \{0,1\} \) 松弛为 \( 0 \leq x_ e \leq 1 \)，得到线性规划（原始问题）： \[ \begin{aligned} \text{最小化} \quad & \sum_ {e \in E} c_ e x_ e \\ \text{满足} \quad & \sum_ {v \in V} x_ {uv} \leq 1 \quad \forall u \in U \\ & \sum_ {u \in U} x_ {uv} \leq 1 \quad \forall v \in V \\ & x_ e \geq 0 \quad \forall e \in E \end{aligned} \] 注意：我们省略了 \( x_ e \leq 1 \)，因为它已被度数约束隐含（每个 \( x_ e \) 最多出现在两个约束中，且每个约束右端为1）。 对偶问题引入变量 \( y_ u \)（对应 \( U \) 中顶点约束）和 \( y_ v \)（对应 \( V \) 中顶点约束），对偶线性规划为： \[ \begin{aligned} \text{最大化} \quad & \sum_ {u \in U} y_ u + \sum_ {v \in V} y_ v \\ \text{满足} \quad & y_ u + y_ v \leq c_ e \quad \forall e = (u,v) \in E \\ & y_ u \geq 0, \quad y_ v \geq 0 \quad \forall u \in U, v \in V \end{aligned} \] 根据对偶理论，任何原始可行解的目标值至少等于任何对偶可行解的目标值（弱对偶性）。 步骤3：原始-对偶算法框架 原始-对偶算法通常从对偶可行解开始，逐步改进对偶变量，同时构建原始整数解（匹配）。该算法的核心思想是： 初始化对偶变量 \( y_ u = y_ v = 0 \)，所有边都是“紧”的候选（即满足 \( y_ u + y_ v = c_ e \) 的边）。 逐步增加对偶变量，使得更多边变紧（进入候选集），同时利用紧边构造匹配。 当构造出一个最大基数匹配时停止，并确保其成本接近最优。 但这里有一个挑战：我们需要同时保证匹配的最大基数和低成本。经典算法（如匈牙利算法）可以精确求解，但为了展示原始-对偶近似算法的思路，我们考虑一个变体：假设图中存在完美匹配（即 \( |U| = |V| \) 且存在匹配覆盖所有顶点），我们寻找最小成本的完美匹配。 步骤4：算法详细步骤（针对完美匹配情形） 假设 \( |U| = |V| = n \)，且存在完美匹配。算法步骤如下： 初始化 ： 设对偶变量 \( y_ u = y_ v = 0 \)。 设匹配 \( M = \emptyset \)。 定义 紧边集合 \( E_ t = \{ e = (u,v) \in E \mid y_ u + y_ v = c_ e \} \)。 迭代过程 ： 在当前紧边子图 \( G_ t = (U, V, E_ t) \) 中寻找一个最大匹配 \( M' \)（使用任意多项式时间算法，如Hopcroft-Karp算法）。 如果 \( M' \) 是完美匹配（大小为 \( n \)），则转到步骤4。 否则，存在未匹配的顶点。设 \( U' \subseteq U \) 和 \( V' \subseteq V \) 分别是在 \( G_ t \) 中未匹配的顶点集合（根据最大匹配定理，存在一个顶点覆盖使得未匹配顶点至少一端在覆盖中）。增加对偶变量以引入新的紧边： 计算增量 \( \delta = \min\{ c_ e - (y_ u + y_ v) \mid e = (u,v) \in E, u \notin U' \text{ 或 } v \notin V' \} \)（即连接已覆盖顶点和未覆盖顶点的边中，最小的“松弛”值）。 对于所有 \( u \in U' \)，令 \( y_ u \leftarrow y_ u + \delta \)。 对于所有 \( v \in V' \)，令 \( y_ v \leftarrow y_ v + \delta \)。 更新紧边集合 \( E_ t \)（现在包含更多边）。 重复步骤1-3直到找到完美匹配 \( M' \)。 输出 ：最终的完美匹配 \( M' \) 即为最小成本完美匹配。 步骤5：算法正确性与最优性说明 该算法本质上是匈牙利算法的对偶形式，对于二分图最小成本完美匹配问题是精确算法（不是近似算法）。为什么？ 每一步保持对偶可行性：增量 \( \delta \) 的选择确保对所有边 \( e = (u,v) \)，不等式 \( y_ u + y_ v \leq c_ e \) 仍然成立。 算法终止时，我们得到一个完美匹配 \( M' \) 和一组对偶变量 \( y \)。 对于匹配 \( M' \) 中的每条边 \( e = (u,v) \)，由构造知它是紧边，即 \( y_ u + y_ v = c_ e \)。 因此，匹配的总成本 \( \sum_ {e \in M'} c_ e = \sum_ {u \in U} y_ u + \sum_ {v \in V} y_ v \)（因为每个顶点恰好被匹配一次）。 根据对偶理论，对偶目标值 \( \sum_ {u \in U} y_ u + \sum_ {v \in V} y_ v \) 是原始成本的下界，而匹配成本等于该下界，所以匹配是最优的。 步骤6：扩展到最大基数最小成本匹配（近似算法版本） 如果不需要完美匹配，而是要求最大基数匹配中的最小成本，我们可以修改算法： 先忽略成本，找到一个最大基数匹配 \( M_ {\text{max}} \)（基数 \( k \)）。 然后，在原图中仅考虑顶点子集：被 \( M_ {\text{max}} \) 覆盖的顶点（共 \( 2k \) 个顶点），以及它们之间的边。在这个子图上寻找最小成本完美匹配（因为子图中存在完美匹配，即 \( M_ {\text{max}} \) 本身）。 在子图上运行上述原始-对偶算法，得到最小成本完美匹配，它也就是原图的最小成本最大基数匹配。 为什么这是精确的？ ：因为任何最大基数匹配都恰好覆盖这 \( 2k \) 个顶点，所以我们只需在这些顶点上优化成本，问题归结为子图上的最小成本完美匹配。 总结 我们基于线性规划和对偶理论，设计了求解二分图最小成本最大匹配的原始-对偶算法。算法通过逐步调整对偶变量，在紧边子图中搜索最大匹配，直至找到完美匹配（或最大基数匹配）。该算法实际上是匈牙利算法的对偶视角，能够给出精确最优解，而不是近似解。这个例子展示了原始-对偶方法如何将组合优化问题与线性规划松弛紧密结合，通过巧妙维护对偶可行性来构造原始整数解。