基于线性规划的图最小费用有向生成树问题的多项式时间算法求解示例
字数 4549 2025-12-17 22:27:44

基于线性规划的图最小费用有向生成树问题的多项式时间算法求解示例

我将详细讲解如何用线性规划方法求解“图最小费用有向生成树”问题。这个问题也称为最小树形图（Minimum Arborescence）问题。

问题描述

我们有一个有向图 \(G = (V, E)\)，其中 \(V\) 是顶点集（\(|V| = n\)），\(E\) 是边集（\(|E| = m\)）。每条边 \(e \in E\) 有一个费用 \(c(e) \in \mathbb{R}\)。我们需要指定一个根节点 \(r \in V\)。目标是找到一个有向生成树（即一个包含所有顶点、以 \(r\) 为根的有向树），满足从 \(r\) 到其他每个顶点都有且仅有一条有向路径，并且使得所选边的总费用最小。

线性规划模型

我们定义一个决策变量 \(x_e\) 表示边 \(e\) 是否被选中：

\[x_e = \begin{cases} 1, & \text{如果边 } e \text{ 在最小费用有向生成树中} \\ 0, & \text{否则} \end{cases} \]

目标函数：最小化总费用

\[\min \sum_{e \in E} c(e) x_e \]

约束条件：

  1. 入度约束：根节点 \(r\) 的入度必须是 0，其他每个非根节点的入度必须是 1。

\[ \sum_{e \in \delta^-(v)} x_e = 1, \quad \forall v \in V \setminus \{r\} \]

其中 \(\delta^-(v)\) 表示指向顶点 \(v\) 的边集。

  1. 连通性约束：对于任意非空子集 \(S \subseteq V \setminus \{r\}\)，必须至少有一条边从外部进入 \(S\)，以确保从根能到达 \(S\) 内的每个顶点。

\[ \sum_{e \in \delta^-(S)} x_e \ge 1, \quad \forall S \subseteq V \setminus \{r\}, S \neq \emptyset \]

其中 \(\delta^-(S)\) 表示起点在 \(S\) 外、终点在 \(S\) 内的边集。

  1. 非负性约束：由于是整数规划，通常用线性松弛：

\[ x_e \ge 0, \quad \forall e \in E \]

整数约束 \(x_e \in \{0,1\}\) 在松弛中忽略，我们将证明线性规划松弛的最优解自动是整数解。

求解过程

我们将通过构造对偶问题，并利用互补松弛条件来设计一个多项式时间的组合算法（即著名的 Edmonds 算法思想在线性规划框架下的解释）。

第 1 步：写出对偶问题

首先，将原问题（线性松弛）写成矩阵形式便于求对偶：

原问题（P）：

\[\begin{aligned} \min \quad & c^T x \\ \text{s.t.} \quad & A_{\text{in}} x = \mathbf{1}_{n-1} \quad &\text{(入度约束)} \\ & B_{\text{cut}} x \ge \mathbf{1}_{2^{n-1}-1} \quad &\text{(连通性约束，指数级数量)} \\ & x \ge 0 \end{aligned} \]

引入对偶变量：

  • 对每个非根节点 \(v\)，有变量 \(y_v\) 对应入度约束。
  • 对每个非空子集 \(S \subseteq V \setminus \{r\}\)，有变量 \(z_S \ge 0\) 对应连通性约束。

对偶问题（D）：

\[\begin{aligned} \max \quad & \sum_{v \neq r} y_v + \sum_{S \neq \emptyset, S \subseteq V\setminus\{r\}} z_S \\ \text{s.t.} \quad & y_{\text{head}(e)} + \sum_{S: e \in \delta^-(S)} z_S \le c(e), \quad \forall e \in E \\ & z_S \ge 0, \quad \forall S \end{aligned} \]

其中 \(y_v\) 无符号限制（因为入度约束是等式），实际上可正可负。

第 2 步：简化对偶约束

令 \(w(e) = c(e) - y_{\text{head}(e)}\)，则对偶约束变为：

