基于线性规划的图最小费用循环流问题的多项式时间缩放成本缩放（Capacity-Scaling）算法求解示例
字数 4811 2025-12-18 04:22:03

基于线性规划的图最小费用循环流问题的多项式时间缩放成本缩放（Capacity-Scaling）算法求解示例

题目描述

考虑一个有向图 \(G=(V, E)\)，每条边 \(e \in E\) 具有容量 \(u_e > 0\)（上界）和单位流量成本 \(c_e \in \mathbb{R}\)。注意，这里没有源点和汇点，我们处理的是循环流（Circulation）问题。给定一个循环流 \(f: E \to \mathbb{R}^+\)，需要满足以下条件：

  1. 容量约束：对于每条边 \(e \in E\)，有 \(0 \le f_e \le u_e\)。
  2. 流量守恒：对于每个节点 \(v \in V\)，流入的流量等于流出的流量，即 \(\sum_{e \in \delta^{-}(v)} f_e = \sum_{e \in \delta^{+}(v)} f_e\)，其中 \(\delta^{-}(v)\) 表示进入节点 \(v\) 的边集，\(\delta^{+}(v)\) 表示离开节点 \(v\) 的边集。

目标是最小化总成本 \(\sum_{e \in E} c_e f_e\)。此问题称为最小费用循环流问题（Minimum-Cost Circulation Problem）。

今天，我将详细讲解一种解决该问题的多项式时间算法——缩放成本缩放算法（Cost Scaling with Capacity Scaling），它结合了容量缩放和成本缩放的思想，能在强多项式时间内找到最优解。我会从问题建模、算法原理、详细步骤和一个小型算例来逐步阐述。

第一部分：问题建模与线性规划形式

1. 线性规划模型

设决策变量为 \(f_e\) 表示边 \(e\) 上的流量。
最小费用循环流问题可建模为以下线性规划：

\[\begin{aligned} \min \quad & \sum_{e \in E} c_e f_e \\ \text{s.t.} \quad & \sum_{e \in \delta^{+}(v)} f_e - \sum_{e \in \delta^{-}(v)} f_e = 0, \quad \forall v \in V \quad &\text{(流量守恒)} \\ & 0 \le f_e \le u_e, \quad \forall e \in E \quad &\text{(容量约束)} \end{aligned} \]

该问题是对偶可行的（当所有 \(c_e \ge 0\) 时），但一般 \(c_e\) 可正可负，因此需要一种能处理任意成本的算法。缩放成本缩放算法通过迭代调整“近似最优”条件来逼近最优解。

第二部分：算法核心概念与预备知识

2. 残差图与约化成本（Reduced Cost）

对于给定流 \(f\)，定义残差图 \(G_f\)：

  • 对于原图边 \(e = (u, v)\)：
    • 若 \(f_e < u_e\)，则在 \(G_f\) 中加入正向边 \((u, v)\)，残差容量 \(r_e = u_e - f_e\)，成本 \(c_e\)。
    • 若 \(f_e > 0\)，则在 \(G_f\) 中加入反向边 \((v, u)\)，残差容量 \(r_e = f_e\)，成本 \(-c_e\)。

设 \(p: V \to \mathbb{R}\) 是节点势（node potential）。对于残差图中的边 \((u, v)\)，定义其约化成本为：

\[c_{uv}^p = c_{uv} + p(u) - p(v) \]

若对所有残差边有 \(c_{uv}^p \ge 0\)，则当前流 \(f\) 是最优的（互补松弛条件）。

3. ε-最优条件（ε-Optimality）

给定参数 ε > 0，若存在节点势 \(p\) 使得对所有残差边 \((u, v)\) 满足：

\[c_{uv}^p \ge -\varepsilon \]

则称流 \(f\) 是 ε-最优 的。当 ε 足够小时（例如 ε < 1/|V|），ε-最优流即为最优流。

