基于线性规划的顶点覆盖问题的原始-对偶近似算法求解示例
字数 3613 2025-12-18 11:30:18

基于线性规划的顶点覆盖问题的原始-对偶近似算法求解示例

我将为您讲解顶点覆盖问题（Vertex Cover）的一种经典近似算法——原始-对偶算法的完整求解过程。该算法利用线性规划的对偶理论，能够在多项式时间内找到不超过最优解两倍的近似解。

问题描述

顶点覆盖问题：

  • 给定一个无向图 \(G=(V,E)\)，其中 \(V\) 是顶点集，\(E\) 是边集。
  • 目标是找到一个最小的顶点子集 \(S\subseteq V\)，使得图中每条边至少有一个端点属于 \(S\)。
  • 这是一个NP-hard问题，但存在简单的2-近似算法。

线性规划模型：

  • 为每个顶点 \(v\in V\) 引入变量 \(x_v\in\{0,1\}\)，表示顶点是否被选中。
  • 整数规划模型：

\[ \begin{aligned} \min\quad & \sum_{v\in V} x_v \\ \text{s.t.}\quad & x_u + x_v \geq 1 \quad \forall (u,v)\in E, \\ & x_v \in \{0,1\} \quad \forall v\in V. \end{aligned} \]

  • 松弛为线性规划（LP）：

\[ \begin{aligned} \min\quad & \sum_{v\in V} x_v \\ \text{s.t.}\quad & x_u + x_v \geq 1 \quad \forall (u,v)\in E, \\ & x_v \geq 0 \quad \forall v\in V. \end{aligned} \]

（注意：由于约束已经保证 \(x_v \leq 1\)，因此无需显式添加上界。）

对偶规划：

  • 为每条边 \(e\in E\) 引入对偶变量 \(y_e \geq 0\)。
  • 对偶规划为：

\[ \begin{aligned} \max\quad & \sum_{e\in E} y_e \\ \text{s.t.}\quad & \sum_{e\ni v} y_e \leq 1 \quad \forall v\in V, \\ & y_e \geq 0 \quad \forall e\in E. \end{aligned} \]

其中 \(\sum_{e\ni v} y_e\) 表示所有与顶点 \(v\) 相关联的边上的 \(y_e\) 之和。

原始-对偶算法的核心思想：

  • 同时构造原始可行解 \(x\)（整数解）和对偶可行解 \(y\)。
  • 利用互补松弛条件指导构造过程，确保原始解不超过对偶目标值的两倍。
  • 由弱对偶定理，对偶目标值是原始最优解的下界，从而得到近似比保证。

算法步骤详解