\[\sum_{S: e \in \delta^-(S)} z_S \le w(e), \quad \forall e \in E \]

并且目标函数为 \(\sum_{v \neq r} y_v + \sum_{S} z_S\)。

第 3 步：互补松弛条件

如果 \(x^*, (y^*, z^*)\) 分别是原问题和对偶问题的最优解，则：

  1. 对每条边 \(e\)：

\[ x_e^* > 0 \implies \sum_{S: e \in \delta^-(S)} z_S^* = w(e) \]

即如果原问题中边被选用（\(x_e^* > 0\)），则对应对偶约束是紧的。

  1. 对每个集合 \(S\)：

\[ z_S^* > 0 \implies \sum_{e \in \delta^-(S)} x_e^* = 1 \]

即如果对偶中 \(z_S^* > 0\)，则进入 \(S\) 的边恰好有一条被选中。

第 4 步：算法思想（Edmonds 算法）

我们通过动态调整对偶变量 \(y_v\) 来逐步构造原问题的最优解，同时维持对偶可行性和互补松弛条件。

算法步骤：

  1. 初始化：设 \(y_v = 0\) 对所有 \(v\)，\(z_S = 0\) 对所有 \(S\)。定义修改后的边权 \(w(e) = c(e) - y_{\text{head}(e)} = c(e)\)。

  2. 找最小入边：对每个非根节点 \(v\)，选择进入 \(v\) 的最小权重边 \(e_v = \arg\min_{e \in \delta^-(v)} w(e)\)，记其权重为 \(\min_v\)。设这些边构成的子图为 \(F\)。

  3. 检测环：

    • 如果 \(F\) 中无环（除了根可能有多条出边），则 \(F\) 已是最小树形图，算法结束。
    • 如果 \(F\) 中有环（有向环），设环为 \(C\)。

  4. 收缩环：

    • 将环 \(C\) 收缩为一个新超级节点 \(v_C\)。
    • 更新图：环外指向环内节点 \(u \in C\) 的边 \(e = (a,u)\) 变为指向 \(v_C\)，其权重更新为 \(w'(e) = w(e) - w(e_u)\)，其中 \(e_u\) 是 \(u\) 在 \(F\) 中的入边（即环中指向 \(u\) 的那条边）。这一步相当于在对偶中增加 \(z_C\) 并调整 \(y_v\) 使得对偶解仍可行。
    • 重复步骤 2-4 在新图上。

  5. 展开环：

    • 当新图得到最小树形图后，逐层展开收缩的环。在环 \(C\) 中，去掉环上一条边（该边是原环中除最小入边外的某条边），并加入环外指向该环的一条边，使得树形图连通。

第 5 步：线性规划解释

  • 每次对环 \(C\) 收缩时，相当于增加对偶变量 \(z_C\) 的值，直到新图中某些修改后的边权 \(w'(e)\) 变为 0（即达到对偶约束的等式）。
  • 调整 \(y_v\) 以保持对偶目标增长：在环 \(C\) 中，对每个节点 \(v \in C\)，减少 \(y_v\) 会使进入 \(v\) 的边权减小，从而允许我们增加 \(z_C\)。
  • 最终构造出的树形图对应原问题的一个整数解 \(x^*\)，满足互补松弛条件，因此是最优的。

第 6 步：复杂度

每次收缩至少减少一个顶点，每轮需 \(O(m)\) 时间找最小入边和检测环，总复杂度 \(O(nm)\)，多项式时间。

示例演示

考虑一个简单有向图：

  • 顶点：\(V = \{r, a, b, c\}\)
  • 边及费用：
    • \((r,a)=4, (r,b)=3, (r,c)=6\)
    • \((a,b)=2, (a,c)=5\)
    • \((b,a)=1, (b,c)=4\)
    • \((c,a)=3, (c,b)=2\)
      根为 \(r\)。

步骤：

  1. 初始 \(w(e)=c(e)\)，每个非根节点选最小入边：

    • a: min(4,1,3)=1 选 (b,a)
    • b: min(3,2,2)=2 选 (a,b) 或 (c,b)，任选 (a,b)
    • c: min(6,5,4)=4 选 (b,c)
      此时边集 \(F = \{(b,a), (a,b), (b,c)\}\)，有环 \(a \to b \to a\)。

  2. 收缩环 \(C=\{a,b\}\) 为超级节点 \(v_C\)。

    • 更新边权（以 \(a\) 为例）：
      • 原入边 (r,a): w=4, 环中 a 的入边 (b,a) 权 1，新权重 4-1=3。
      • 原入边 (c,a): 3-1=2。
    • 类似更新 b 的入边（但 b 已在环内，环内边忽略）。
    • 新图：顶点 {r, v_C, c}，边：
      • (r, v_C)=min(3,2)=2（来自 (r,b) 和 (r,a) 更新后的最小）
      • (c, v_C)=min(2,2)=2
      • (v_C, c)：从原环到 c 的边 (a,c)=5, (b,c)=4，需减去环中对应节点的入边权重，得 5-1=4, 4-2=2，最小 2。

  3. 在新图中，每个非根节点选最小入边：

    • v_C: min(2,2)=2 选 (r, v_C)
    • c: 入边 (b,c) 在收缩后为 (v_C,c)=2，选之。
      无边集无环，得到树形图。

  4. 展开环 \(C\)：新图中 (v_C,c) 对应原边 (b,c)，(r, v_C) 对应原边 (r,b)。在环 {a,b} 中，需去掉一条边使得树连通。原环边 (b,a) 和 (a,b) 中，去掉 (a,b)（因为 (r,b) 已进入环），保留 (b,a)。最终树：边集 {(r,b), (b,a), (b,c)}，总费用 3+1+4=8。

结论

通过线性规划对偶理论，我们解释了最小费用有向生成树的多项式时间算法（Edmonds 算法）本质上是在求解线性规划松弛，并且该松弛具有整数最优解。整个算法保证在多项式时间内找到精确最优解，而不仅仅是近似解。

基于线性规划的图最小费用有向生成树问题的多项式时间算法求解示例 我将详细讲解如何用线性规划方法求解“图最小费用有向生成树”问题。这个问题也称为最小树形图（Minimum Arborescence）问题。 问题描述 我们有一个有向图 \( G = (V, E) \)，其中 \( V \) 是顶点集（\( |V| = n \)），\( E \) 是边集（\( |E| = m \)）。每条边 \( e \in E \) 有一个费用 \( c(e) \in \mathbb{R} \)。我们需要指定一个根节点 \( r \in V \)。目标是找到一个有向生成树（即一个包含所有顶点、以 \( r \) 为根的有向树），满足从 \( r \) 到其他每个顶点都有且仅有一条有向路径，并且使得所选边的总费用最小。 线性规划模型 我们定义一个决策变量 \( x_ e \) 表示边 \( e \) 是否被选中： \[ x_ e = \begin{cases} 1, & \text{如果边 } e \text{ 在最小费用有向生成树中} \\ 0, & \text{否则} \end{cases} \] 目标函数 ：最小化总费用 \[ \min \sum_ {e \in E} c(e) x_ e \] 约束条件 ： 入度约束 ：根节点 \( r \) 的入度必须是 0，其他每个非根节点的入度必须是 1。 \[ \sum_ {e \in \delta^-(v)} x_ e = 1, \quad \forall v \in V \setminus \{r\} \] 其中 \( \delta^-(v) \) 表示指向顶点 \( v \) 的边集。 连通性约束 ：对于任意非空子集 \( S \subseteq V \setminus \{r\} \)，必须至少有一条边从外部进入 \( S \)，以确保从根能到达 \( S \) 内的每个顶点。 \[ \sum_ {e \in \delta^-(S)} x_ e \ge 1, \quad \forall S \subseteq V \setminus \{r\}, S \neq \emptyset \] 其中 \( \delta^-(S) \) 表示起点在 \( S \) 外、终点在 \( S \) 内的边集。 非负性约束 ：由于是整数规划，通常用线性松弛： \[ x_ e \ge 0, \quad \forall e \in E \] 整数约束 \( x_ e \in \{0,1\} \) 在松弛中忽略，我们将证明线性规划松弛的最优解自动是整数解。 求解过程 我们将通过构造 对偶问题 ，并利用 互补松弛条件 来设计一个多项式时间的组合算法（即著名的 Edmonds 算法思想在线性规划框架下的解释）。 第 1 步：写出对偶问题 首先，将原问题（线性松弛）写成矩阵形式便于求对偶： 原问题（P）： \[ \begin{aligned} \min \quad & c^T x \\ \text{s.t.} \quad & A_ {\text{in}} x = \mathbf{1} {n-1} \quad &\text{(入度约束)} \\ & B {\text{cut}} x \ge \mathbf{1}_ {2^{n-1}-1} \quad &\text{(连通性约束，指数级数量)} \\ & x \ge 0 \end{aligned} \] 引入对偶变量： 对每个非根节点 \( v \)，有变量 \( y_ v \) 对应入度约束。 对每个非空子集 \( S \subseteq V \setminus \{r\} \)，有变量 \( z_ S \ge 0 \) 对应连通性约束。 对偶问题（D） ： \[ \begin{aligned} \max \quad & \sum_ {v \neq r} y_ v + \sum_ {S \neq \emptyset, S \subseteq V\setminus\{r\}} z_ S \\ \text{s.t.} \quad & y_ {\text{head}(e)} + \sum_ {S: e \in \delta^-(S)} z_ S \le c(e), \quad \forall e \in E \\ & z_ S \ge 0, \quad \forall S \end{aligned} \] 其中 \( y_ v \) 无符号限制（因为入度约束是等式），实际上可正可负。 第 2 步：简化对偶约束 令 \( w(e) = c(e) - y_ {\text{head}(e)} \)，则对偶约束变为： \[ \sum_ {S: e \in \delta^-(S)} z_ S \le w(e), \quad \forall e \in E \] 并且目标函数为 \( \sum_ {v \neq r} y_ v + \sum_ {S} z_ S \)。 第 3 步：互补松弛条件 如果 \( x^ , (y^ , z^* ) \) 分别是原问题和对偶问题的最优解，则： 对每条边 \( e \)： \[ x_ e^* > 0 \implies \sum_ {S: e \in \delta^-(S)} z_ S^* = w(e) \] 即如果原问题中边被选用（\( x_ e^* > 0 \)），则对应对偶约束是紧的。 对每个集合 \( S \)： \[ z_ S^* > 0 \implies \sum_ {e \in \delta^-(S)} x_ e^* = 1 \] 即如果对偶中 \( z_ S^* > 0 \)，则进入 \( S \) 的边恰好有一条被选中。 第 4 步：算法思想（Edmonds 算法） 我们通过动态调整对偶变量 \( y_ v \) 来逐步构造原问题的最优解，同时维持对偶可行性和互补松弛条件。 算法步骤 ： 初始化 ：设 \( y_ v = 0 \) 对所有 \( v \)，\( z_ S = 0 \) 对所有 \( S \)。定义修改后的边权 \( w(e) = c(e) - y_ {\text{head}(e)} = c(e) \)。 找最小入边 ：对每个非根节点 \( v \)，选择进入 \( v \) 的最小权重边 \( e_ v = \arg\min_ {e \in \delta^-(v)} w(e) \)，记其权重为 \( \min_ v \)。设这些边构成的子图为 \( F \)。 检测环 ： 如果 \( F \) 中无环（除了根可能有多条出边），则 \( F \) 已是最小树形图，算法结束。 如果 \( F \) 中有环（有向环），设环为 \( C \)。 收缩环 ： 将环 \( C \) 收缩为一个新超级节点 \( v_ C \)。 更新图：环外指向环内节点 \( u \in C \) 的边 \( e = (a,u) \) 变为指向 \( v_ C \)，其权重更新为 \( w'(e) = w(e) - w(e_ u) \)，其中 \( e_ u \) 是 \( u \) 在 \( F \) 中的入边（即环中指向 \( u \) 的那条边）。这一步相当于在对偶中增加 \( z_ C \) 并调整 \( y_ v \) 使得对偶解仍可行。 重复步骤 2-4 在新图上。 展开环 ： 当新图得到最小树形图后，逐层展开收缩的环。在环 \( C \) 中，去掉环上一条边（该边是原环中除最小入边外的某条边），并加入环外指向该环的一条边，使得树形图连通。 第 5 步：线性规划解释 每次对环 \( C \) 收缩时，相当于增加对偶变量 \( z_ C \) 的值，直到新图中某些修改后的边权 \( w'(e) \) 变为 0（即达到对偶约束的等式）。 调整 \( y_ v \) 以保持对偶目标增长：在环 \( C \) 中，对每个节点 \( v \in C \)，减少 \( y_ v \) 会使进入 \( v \) 的边权减小，从而允许我们增加 \( z_ C \)。 最终构造出的树形图对应原问题的一个整数解 \( x^* \)，满足互补松弛条件，因此是最优的。 第 6 步：复杂度 每次收缩至少减少一个顶点，每轮需 \( O(m) \) 时间找最小入边和检测环，总复杂度 \( O(nm) \)，多项式时间。 示例演示 考虑一个简单有向图： 顶点：\( V = \{r, a, b, c\} \) 边及费用： \( (r,a)=4, (r,b)=3, (r,c)=6 \) \( (a,b)=2, (a,c)=5 \) \( (b,a)=1, (b,c)=4 \) \( (c,a)=3, (c,b)=2 \) 根为 \( r \)。 步骤 ： 初始 \( w(e)=c(e) \)，每个非根节点选最小入边： a: min(4,1,3)=1 选 (b,a) b: min(3,2,2)=2 选 (a,b) 或 (c,b)，任选 (a,b) c: min(6,5,4)=4 选 (b,c) 此时边集 \( F = \{(b,a), (a,b), (b,c)\} \)，有环 \( a \to b \to a \)。 收缩环 \( C=\{a,b\} \) 为超级节点 \( v_ C \)。 更新边权（以 \( a \) 为例）： 原入边 (r,a): w=4, 环中 a 的入边 (b,a) 权 1，新权重 4-1=3。 原入边 (c,a): 3-1=2。 类似更新 b 的入边（但 b 已在环内，环内边忽略）。 新图：顶点 {r, v_ C, c}，边： (r, v_ C)=min(3,2)=2（来自 (r,b) 和 (r,a) 更新后的最小） (c, v_ C)=min(2,2)=2 (v_ C, c)：从原环到 c 的边 (a,c)=5, (b,c)=4，需减去环中对应节点的入边权重，得 5-1=4, 4-2=2，最小 2。 在新图中，每个非根节点选最小入边： v_ C: min(2,2)=2 选 (r, v_ C) c: 入边 (b,c) 在收缩后为 (v_ C,c)=2，选之。 无边集无环，得到树形图。 展开环 \( C \)：新图中 (v_ C,c) 对应原边 (b,c)，(r, v_ C) 对应原边 (r,b)。在环 {a,b} 中，需去掉一条边使得树连通。原环边 (b,a) 和 (a,b) 中，去掉 (a,b)（因为 (r,b) 已进入环），保留 (b,a)。最终树：边集 {(r,b), (b,a), (b,c)}，总费用 3+1+4=8。 结论 通过线性规划对偶理论，我们解释了最小费用有向生成树的多项式时间算法（Edmonds 算法）本质上是在求解线性规划松弛，并且该松弛具有整数最优解。整个算法保证在多项式时间内找到精确最优解，而不仅仅是近似解。