基于线性规划的图最大权匹配问题的原始-对偶近似算法求解示例
字数 2537 2025-12-02 21:01:05

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

题目描述
考虑一个无向图 \(G = (V, E)\)，每条边 \(e \in E\) 有一个权重 \(w_e \geq 0\)。匹配是边的子集，其中任意两条边不共享公共顶点。目标是找到一个匹配，使得匹配中边的权重之和最大。该问题是NP难问题，但通过线性规划松弛和原始-对偶方法，可设计近似算法。本示例将展示如何利用原始-对偶框架构造一个1/2-近似算法（即解至少是最优值的1/2）。

解题过程
步骤1: 线性规划建模

  • 定义变量 \(x_e \in \{0,1\}\) 表示边 \(e\) 是否在匹配中。
  • 约束：每个顶点最多与一条匹配边相连，即对每个顶点 \(v\)，\(\sum_{e \in \delta(v)} x_e \leq 1\)，其中 \(\delta(v)\) 表示与 \(v\) 相连的边集。
  • 目标：最大化 \(\sum_{e \in E} w_e x_e\)。

整数规划松弛为线性规划（LP）：

\[\begin{align*} \max \quad & \sum_{e \in E} w_e x_e \\ \text{s.t.} \quad & \sum_{e \in \delta(v)} x_e \leq 1, \quad \forall v \in V \\ & x_e \geq 0, \quad \forall e \in E \end{align*} \]

（注：虽然原问题要求 \(x_e \in \{0,1\}\)，但LP松弛后最优解可能含分数值，需通过算法处理。）

步骤2: 构造对偶问题

  • 对每个顶点约束引入对偶变量 \(y_v \geq 0\)。
  • 对偶LP为：

\[\begin{align*} \min \quad & \sum_{v \in V} y_v \\ \text{s.t.} \quad & y_u + y_v \geq w_e, \quad \forall e = (u,v) \in E \\ & y_v \geq 0, \quad \forall v \in V \end{align*} \]

对偶约束要求每条边 \(e\) 的两个端点的对偶变量之和至少为 \(w_e\)。

步骤3: 原始-对偶框架设计
算法核心思想：

  1. 初始化：所有 \(x_e = 0\)，所有 \(y_v = 0\)，匹配集 \(M = \emptyset\)。
  2. 逐步增加对偶变量 \(y_v\)（称为“顶点价格”），直到某些边满足紧约束（即 \(y_u + y_v = w_e\)）。
  3. 将紧边加入候选集，并检查是否可加入匹配 \(M\)（不违反匹配约束）。
  4. 当所有边被覆盖或无法继续时停止。

步骤4: 算法详细步骤

  • 阶段1: 对偶增长
    遍历所有边，若边 \(e = (u,v)\) 不满足紧约束（即 \(y_u + y_v < w_e\)），则同时增加 \(y_u\) 和 \(y_v\)，直到 \(y_u + y_v = w_e\)。此时将 \(e\) 标记为“紧边”。
  • 阶段2: 匹配构造
    检查所有紧边：按任意顺序考虑每条紧边 \(e\)，若其两端点均未匹配，则将 \(e\) 加入匹配 \(M\)。
  • 输出匹配 \(M\) 及其权重和。

步骤5: 示例演示
考虑图：顶点集 \(V = \{1,2,3\}\)，边 \(e_1 = (1,2)\) 权重 3，\(e_2 = (2,3)\) 权重 2，\(e_3 = (1,3)\) 权重 2。

  1. 初始化：\(y_1 = y_2 = y_3 = 0\)，\(M = \emptyset\)。
  2. 对偶增长：
    • 边 \(e_1\)：\(y_1 + y_2 = 0 < 3\)，增加 \(y_1, y_2\) 至 1.5，使和等于 3。
    • 边 \(e_2\)：\(y_2 + y_3 = 1.5 + 0 = 1.5 < 2\)，增加 \(y_2, y_3\) 至 1.5 和 0.5（注：\(y_2\) 已为 1.5，仅增 \(y_3\) 至 0.5，使和等于 2）。
    • 边 \(e_3\)：\(y_1 + y_3 = 1.5 + 0.5 = 2\)，已紧。
  3. 匹配构造：
    • 考虑 \(e_1\)：顶点1、2未匹配，将 \(e_1\) 加入 \(M\)。
    • \(e_2\)：顶点2已匹配，跳过。
    • \(e_3\)：顶点1已匹配，跳过。
      最终 \(M = \{e_1\}\)，权重和 = 3。
      最优解为 \(\{e_2, e_3\}\) 权重和 4，算法解为最优解的 3/4 > 1/2，满足近似比。

步骤6: 理论保证

  • 可行性：算法输出的 \(M\) 是合法匹配（因每次加入边时检查顶点冲突）。
  • 近似比：设算法解权重为 \(w(M) = \sum_{e \in M} w_e\)。由紧边条件 \(w_e = y_u + y_v\)，有：

\[ w(M) = \sum_{e \in M} (y_u + y_v) \leq \sum_{v \in V} y_v \leq 2 \cdot \sum_{v \in V} y_v^* \]

其中 \(y_v^*\) 是对偶最优解（因每个顶点最多被两条匹配边覆盖）。由弱对偶定理，\(\sum_{v} y_v^*\) 不小于原问题最优值，故 \(w(M) \geq \frac{1}{2} \text{OPT}\)。

总结
通过线性规划对偶理论，将离散优化问题转化为连续松弛，利用原始-对偶方法构造简单高效的近似算法。此方法避免了直接求解整数规划，适用于大规模图的最大权匹配问题。