步骤1：初始化

  • 设置所有原始变量 \(x_v = 0\)（表示所有顶点初始未选中）。
  • 设置所有对偶变量 \(y_e = 0\)（表示所有边初始未“覆盖”）。
  • 定义一个边集合 \(E' = E\)（表示尚未被覆盖的边）。

步骤2：逐步提升对偶变量

  • 当 \(E'\) 非空时（即存在未被覆盖的边），执行循环：
    1. 选择一条边：从 \(E'\) 中任选一条边 \(e=(u,v)\)。
    2. 增加对偶变量：增加 \(y_e\) 的值，同时保持对偶可行性。具体地，持续增加 \(y_e\)，直到某个端点 \(u\) 或 \(v\) 的邻边对偶变量之和达到1（即约束变紧）。
      • 设顶点 \(u\) 和 \(v\) 的当前对偶约束松弛量分别为 \(s_u = 1 - \sum_{e'\ni u} y_{e'}\) 和 \(s_v = 1 - \sum_{e'\ni v} y_{e'}\)。
      • 将 \(y_e\) 增加 \(\delta = \min(s_u, s_v)\)。
      • 此时，顶点 \(u\) 或 \(v\)（或两者）的对偶约束变为紧（等式成立）。
    3. 覆盖紧约束顶点：将对偶约束变紧的顶点加入覆盖集。
      • 若 \(u\) 的对偶约束变紧（\(\sum_{e'\ni u} y_{e'} = 1\)），则设置 \(x_u = 1\)。
      • 若 \(v\) 的对偶约束变紧，则设置 \(x_v = 1\)。
      • 注意：一条边可能使两个端点同时变紧，此时两个顶点都被选中。
    4. 更新未覆盖边集合：将新选中顶点所关联的所有边从 \(E'\) 中移除（因为这些边现在已被覆盖）。

步骤3：输出覆盖集

  • 输出 \(S = \{v \in V \mid x_v = 1\}\) 作为顶点覆盖。

实例演示

考虑一个简单图：顶点集 \(V=\{1,2,3,4\}\)，边集 \(E=\{(1,2),(2,3),(3,4),(4,1),(2,4)\}\)。

执行过程：

  1. 初始化：

    • \(x_1=x_2=x_3=x_4=0\)，\(y_e=0\) 对所有边，\(E' = \{(1,2),(2,3),(3,4),(4,1),(2,4)\}\)。

  2. 第一轮迭代：

    • 选择边 \(e=(1,2)\)。
    • 计算 \(s_1 = 1 - 0 = 1\)，\(s_2 = 1 - 0 = 1\)，\(\delta = \min(1,1)=1\)。
    • 增加 \(y_{(1,2)}\) 至 \(1\)。此时顶点1和2的对偶约束同时变紧（因为各自只有一条边关联）。
    • 设置 \(x_1=1\)，\(x_2=1\)。
    • 移除边 \((1,2)\)、\((2,3)\)、\((4,1)\)、\((2,4)\)（这些边关联顶点1或2）。现在 \(E' = \{(3,4)\}\)。

  3. 第二轮迭代：

    • 选择边 \(e=(3,4)\)。
    • 计算 \(s_3 = 1 - 0 = 1\)，\(s_4 = 1 - 0 = 1\)（注意顶点4之前关联的边 \((4,1)\) 和 \((2,4)\) 已被移除，其当前的 \(\sum y_e\) 仍为0）。
    • 增加 \(y_{(3,4)}\) 至 \(1\)。顶点3和4的对偶约束变紧。
    • 设置 \(x_3=1\)，\(x_4=1\)。
    • 移除边 \((3,4)\)。现在 \(E' = \emptyset\)。

  4. 输出：

    • 覆盖集 \(S = \{1,2,3,4\}\)，即所有顶点。

结果分析：

  • 算法输出覆盖大小为4。
  • 该图的最小顶点覆盖实际为 \(\{2,4\}\) 或 \(\{1,3\}\)，大小为2。
  • 因此近似比为 \(4/2=2\)，达到理论最坏情况。

算法理论保证

近似比证明：

  1. 算法产生的 \(x\) 是整数可行解（每条边至少有一个端点在 \(S\) 中），因为算法会持续增加对偶变量直到覆盖所有边。
  2. 由构造过程，当顶点 \(v\) 被选中（\(x_v=1\)）时，其关联边的对偶变量之和恰好为1（对偶约束紧）。
  3. 因此，原始目标值：

\[ \sum_{v\in V} x_v = \sum_{v\in S} 1 = |S|. \]

  1. 每条边 \(e=(u,v)\) 最多贡献两次到对偶约束和中（一次对 \(u\)，一次对 \(v\)），故：

\[ \sum_{v\in S} \sum_{e\ni v} y_e \leq 2 \sum_{e\in E} y_e. \]

  1. 由于对顶点 \(v\in S\) 有 \(\sum_{e\ni v} y_e = 1\)，所以：

\[ |S| = \sum_{v\in S} 1 = \sum_{v\in S} \sum_{e\ni v} y_e \leq 2 \sum_{e\in E} y_e. \]

  1. 由弱对偶定理，对偶可行解的目标值 \(\sum_{e\in E} y_e\) 不超过原始LP最优值 \(OPT_{LP}\)，而 \(OPT_{LP} \leq OPT_{IP}\)（整数规划最优值）。因此：

\[ |S| \leq 2 \sum_{e\in E} y_e \leq 2 OPT_{LP} \leq 2 OPT_{IP}. \]

证毕。

时间复杂度：

  • 每轮迭代至少使一个顶点变紧，因此最多 \(|V|\) 轮迭代。
  • 每轮迭代可在 \(O(|E|)\) 时间内更新松弛量和边集合。
  • 总时间复杂度为 \(O(|V||E|)\)，是多项式时间。

总结

原始-对偶算法为顶点覆盖问题提供了一个简洁、高效的2-近似算法。其优势在于：

  1. 无需求解线性规划：直接构造对偶可行解指导原始整数解构造。
  2. 理论保证强：严格证明近似比不超过2。
  3. 易于实现：只需维护对偶变量松弛量和未覆盖边集合。

该算法展示了如何利用对偶理论设计组合优化问题的近似算法，是原始-对偶方法的经典范例。

基于线性规划的顶点覆盖问题的原始-对偶近似算法求解示例 我将为您讲解顶点覆盖问题（Vertex Cover）的一种经典近似算法——原始-对偶算法的完整求解过程。该算法利用线性规划的对偶理论，能够在多项式时间内找到不超过最优解两倍的近似解。 问题描述 顶点覆盖问题 ： 给定一个无向图 \(G=(V,E)\)，其中 \(V\) 是顶点集，\(E\) 是边集。 目标是找到一个最小的顶点子集 \(S\subseteq V\)，使得图中每条边至少有一个端点属于 \(S\)。 这是一个NP-hard问题，但存在简单的2-近似算法。 线性规划模型 ： 为每个顶点 \(v\in V\) 引入变量 \(x_ v\in\{0,1\}\)，表示顶点是否被选中。 整数规划模型： \[ \begin{aligned} \min\quad & \sum_ {v\in V} x_ v \\ \text{s.t.}\quad & x_ u + x_ v \geq 1 \quad \forall (u,v)\in E, \\ & x_ v \in \{0,1\} \quad \forall v\in V. \end{aligned} \] 松弛为线性规划（LP）： \[ \begin{aligned} \min\quad & \sum_ {v\in V} x_ v \\ \text{s.t.}\quad & x_ u + x_ v \geq 1 \quad \forall (u,v)\in E, \\ & x_ v \geq 0 \quad \forall v\in V. \end{aligned} \] （注意：由于约束已经保证 \(x_ v \leq 1\)，因此无需显式添加上界。） 对偶规划 ： 为每条边 \(e\in E\) 引入对偶变量 \(y_ e \geq 0\)。 对偶规划为： \[ \begin{aligned} \max\quad & \sum_ {e\in E} y_ e \\ \text{s.t.}\quad & \sum_ {e\ni v} y_ e \leq 1 \quad \forall v\in V, \\ & y_ e \geq 0 \quad \forall e\in E. \end{aligned} \] 其中 \(\sum_ {e\ni v} y_ e\) 表示所有与顶点 \(v\) 相关联的边上的 \(y_ e\) 之和。 原始-对偶算法的核心思想 ： 同时构造原始可行解 \(x\)（整数解）和对偶可行解 \(y\)。 利用互补松弛条件指导构造过程，确保原始解不超过对偶目标值的两倍。 由弱对偶定理，对偶目标值是原始最优解的下界，从而得到近似比保证。 算法步骤详解 步骤1：初始化 设置所有原始变量 \(x_ v = 0\)（表示所有顶点初始未选中）。 设置所有对偶变量 \(y_ e = 0\)（表示所有边初始未“覆盖”）。 定义一个边集合 \(E' = E\)（表示尚未被覆盖的边）。 步骤2：逐步提升对偶变量 当 \(E'\) 非空时（即存在未被覆盖的边），执行循环： 选择一条边 ：从 \(E'\) 中任选一条边 \(e=(u,v)\)。 增加对偶变量 ：增加 \(y_ e\) 的值，同时保持对偶可行性。具体地，持续增加 \(y_ e\)，直到某个端点 \(u\) 或 \(v\) 的邻边对偶变量之和达到1（即约束变紧）。 设顶点 \(u\) 和 \(v\) 的当前对偶约束松弛量分别为 \(s_ u = 1 - \sum_ {e'\ni u} y_ {e'}\) 和 \(s_ v = 1 - \sum_ {e'\ni v} y_ {e'}\)。 将 \(y_ e\) 增加 \(\delta = \min(s_ u, s_ v)\)。 此时，顶点 \(u\) 或 \(v\)（或两者）的对偶约束变为紧（等式成立）。 覆盖紧约束顶点 ：将对偶约束变紧的顶点加入覆盖集。 若 \(u\) 的对偶约束变紧（\(\sum_ {e'\ni u} y_ {e'} = 1\)），则设置 \(x_ u = 1\)。 若 \(v\) 的对偶约束变紧，则设置 \(x_ v = 1\)。 注意：一条边可能使两个端点同时变紧，此时两个顶点都被选中。 更新未覆盖边集合 ：将新选中顶点所关联的所有边从 \(E'\) 中移除（因为这些边现在已被覆盖）。 步骤3：输出覆盖集 输出 \(S = \{v \in V \mid x_ v = 1\}\) 作为顶点覆盖。 实例演示 考虑一个简单图：顶点集 \(V=\{1,2,3,4\}\)，边集 \(E=\{(1,2),(2,3),(3,4),(4,1),(2,4)\}\)。 执行过程 ： 初始化 ： \(x_ 1=x_ 2=x_ 3=x_ 4=0\)，\(y_ e=0\) 对所有边，\(E' = \{(1,2),(2,3),(3,4),(4,1),(2,4)\}\)。 第一轮迭代 ： 选择边 \(e=(1,2)\)。 计算 \(s_ 1 = 1 - 0 = 1\)，\(s_ 2 = 1 - 0 = 1\)，\(\delta = \min(1,1)=1\)。 增加 \(y_ {(1,2)}\) 至 \(1\)。此时顶点1和2的对偶约束同时变紧（因为各自只有一条边关联）。 设置 \(x_ 1=1\)，\(x_ 2=1\)。 移除边 \((1,2)\)、\((2,3)\)、\((4,1)\)、\((2,4)\)（这些边关联顶点1或2）。现在 \(E' = \{(3,4)\}\)。 第二轮迭代 ： 选择边 \(e=(3,4)\)。 计算 \(s_ 3 = 1 - 0 = 1\)，\(s_ 4 = 1 - 0 = 1\)（注意顶点4之前关联的边 \((4,1)\) 和 \((2,4)\) 已被移除，其当前的 \(\sum y_ e\) 仍为0）。 增加 \(y_ {(3,4)}\) 至 \(1\)。顶点3和4的对偶约束变紧。 设置 \(x_ 3=1\)，\(x_ 4=1\)。 移除边 \((3,4)\)。现在 \(E' = \emptyset\)。 输出 ： 覆盖集 \(S = \{1,2,3,4\}\)，即所有顶点。 结果分析 ： 算法输出覆盖大小为4。 该图的最小顶点覆盖实际为 \(\{2,4\}\) 或 \(\{1,3\}\)，大小为2。 因此近似比为 \(4/2=2\)，达到理论最坏情况。 算法理论保证 近似比证明 ： 算法产生的 \(x\) 是整数可行解（每条边至少有一个端点在 \(S\) 中），因为算法会持续增加对偶变量直到覆盖所有边。 由构造过程，当顶点 \(v\) 被选中（\(x_ v=1\)）时，其关联边的对偶变量之和恰好为1（对偶约束紧）。 因此，原始目标值： \[ \sum_ {v\in V} x_ v = \sum_ {v\in S} 1 = |S|. \] 每条边 \(e=(u,v)\) 最多贡献两次到对偶约束和中（一次对 \(u\)，一次对 \(v\)），故： \[ \sum_ {v\in S} \sum_ {e\ni v} y_ e \leq 2 \sum_ {e\in E} y_ e. \] 由于对顶点 \(v\in S\) 有 \(\sum_ {e\ni v} y_ e = 1\)，所以： \[ |S| = \sum_ {v\in S} 1 = \sum_ {v\in S} \sum_ {e\ni v} y_ e \leq 2 \sum_ {e\in E} y_ e. \] 由弱对偶定理，对偶可行解的目标值 \(\sum_ {e\in E} y_ e\) 不超过原始LP最优值 \(OPT_ {LP}\)，而 \(OPT_ {LP} \leq OPT_ {IP}\)（整数规划最优值）。因此： \[ |S| \leq 2 \sum_ {e\in E} y_ e \leq 2 OPT_ {LP} \leq 2 OPT_ {IP}. \] 证毕。 时间复杂度 ： 每轮迭代至少使一个顶点变紧，因此最多 \(|V|\) 轮迭代。 每轮迭代可在 \(O(|E|)\) 时间内更新松弛量和边集合。 总时间复杂度为 \(O(|V||E|)\)，是多项式时间。 总结 原始-对偶算法为顶点覆盖问题提供了一个简洁、高效的2-近似算法。其优势在于： 无需求解线性规划 ：直接构造对偶可行解指导原始整数解构造。 理论保证强 ：严格证明近似比不超过2。 易于实现 ：只需维护对偶变量松弛量和未覆盖边集合。 该算法展示了如何利用对偶理论设计组合优化问题的近似算法，是原始-对偶方法的经典范例。