基于线性规划的图最小费用有向生成树问题的多项式时间算法求解示例 问题描述 给定一个有向图 \( G = (V, E) \)，其中 \( V \) 是顶点集（\( |V| = n \)），\( E \) 是边集（每条边 \( (i,j) \) 有费用 \( c_ {ij} \geq 0 \)）。指定一个根节点 \( r \in V \)。我们需要找到一个以 \( r \) 为根的有向生成树（也称为“树枝形图”或“根指向树”），即： 每个非根节点 \( v \neq r \) 恰好有一条入边。 整个子图是无环的，并且从根 \( r \) 到每个节点有唯一的有向路径。 目标：最小化所选边的总费用。 这是一个经典的最优树形图问题，可通过线性规划建模，并有多项式时间算法（如Chu-Liu/Edmonds算法），但此处我们通过线性规划对偶的角度，展示其多项式可解性。 步骤1：线性规划建模 我们为每条边 \( (i,j) \in E \) 引入变量 \( x_ {ij} \in \{0,1\} \)，表示该边是否被选中。问题可建模为整数规划： \[ \begin{aligned} \min \quad & \sum_ {(i,j) \in E} c_ {ij} x_ {ij} \\ \text{s.t.} \quad & \sum_ {i: (i,j) \in E} x_ {ij} = 1, \quad \forall j \neq r \quad \text{(每个非根节点恰好一条入边)} \\ & \sum_ {(i,j) \in E(S)} x_ {ij} \leq |S| - 1, \quad \forall S \subseteq V \setminus \{r\}, S \neq \emptyset \quad \text{(消除有向环)} \\ & x_ {ij} \in \{0,1\}, \quad \forall (i,j) \in E \end{aligned} \] 其中 \( E(S) = \{ (i,j) \in E : i,j \in S \} \) 是 \( S \) 内的边集。第二个约束保证了每个非根节点子集内不形成有向环（即从根出发无法形成封闭回路）。 步骤2：线性规划松弛与对偶 将 \( x_ {ij} \in \{0,1\} \) 松弛为 \( x_ {ij} \geq 0 \)，得到线性规划（LP）。约束数量是指数级的，但我们可以通过其对偶来设计多项式时间算法。 对偶问题 ：为每个节点 \( j \neq r \) 的入度约束引入对偶变量 \( \pi_ j \in \mathbb{R} \)，为每个子集 \( S \) 的消除环约束引入对偶变量 \( y_ S \geq 0 \)。经过推导（详见组合优化教材），可得到简洁的对偶形式： \[ \begin{aligned} \max \quad & \sum_ {j \neq r} \pi_ j - \sum_ {S \neq \emptyset, S \subseteq V\setminus\{r\}} (|S|-1) y_ S \\ \text{s.t.} \quad & \pi_ j - \sum_ {S: i,j \in S} y_ S \leq c_ {ij}, \quad \forall (i,j) \in E, j \neq r \\ & y_ S \geq 0, \quad \forall S \end{aligned} \] 关键观察 ：在最优解中，我们可以将 \( y_ S \) 视为“收缩”集合 \( S \) 时的费用调整，这导向了一个多项式时间算法。 步骤3：算法思想（基于对偶的收缩法） 我们可以通过对偶变量动态调整边费用，并迭代地收缩环，最终构造出最小费用有向生成树。这本质上是 Edmonds算法 的线性规划对偶解释： 初始化 ：每个节点单独视为一个“超级节点”，当前图 \( G' = G \)。 为每个非根节点选择最小入边 ： 对每个 \( j \neq r \)，选择进入 \( j \) 的边中费用最小的，设为 \( (i^* , j) \)。 如果这些边不形成有向环，则已得到树，结束。 处理有向环 ： 如果所选边形成一个环 \( C \)，则将 \( C \) 中所有节点收缩为一个新的超级节点 \( v_ C \)。 调整与 \( C \) 相关边的费用：对进入 \( C \) 中节点 \( j \) 的边 \( (i,j) \)，新费用为 \( c_ {ij} - (c_ {i^* j} - \min\_in\_edge\_cost_ j) \)（这等价于在对偶中增加 \( y_ C \)）。 递归求解 ：在收缩后的新图上递归求解，得到一棵树。 展开环 ： 从环 \( C \) 中删除一条边（即环中进入某个节点的边），并添加递归解中进入超级节点 \( v_ C \) 的边，以保证无环性。 对偶变量的更新 ：在收缩环 \( C \) 时，对偶变量 \( y_ C \) 被设为环中边的“最小入边费用调整量”，这保证了原始-对偶可行性。 步骤4：具体计算示例 考虑一个有向图 \( V = \{r, a, b, c\} \)，根为 \( r \)。边及费用： \( (r,a)=3, (r,b)=4, (r,c)=5 \) \( (a,b)=2, (b,a)=1, (b,c)=3, (c,a)=4 \) 步骤4.1：为每个非根节点选最小入边 \( a \): 入边有 \( (r,a)=3, (c,a)=4, (b,a)=1 \) → 选 \( (b,a)=1 \) \( b \): 入边有 \( (r,b)=4, (a,b)=2 \) → 选 \( (a,b)=2 \) \( c \): 入边有 \( (r,c)=5, (b,c)=3 \) → 选 \( (b,c)=3 \) 当前所选边：\( (b,a), (a,b), (b,c) \) 包含环 \( a \to b \to a \)。 步骤4.2：收缩环 \( C = \{a,b\} \) 环上边费用：\( (b,a)=1, (a,b)=2 \)。 调整量 \( \delta = \min\{1,2\} = 1 \)（即对偶变量 \( y_ C = 1 \)）。 收缩为超级节点 \( v_ {ab} \)。 调整进入 \( a,b \) 的边费用： 进入 \( a \) 的边 \( (r,a) \): 新费用 = \( 3 - 1 = 2 \) 进入 \( b \) 的边无外部进入（原 \( (a,b) \) 在环内，不考虑） 注意：进入 \( b \) 的边 \( (r,b)=4 \) 在收缩后进入 \( v_ {ab} \)，但 \( b \) 在环内最小入边是 \( (a,b)=2 \)，调整量是 2？这里需注意：在标准Edmonds算法中，对环上每个节点，用其最小入边费用调整所有入边。更准确步骤： 重新计算： 对环 \( C=\{a,b\} \)： 对 \( a \)，最小入边费用 = 1（来自 \( b \)） 对 \( b \)，最小入边费用 = 2（来自 \( a \)） 调整量 \( \delta = 1 \)（环上最小入边费用）。 调整进入环的边费用： 边 \( (r,a) \): 新费用 = \( 3 - 1 = 2 \) 边 \( (r,b) \): 新费用 = \( 4 - 1 = 3 \) 边 \( (c,a) \): 新费用 = \( 4 - 1 = 3 \) 环内边 \( (b,a), (a,b) \) 移除。 收缩后新图节点：\( \{r, v_ {ab}, c\} \)。 新图的边（终点为 \( v_ {ab} \) 或 \( c \)）： 到 \( v_ {ab} \): \( (r, v_ {ab}) \) 费用 = min(调整后进入 a,b 的边) = min(2,3) = 2（取 \( (r,a) \) 调整后） 到 \( c \): 原有 \( (r,c)=5, (b,c)=3 \)，其中 \( (b,c) \) 的起点 b 在环内，所以变为 \( (v_ {ab}, c) \) 费用 = 3 注意：进入 c 的边 \( (b,c) \) 不需要调整，因为 c 不在环内。 步骤4.3：递归求解收缩后图 节点 \( c \) 最小入边：\( (v_ {ab}, c)=3 \) 与 \( (r,c)=5 \)，选 \( (v_ {ab}, c)=3 \)。 节点 \( v_ {ab} \) 最小入边：\( (r, v_ {ab})=2 \)。 无环，得到树：边 \( \{ (r, v_ {ab}), (v_ {ab}, c) \} \)。 步骤4.4：展开环 \( v_ {ab} \) 在环 \( \{a,b\} \) 中，原选入边：\( (b,a), (a,b) \)。 在收缩树中，进入 \( v_ {ab} \) 的边是 \( (r, v_ {ab}) \)，对应原图中 \( (r,a) \)（因为调整时用此边）。 在环中删除一条边，使得从 \( r \) 出发可达所有点：删除 \( (a,b) \)（因为保留 \( (b,a) \) 和新增 \( (r,a) \) 不形成环）。 最终边集：\( (r,a), (b,a), (v_ {ab}, c) \) 即 \( (b,c) \)。 树为：\( r \to a, b \to a, b \to c \)。但注意 \( b \) 无入边？实际上，\( b \) 的入边是 \( (a,b) \) 但被删除了。所以我们需要确保每个非根节点有入边：检查发现 \( b \) 无入边！这说明展开时需小心。 修正展开 ：标准方法是，在环 \( C \) 中，我们保留了环上所有最小入边，除了进入收缩树中进入超级节点的那个原节点，其入边用收缩树中进入超级节点的边替代。更准确步骤： 收缩树边：\( (r, v_ {ab}) \) 和 \( (v_ {ab}, c) \)。 展开 \( v_ {ab} \)： 边 \( (v_ {ab}, c) \) 在原图中对应 \( (b,c) \)，加入。 边 \( (r, v_ {ab}) \) 在原图中对应进入环的边，设为进入环中某个节点，我们选择进入 \( a \) 的 \( (r,a) \) 加入。 环 \( C \) 中，原选了 \( (b,a) \) 和 \( (a,b) \)。现在，因为 \( (r,a) \) 进入了 \( a \)，所以环中进入 \( a \) 的边 \( (b,a) \) 必须删除（否则 \( a \) 有两条入边）。保留 \( (a,b) \) 作为 \( b \) 的入边。 最终边集：\( (r,a), (a,b), (b,c) \)。 检查：每个非根节点恰一条入边（\( a \) 来自 \( r \)，\( b \) 来自 \( a \)，\( c \) 来自 \( b \)），无环，总费用 = 3+2+3=8。 步骤5：对偶变量与最优性 对偶变量 \( \pi_ a, \pi_ b, \pi_ c \) 可设为每个节点最小入边费用（在最后一次迭代中），例如 \( \pi_ a=3, \pi_ b=2, \pi_ c=3 \)。 收缩环时 \( y_ {\{a,b\}}=1 \)。 对偶目标：\( \sum_ {j\neq r} \pi_ j - \sum_ S (|S|-1)y_ S = (3+2+3) - (2-1)\times 1 = 8-1=7 \)。 但原始费用是8，为何对偶小1？说明对偶解未完全优化。实际上，我们可以调整对偶使等于原始最优值8，验证原始-对偶互补松弛条件。 互补松弛 ： 原始边变量 \( x_ {ij}>0 \) 对应边 \( (r,a),(a,b),(b,c) \) 应满足对偶约束紧：\( \pi_ j - \sum_ {S: i,j\in S} y_ S = c_ {ij} \)。 代入得： \( (r,a) \): \( \pi_ a - y_ {\{a,b\}} = 3 \) → \( \pi_ a = 3+1=4 \) \( (a,b) \): \( \pi_ b - y_ {\{a,b\}} = 2 \) → \( \pi_ b = 2+1=3 \) \( (b,c) \): \( \pi_ c = 3 \)（c不在集合S中） 对偶目标：\( (4+3+3) - 1 = 9-1=8 \)，与原始最优值相等，证明最优。 步骤6：算法复杂度 每次迭代至少减少一个节点，每次找最小入边和检测环可用DFS/BFS，总复杂度 \( O(nm) \) 或更优实现 \( O(m + n\log n) \)。该算法本质上是在求解上述线性规划的对偶，并通过构造原始解证明整数性（因为该线性规划的可行域是多面体，其顶点都是整数解）。 总结 最小费用有向生成树问题可通过线性规划建模，其松弛具有整数最优解。基于原始-对偶思想的收缩算法（Edmonds算法）能在多项式时间内求解，并通过调整对偶变量保证最优性。此问题展示了组合优化中线性规划对偶如何引导高效算法设计。