基于线性规划的图最大权匹配问题的原始-对偶近似算法求解示例 题目描述 考虑一个无向图 \( G = (V, E) \)，每条边 \( e \in E \) 有一个权重 \( w_ e \geq 0 \)。匹配是边的子集，其中任意两条边不共享公共顶点。目标是找到一个匹配，使得匹配中边的权重之和最大。该问题是NP难问题，但通过线性规划松弛和原始-对偶方法，可设计近似算法。本示例将展示如何利用原始-对偶框架构造一个1/2-近似算法（即解至少是最优值的1/2）。 解题过程 步骤1: 线性规划建模 定义变量 \( x_ e \in \{0,1\} \) 表示边 \( e \) 是否在匹配中。 约束：每个顶点最多与一条匹配边相连，即对每个顶点 \( v \)，\( \sum_ {e \in \delta(v)} x_ e \leq 1 \)，其中 \( \delta(v) \) 表示与 \( v \) 相连的边集。 目标：最大化 \( \sum_ {e \in E} w_ e x_ e \)。 整数规划松弛为线性规划（LP）： \[ \begin{align* } \max \quad & \sum_ {e \in E} w_ e x_ e \\ \text{s.t.} \quad & \sum_ {e \in \delta(v)} x_ e \leq 1, \quad \forall v \in V \\ & x_ e \geq 0, \quad \forall e \in E \end{align* } \] （注：虽然原问题要求 \( x_ e \in \{0,1\} \)，但LP松弛后最优解可能含分数值，需通过算法处理。） 步骤2: 构造对偶问题 对每个顶点约束引入对偶变量 \( y_ v \geq 0 \)。 对偶LP为： \[ \begin{align* } \min \quad & \sum_ {v \in V} y_ v \\ \text{s.t.} \quad & y_ u + y_ v \geq w_ e, \quad \forall e = (u,v) \in E \\ & y_ v \geq 0, \quad \forall v \in V \end{align* } \] 对偶约束要求每条边 \( e \) 的两个端点的对偶变量之和至少为 \( w_ e \)。 步骤3: 原始-对偶框架设计 算法核心思想： 初始化：所有 \( x_ e = 0 \)，所有 \( y_ v = 0 \)，匹配集 \( M = \emptyset \)。 逐步增加对偶变量 \( y_ v \)（称为“顶点价格”），直到某些边满足紧约束（即 \( y_ u + y_ v = w_ e \)）。 将紧边加入候选集，并检查是否可加入匹配 \( M \)（不违反匹配约束）。 当所有边被覆盖或无法继续时停止。 步骤4: 算法详细步骤 阶段1: 对偶增长 遍历所有边，若边 \( e = (u,v) \) 不满足紧约束（即 \( y_ u + y_ v < w_ e \)），则同时增加 \( y_ u \) 和 \( y_ v \)，直到 \( y_ u + y_ v = w_ e \)。此时将 \( e \) 标记为“紧边”。 阶段2: 匹配构造 检查所有紧边：按任意顺序考虑每条紧边 \( e \)，若其两端点均未匹配，则将 \( e \) 加入匹配 \( M \)。 输出匹配 \( M \) 及其权重和。 步骤5: 示例演示 考虑图：顶点集 \( V = \{1,2,3\} \)，边 \( e_ 1 = (1,2) \) 权重 3，\( e_ 2 = (2,3) \) 权重 2，\( e_ 3 = (1,3) \) 权重 2。 初始化：\( y_ 1 = y_ 2 = y_ 3 = 0 \)，\( M = \emptyset \)。 对偶增长： 边 \( e_ 1 \)：\( y_ 1 + y_ 2 = 0 < 3 \)，增加 \( y_ 1, y_ 2 \) 至 1.5，使和等于 3。 边 \( e_ 2 \)：\( y_ 2 + y_ 3 = 1.5 + 0 = 1.5 < 2 \)，增加 \( y_ 2, y_ 3 \) 至 1.5 和 0.5（注：\( y_ 2 \) 已为 1.5，仅增 \( y_ 3 \) 至 0.5，使和等于 2）。 边 \( e_ 3 \)：\( y_ 1 + y_ 3 = 1.5 + 0.5 = 2 \)，已紧。 匹配构造： 考虑 \( e_ 1 \)：顶点1、2未匹配，将 \( e_ 1 \) 加入 \( M \)。 \( e_ 2 \)：顶点2已匹配，跳过。 \( e_ 3 \)：顶点1已匹配，跳过。 最终 \( M = \{e_ 1\} \)，权重和 = 3。 最优解为 \( \{e_ 2, e_ 3\} \) 权重和 4，算法解为最优解的 3/4 > 1/2，满足近似比。 步骤6: 理论保证 可行性：算法输出的 \( M \) 是合法匹配（因每次加入边时检查顶点冲突）。 近似比：设算法解权重为 \( w(M) = \sum_ {e \in M} w_ e \)。由紧边条件 \( w_ e = y_ u + y_ v \)，有： \[ w(M) = \sum_ {e \in M} (y_ u + y_ v) \leq \sum_ {v \in V} y_ v \leq 2 \cdot \sum_ {v \in V} y_ v^* \] 其中 \( y_ v^* \) 是对偶最优解（因每个顶点最多被两条匹配边覆盖）。由弱对偶定理，\( \sum_ {v} y_ v^* \) 不小于原问题最优值，故 \( w(M) \geq \frac{1}{2} \text{OPT} \)。 总结 通过线性规划对偶理论，将离散优化问题转化为连续松弛，利用原始-对偶方法构造简单高效的近似算法。此方法避免了直接求解整数规划，适用于大规模图的最大权匹配问题。