缩放成本缩放算法的思路：

  1. 从较大的 ε 开始，找到一个 ε-最优流。
  2. 逐步减小 ε（如 ε ← ε/α，α>1），并将当前流调整为新的 ε-最优流。
  3. 当 ε 足够小时，得到最优流。

但单纯成本缩放在最坏情况下可能不是强多项式。因此，本算法结合容量缩放：在每一轮缩放中，我们不仅缩放成本容差 ε，还限制考虑那些残差容量至少为某个阈值 Δ 的边，从而保证每轮增广都能输送足够大的流量，控制迭代次数。

第三部分：缩放成本缩放算法详细步骤

算法分为外层循环（成本缩放）和内层循环（容量缩放）。

步骤 1：初始化

  • 设置初始 ε = max{|c_e|}（或一个更大的数，例如 C = max{|c_e|}，取 ε = C）。
  • 初始流 \(f = 0\)。
  • 初始势 \(p(v) = 0\)，∀v ∈ V。

步骤 2：成本缩放主循环

当 ε ≥ 1/|V| 时（或更小的阈值）执行：

  1. 容量缩放子循环：

    • 令 Δ = max{u_e}（或一个较大的容量值，例如 2^⌊log₂U⌋，U是最大容量）。
    • 当 Δ ≥ 1 时执行：
      a. 构造 Δ-残差图 \(G_{f,Δ}\)：只包含那些残差容量 ≥ Δ 的边。
      b. 在 \(G_{f,Δ}\) 中，若存在边 \((u, v)\) 的约化成本 \(c_{uv}^p < -\varepsilon\)，则这是一条“负约化成本边”，可能带来改进机会。
      c. 尝试沿这样的边进行流量推送（类似于推流操作），或在由这些边组成的图中寻找增广环（负费用环）并消去（cycle canceling），但为了效率，我们通常使用改进操作：沿满足 \(c_{uv}^p < -\varepsilon\) 且残差容量 ≥ Δ 的边尽可能推送流量（受 Δ 限制），并更新势使得约化成本逐步满足 ε-最优条件。
      d. 流量推送后，更新流 \(f\) 和势 \(p\)，使得算法维持 ε-最优性。
      e. 若当前 Δ-残差图中没有满足 \(c_{uv}^p < -\varepsilon\) 且残差容量 ≥ Δ 的边，则令 Δ = Δ/2（容量缩放），进入更小的容量尺度。
    • 容量缩放结束后，我们得到一个关于当前 ε 的 ε-最优流，且所有边都满足 \(c_{uv}^p \ge -\varepsilon\)。

  2. 缩小 ε：令 ε = ε / α，通常 α = 2（或一个大于1的常数）。进入下一轮成本缩放。

步骤 3：终止

当 ε < 1/|V| 时，当前流 \(f\) 即为最优解。

第四部分：一个小型算例演示

考虑一个简单有向图 \(G\)：

  • 节点 V = {1, 2, 3}
  • 边 E 及参数：
    • e1: (1→2), u=5, c=4
    • e2: (2→3), u=5, c=-2
    • e3: (3→1), u=5, c=3
      目标：求最小费用循环流。

初始化

ε = max{|4|, |-2|, |3|} = 4。
f = 0。
p(1)=p(2)=p(3)=0。

第一轮成本缩放：ε=4

容量缩放初始化 Δ = 5（最大容量）。

Δ=5：
构造 Δ-残差图：所有边残差容量为5 ≥ 5，全部包含。
计算约化成本（p=0）：

  • c12^p = 4 ≥ -4 ✅
  • c23^p = -2 < -4? 否，-2 > -4 ✅
  • c31^p = 3 ≥ -4 ✅
    没有边满足 \(c_{uv}^p < -4\)，所以无需推送。
    Δ 缩小为 Δ=2.5（为简化，用整数步骤演示，实际可连续缩放，但这里假设Δ除2后为2）。

Δ=2：
检查所有残差容量 ≥ 2 的边（目前全部满足）。
约化成本同上，仍无非负情况。
Δ=1：
同样无非负情况。

此时，流 f=0 是 ε=4 下的 ε-最优流。

缩小 ε： ε = 4/2 = 2。

第二轮成本缩放：ε=2

重置 Δ=5。
Δ=5：
约化成本：
c23^p = -2，检查是否 < -ε = -2？ 否（等于 -2），所以不满足严格小于。
Δ 缩放至 Δ=2。
Δ=2：
c23^p = -2 < -2？ 否（等于），仍不触发。
实际上，当前流 f=0 在 ε=2 下也是 ε-最优的，因为最负的约化成本是 -2 ≥ -2。
缩小 ε： ε = 2/2 = 1。

第三轮成本缩放：ε=1

Δ=5：
c23^p = -2 < -1？ 是！ 边 (2,3) 在残差图中（正向边），残差容量=5 ≥ 5，我们可以沿此边推送流量以降低成本。
推送流量：沿 (2,3) 推送 min(残差容量, Δ) = min(5, 5)=5 单位流量。
更新流：f23 = 5。
但这样破坏了节点2的流量守恒（流入0，流出5），节点3也失衡（流入5，流出0）。因此需要同时调整其他边流量以满足守恒。

实际上，为了维持循环流，我们需要沿一个环推送流量。检查图中是否存在包含(2,3)的负费用环？由边(2,3)（c=-2）、(3,1)（c=3）、(1,2)（c=4）组成环，总成本 = -2+3+4=5 >0，不是负环。然而在 ε-最优框架下，我们允许沿约化成本 < -ε 的边推送流量，然后通过势更新和后续调整恢复 ε-最优性。

为了简化演示，我们采用一个更系统的做法：当发现约化成本 < -ε 的边时，可以沿该边尽可能推送流量（受 Δ 限制），然后更新节点势以“修复”约化成本，并可能引发其他边不满足条件，需要继续处理。

但为了清晰展示最终结果，我们直接跳到算法收敛后的状态：经过若干轮调整（推送流量并更新势），最终会找到一个流，使得所有约化成本 ≥ -ε。当 ε=1 足够小时，流可能已经是最优。

让我们直接计算最优解：
观察目标函数：成本 c12=4, c23=-2, c31=3。
我们希望尽可能多用负成本边 (2,3)，同时满足容量和守恒。
设流为 f12=a, f23=b, f31=c。
守恒条件：
节点1: a - c = 0 → a = c。
节点2: b - a = 0 → b = a。
节点3: c - b = 0 → c = b。
所以 a=b=c=x。
容量约束：0 ≤ x ≤ 5。
总成本 = 4x - 2x + 3x = 5x。
要最小化 5x，应取最小 x=0。因此最优流是全零流，成本 0。

但等等，若 x=0，成本为 0。检查是否存在更优解？考虑环流量为负？但流量非负。所以最优就是零流。

在本例中，零流确实是最优解，因为任何正流量都会产生正成本（环总成本5>0）。算法在 ε 缩小到 <1 时，会确认零流是最优的。

第五部分：算法复杂度与总结

  • 成本缩放：从 ε = C 缩小到 ε < 1/|V|，共 O(log (C|V|)) 轮。
  • 容量缩放：每轮成本缩放中，Δ 从最大值缩小到 1，共 O(log U) 轮。
  • 每轮 Δ 缩放内的推送/调整操作可在 O(|V| |E|) 或更优时间内完成。
  • 总复杂度：O(|V| |E| log U log (C|V|))，这是强多项式时间。

总结：
缩放成本缩放算法通过双重缩放（成本容差 ε 和容量阈值 Δ）保证了多项式迭代次数，同时利用势函数维持 ε-最优性，逐步逼近最优循环流。该算法融合了成本缩放和容量缩放的优点，是求解最小费用循环流问题的高效强多项式算法之一。

通过本例，您应理解该算法的框架、ε-最优条件的作用以及双重缩放如何控制算法进度。

基于线性规划的图最小费用循环流问题的多项式时间缩放成本缩放（Capacity-Scaling）算法求解示例 题目描述 考虑一个有向图 \(G=(V, E)\)，每条边 \(e \in E\) 具有容量 \(u_ e > 0\)（上界）和单位流量成本 \(c_ e \in \mathbb{R}\)。注意，这里没有源点和汇点，我们处理的是 循环流（Circulation） 问题。给定一个循环流 \(f: E \to \mathbb{R}^+\)，需要满足以下条件： 容量约束 ：对于每条边 \(e \in E\)，有 \(0 \le f_ e \le u_ e\)。 流量守恒 ：对于每个节点 \(v \in V\)，流入的流量等于流出的流量，即 \(\sum_ {e \in \delta^{-}(v)} f_ e = \sum_ {e \in \delta^{+}(v)} f_ e\)，其中 \(\delta^{-}(v)\) 表示进入节点 \(v\) 的边集，\(\delta^{+}(v)\) 表示离开节点 \(v\) 的边集。 目标是最小化总成本 \(\sum_ {e \in E} c_ e f_ e\)。此问题称为 最小费用循环流问题（Minimum-Cost Circulation Problem） 。 今天，我将详细讲解一种解决该问题的多项式时间算法—— 缩放成本缩放算法（Cost Scaling with Capacity Scaling） ，它结合了容量缩放和成本缩放的思想，能在强多项式时间内找到最优解。我会从问题建模、算法原理、详细步骤和一个小型算例来逐步阐述。 第一部分：问题建模与线性规划形式 1. 线性规划模型 设决策变量为 \(f_ e\) 表示边 \(e\) 上的流量。 最小费用循环流问题可建模为以下线性规划： \[ \begin{aligned} \min \quad & \sum_ {e \in E} c_ e f_ e \\ \text{s.t.} \quad & \sum_ {e \in \delta^{+}(v)} f_ e - \sum_ {e \in \delta^{-}(v)} f_ e = 0, \quad \forall v \in V \quad &\text{(流量守恒)} \\ & 0 \le f_ e \le u_ e, \quad \forall e \in E \quad &\text{(容量约束)} \end{aligned} \] 该问题是对偶可行的（当所有 \(c_ e \ge 0\) 时），但一般 \(c_ e\) 可正可负，因此需要一种能处理任意成本的算法。缩放成本缩放算法通过迭代调整“近似最优”条件来逼近最优解。 第二部分：算法核心概念与预备知识 2. 残差图与约化成本（Reduced Cost） 对于给定流 \(f\)，定义残差图 \(G_ f\)： 对于原图边 \(e = (u, v)\)： 若 \(f_ e < u_ e\)，则在 \(G_ f\) 中加入正向边 \((u, v)\)，残差容量 \(r_ e = u_ e - f_ e\)，成本 \(c_ e\)。 若 \(f_ e > 0\)，则在 \(G_ f\) 中加入反向边 \((v, u)\)，残差容量 \(r_ e = f_ e\)，成本 \(-c_ e\)。 设 \(p: V \to \mathbb{R}\) 是节点势（node potential）。对于残差图中的边 \((u, v)\)，定义其 约化成本 为： \[ c_ {uv}^p = c_ {uv} + p(u) - p(v) \] 若对所有残差边有 \(c_ {uv}^p \ge 0\)，则当前流 \(f\) 是最优的（互补松弛条件）。 3. ε-最优条件（ε-Optimality） 给定参数 ε > 0，若存在节点势 \(p\) 使得对所有残差边 \((u, v)\) 满足： \[ c_ {uv}^p \ge -\varepsilon \] 则称流 \(f\) 是 ε-最优 的。当 ε 足够小时（例如 ε < 1/|V|），ε-最优流即为最优流。 缩放成本缩放算法 的思路： 从较大的 ε 开始，找到一个 ε-最优流。 逐步减小 ε（如 ε ← ε/α，α>1），并将当前流调整为新的 ε-最优流。 当 ε 足够小时，得到最优流。 但单纯成本缩放在最坏情况下可能不是强多项式。因此，本算法 结合容量缩放 ：在每一轮缩放中，我们不仅缩放成本容差 ε，还限制考虑那些残差容量至少为某个阈值 Δ 的边，从而保证每轮增广都能输送足够大的流量，控制迭代次数。 第三部分：缩放成本缩放算法详细步骤 算法分为外层循环（成本缩放）和内层循环（容量缩放）。 步骤 1：初始化 设置初始 ε = max{|c_ e|}（或一个更大的数，例如 C = max{|c_ e|}，取 ε = C）。 初始流 \(f = 0\)。 初始势 \(p(v) = 0\)，∀v ∈ V。 步骤 2：成本缩放主循环 当 ε ≥ 1/|V| 时（或更小的阈值）执行： 容量缩放子循环 ： 令 Δ = max{u_ e}（或一个较大的容量值，例如 2^⌊log₂U⌋，U是最大容量）。 当 Δ ≥ 1 时执行： a. 构造 Δ-残差图 \(G_ {f,Δ}\)：只包含那些残差容量 ≥ Δ 的边。 b. 在 \(G_ {f,Δ}\) 中，若存在边 \((u, v)\) 的约化成本 \(c_ {uv}^p < -\varepsilon\)，则这是一条“负约化成本边”，可能带来改进机会。 c. 尝试沿这样的边进行流量推送（类似于推流操作），或在由这些边组成的图中寻找增广环（负费用环）并消去（cycle canceling），但为了效率，我们通常使用 改进操作 ：沿满足 \(c_ {uv}^p < -\varepsilon\) 且残差容量 ≥ Δ 的边尽可能推送流量（受 Δ 限制），并更新势使得约化成本逐步满足 ε-最优条件。 d. 流量推送后，更新流 \(f\) 和势 \(p\)，使得算法维持 ε-最优性。 e. 若当前 Δ-残差图中没有满足 \(c_ {uv}^p < -\varepsilon\) 且残差容量 ≥ Δ 的边，则令 Δ = Δ/2（容量缩放），进入更小的容量尺度。 容量缩放结束后，我们得到一个关于当前 ε 的 ε-最优流，且所有边都满足 \(c_ {uv}^p \ge -\varepsilon\)。 缩小 ε ：令 ε = ε / α，通常 α = 2（或一个大于1的常数）。进入下一轮成本缩放。 步骤 3：终止 当 ε < 1/|V| 时，当前流 \(f\) 即为最优解。 第四部分：一个小型算例演示 考虑一个简单有向图 \(G\)： 节点 V = {1, 2, 3} 边 E 及参数： e1: (1→2), u=5, c=4 e2: (2→3), u=5, c=-2 e3: (3→1), u=5, c=3 目标：求最小费用循环流。 初始化 ε = max{|4|, |-2|, |3|} = 4。 f = 0。 p(1)=p(2)=p(3)=0。 第一轮成本缩放：ε=4 容量缩放初始化 Δ = 5（最大容量）。 Δ=5： 构造 Δ-残差图：所有边残差容量为5 ≥ 5，全部包含。 计算约化成本（p=0）： c12^p = 4 ≥ -4 ✅ c23^p = -2 < -4? 否，-2 > -4 ✅ c31^p = 3 ≥ -4 ✅ 没有边满足 \(c_ {uv}^p < -4\)，所以无需推送。 Δ 缩小为 Δ=2.5（为简化，用整数步骤演示，实际可连续缩放，但这里假设Δ除2后为2）。 Δ=2： 检查所有残差容量 ≥ 2 的边（目前全部满足）。 约化成本同上，仍无非负情况。 Δ=1： 同样无非负情况。 此时，流 f=0 是 ε=4 下的 ε-最优流。 缩小 ε： ε = 4/2 = 2。 第二轮成本缩放：ε=2 重置 Δ=5。 Δ=5： 约化成本： c23^p = -2，检查是否 < -ε = -2？ 否（等于 -2），所以不满足严格小于。 Δ 缩放至 Δ=2。 Δ=2： c23^p = -2 < -2？ 否（等于），仍不触发。 实际上，当前流 f=0 在 ε=2 下也是 ε-最优的，因为最负的约化成本是 -2 ≥ -2。 缩小 ε： ε = 2/2 = 1。 第三轮成本缩放：ε=1 Δ=5： c23^p = -2 < -1？ 是！ 边 (2,3) 在残差图中（正向边），残差容量=5 ≥ 5，我们可以沿此边推送流量以降低成本。 推送流量：沿 (2,3) 推送 min(残差容量, Δ) = min(5, 5)=5 单位流量。 更新流：f23 = 5。 但这样破坏了节点2的流量守恒（流入0，流出5），节点3也失衡（流入5，流出0）。因此需要同时调整其他边流量以满足守恒。 实际上，为了维持循环流，我们需要 沿一个环 推送流量。检查图中是否存在包含(2,3)的负费用环？由边(2,3)（c=-2）、(3,1)（c=3）、(1,2)（c=4）组成环，总成本 = -2+3+4=5 >0，不是负环。然而在 ε-最优框架下，我们允许沿约化成本 < -ε 的边推送流量，然后通过势更新和后续调整恢复 ε-最优性。 为了简化演示，我们采用一个更系统的做法：当发现约化成本 < -ε 的边时，可以沿该边尽可能推送流量（受 Δ 限制），然后更新节点势以“修复”约化成本，并可能引发其他边不满足条件，需要继续处理。 但为了清晰展示最终结果，我们直接跳到算法收敛后的状态：经过若干轮调整（推送流量并更新势），最终会找到一个流，使得所有约化成本 ≥ -ε。当 ε=1 足够小时，流可能已经是最优。 让我们直接计算 最优解 ： 观察目标函数：成本 c12=4, c23=-2, c31=3。 我们希望尽可能多用负成本边 (2,3)，同时满足容量和守恒。 设流为 f12=a, f23=b, f31=c。 守恒条件： 节点1: a - c = 0 → a = c。 节点2: b - a = 0 → b = a。 节点3: c - b = 0 → c = b。 所以 a=b=c=x。 容量约束：0 ≤ x ≤ 5。 总成本 = 4x - 2x + 3x = 5x。 要最小化 5x，应取最小 x=0。因此最优流是全零流，成本 0。 但等等，若 x=0，成本为 0。检查是否存在更优解？考虑环流量为负？但流量非负。所以最优就是零流。 在本例中，零流确实是最优解，因为任何正流量都会产生正成本（环总成本5>0）。算法在 ε 缩小到 <1 时，会确认零流是最优的。 第五部分：算法复杂度与总结 成本缩放 ：从 ε = C 缩小到 ε < 1/|V|，共 O(log (C|V|)) 轮。 容量缩放 ：每轮成本缩放中，Δ 从最大值缩小到 1，共 O(log U) 轮。 每轮 Δ 缩放内的推送/调整操作可在 O(|V| |E|) 或更优时间内完成。 总复杂度：O(|V| |E| log U log (C|V|))，这是强多项式时间。 总结 ： 缩放成本缩放算法通过双重缩放（成本容差 ε 和容量阈值 Δ）保证了多项式迭代次数，同时利用势函数维持 ε-最优性，逐步逼近最优循环流。该算法融合了成本缩放和容量缩放的优点，是求解最小费用循环流问题的高效强多项式算法之一。 通过本例，您应理解该算法的框架、ε-最优条件的作用以及双重缩放如何控制算法进度。