基于线性规划的图最小费用流问题的多项式时间最小平均回路消去算法求解示例

字数 3536 2025-12-21 06:59:03

基于线性规划的图最小费用流问题的多项式时间最小平均回路消去算法求解示例

1. 问题描述

最小费用流问题（Minimum Cost Flow Problem） 是图论和组合优化中的一个经典问题。
给定一个有向图 \(G = (V, E)\)，其中：

\(V\) 是顶点集合，\(|V| = n\)。
\(E\) 是边集合，\(|E| = m\)。
每条边 \(e = (u, v)\) 有一个容量 \(c_e \geq 0\) 和一个单位流量费用 \(w_e\)（可以是负数）。
每个顶点 \(v\) 有一个净需求（净供给） \(b_v\)：
- 若 \(b_v > 0\)，表示顶点 \(v\) 是供应点，需向外提供 \(b_v\) 单位流量。
- 若 \(b_v < 0\)，表示顶点 \(v\) 是需求点，需接收 \(-b_v\) 单位流量。
- 若 \(b_v = 0\)，表示顶点 \(v\) 是转运点。
要求满足流量平衡：总供应量 \(\sum_{v: b_v > 0} b_v = \sum_{v: b_v < 0} -b_v\)。

目标：找到一个可行流 \(f: E \to \mathbb{R}_{\ge 0}\)，满足容量约束 \(0 \le f_e \le c_e\) 和流量平衡约束，并最小化总费用：

\[\sum_{e \in E} w_e f_e \]

2. 算法背景

最小平均回路消去算法（Minimum Mean Cycle Cancelling, MMCC） 是 Goldberg 和 Tarjan 提出的一种多项式时间算法，用于求解最小费用流问题。
它基于一个关键观察：如果一个流是最小费用流，那么残余网络中不存在负费用回路。
因此，算法反复找到残余网络中平均费用最小的负回路，并沿该回路推送尽可能多的流量，直到残余网络中无负回路为止。

为什么最小平均回路消去是多项式时间？
因为每次迭代消去的回路具有特殊的“最小平均费用”性质，保证了迭代次数为 \(O(nm \log(nW))\)，其中 \(W\) 是最大费用绝对值。整体复杂度为 \(O(nm^2 \log n \cdot \log(nW))\)，属于强多项式时间算法。

3. 算法步骤详解

步骤1：建立初始可行流

首先需要找到一个初始可行流（例如，可以用最大流算法在扩展网络上求出一个满足供需的可行流）。
更简单的方法：如果所有容量非负且供需平衡，可以先设所有流为零，然后通过添加人工边（大费用）构造一个初始可行流，但通常直接假设初始可行流存在或使用两阶段法。

步骤2：构造残余网络 \(G_f\)

对原图中每条边 \(e = (u, v)\)：
- 若 \(f_e < c_e\)，则在残余网络中加一条前向边 \((u, v)\)，容量为 \(c_e - f_e\)，费用为 \(w_e\)。
- 若 \(f_e > 0\)，则在残余网络中加一条反向边 \((v, u)\)，容量为 \(f_e\)，费用为 \(-w_e\)。
残余网络中的边费用可能是负的，负费用回路表示可以通过沿该回路增流来降低总费用。

步骤3：寻找最小平均回路

定义回路 \(C\) 的平均费用为：

\[ \mu(C) = \frac{\sum_{e \in C} w_e}{|C|} \]

目标：在残余网络中找到平均费用最小的回路 \(C_{\min}\)（即使 \(\mu(C_{\min})\) 最小）。
寻找最小平均回路可以用 Karp 算法（1978）在 \(O(nm)\) 时间内完成：
- 令 \(d_k(v)\) 表示从某个起点到顶点 \(v\) 恰好经过 \(k\) 条边的最小费用路径长度（允许负边）。
- 通过动态规划计算 \(d_k(v)\) 对所有 \(k=0,1,\dots,n\) 和所有顶点 \(v\)。
- 最小平均回路值由下式给出：

\[ \mu^* = \min_{v \in V} \max_{0 \le k \le n-1} \frac{d_n(v) - d_k(v)}{n - k} \]

同时可以回溯找到对应的回路。

步骤4：沿回路增流

对找到的最小平均回路 \(C_{\min}\)，计算其能推送的最大流量：

\[ \Delta = \min_{e \in C_{\min}} r_e \]

其中 \(r_e\) 是残余网络中边 \(e\) 的容量。

沿 \(C_{\min}\) 推送 \(\Delta\) 单位流量：
- 对前向边：增加流量。
- 对反向边：减少流量。
更新残余网络。

步骤5：重复与终止

重复步骤 2–4，直到残余网络中不存在负费用回路（此时流是最小费用流）。
注意：最小平均回路可能费用为零（非负），此时算法终止。

4. 为什么最小平均回路消去能保证多项式时间？

关键引理：设 \(\mu(f)\) 是当前流 \(f\) 对应的残余网络中最小平均回路的值（若无非负回路，则 \(\mu(f) \ge 0\)）。
每次消去最小平均回路后，\(\mu(f)\) 不会减小，并且每经过 \(m\) 次迭代，\(\mu(f)\) 至少增加一个因子 \((1 - 1/n)\) 或变为非负。
因此，负回路消去的总次数为 \(O(nm \log(nW))\)。

5. 实例演示

考虑一个有向图：

顶点：\(s, a, b, t\)，净需求：\(b_s = 4, b_a = 0, b_b = 0, b_t = -4\)。
边与参数：
1. \((s, a)\): 容量 5，费用 2
2. \((s, b)\): 容量 3，费用 4
3. \((a, b)\): 容量 2，费用 -1
4. \((a, t)\): 容量 3，费用 3
5. \((b, t)\): 容量 4，费用 1

步骤1：初始可行流设为 \(f = 0\)，满足容量约束但不满足供需。需先找可行流（比如从 s 到 t 送 4 单位）。为简化，假设我们已通过某种方法得到初始流：
\(f_{sa} = 3, f_{sb} = 1, f_{ab} = 0, f_{at} = 3, f_{bt} = 1\)。
检查平衡：s 流出 4，t 流入 4，中间点平衡，可行。

步骤2：构造残余网络（略去具体数值），计算边费用。

步骤3：在残余网络中找最小平均回路。
可能找到回路 \(a \to b \to a\)（通过残余边 \((a,b)\) 和反向边 \((b,a)\)），其平均费用为 \((-1 + (-4))/2 = -2.5\)，为负。

步骤4：沿此回路推流，例如推 1 单位，更新流：
\(f_{ab}\) 增加 1，\(f_{sb}\) 减少 1（因为反向边推流相当于减少原流），同时调整相关边以满足平衡。

步骤5：重新计算残余网络，继续寻找最小平均回路，直到无负回路。

最终得到最小费用流：
\(f_{sa} = 4, f_{sb} = 0, f_{ab} = 1, f_{at} = 3, f_{bt} = 2\)，总费用 \(4 \times 2 + 0 \times 4 + 1 \times (-1) + 3 \times 3 + 2 \times 1 = 8 - 1 + 9 + 2 = 18\)。

6. 算法总结

输入：有向图 \(G\)，容量 \(c\)，费用 \(w\)，净需求 \(b\)。
输出：最小费用流 \(f\)。
步骤：
1. 找初始可行流（可借助辅助网络）。
2. 构建残余网络 \(G_f\)。
3. 在 \(G_f\) 中用 Karp 算法找最小平均回路 \(C\)。
4. 若 \(\mu(C) \ge 0\)，停止；否则沿 \(C\) 推送最大可能流量。
5. 更新流，返回步骤 2。
时间复杂度：\(O(nm^2 \log n \cdot \log(nW))\)。
特点：强多项式时间，不依赖费用值的大小；适合理论分析，实际中可能不如成本缩放算法快，但保证了多项式收敛性。

基于线性规划的图最小费用流问题的多项式时间最小平均回路消去算法求解示例 1. 问题描述最小费用流问题（Minimum Cost Flow Problem）是图论和组合优化中的一个经典问题。给定一个有向图 \( G = (V, E) \)，其中： \( V \) 是顶点集合，\( |V| = n \)。 \( E \) 是边集合，\( |E| = m \)。每条边 \( e = (u, v) \) 有一个容量 \( c_ e \geq 0 \) 和一个单位流量费用 \( w_ e \)（可以是负数）。每个顶点 \( v \) 有一个净需求（净供给） \( b_ v \)：若 \( b_ v > 0 \)，表示顶点 \( v \) 是供应点，需向外提供 \( b_ v \) 单位流量。若 \( b_ v < 0 \)，表示顶点 \( v \) 是需求点，需接收 \( -b_ v \) 单位流量。若 \( b_ v = 0 \)，表示顶点 \( v \) 是转运点。要求满足流量平衡：总供应量 \( \sum_ {v: b_ v > 0} b_ v = \sum_ {v: b_ v < 0} -b_ v \)。目标：找到一个可行流 \( f: E \to \mathbb{R} {\ge 0} \)，满足容量约束 \( 0 \le f_ e \le c_ e \) 和流量平衡约束，并最小化总费用： \[ \sum {e \in E} w_ e f_ e \] 2. 算法背景最小平均回路消去算法（Minimum Mean Cycle Cancelling, MMCC）是 Goldberg 和 Tarjan 提出的一种多项式时间算法，用于求解最小费用流问题。它基于一个关键观察：如果一个流是最小费用流，那么残余网络中不存在负费用回路。因此，算法反复找到残余网络中平均费用最小的负回路，并沿该回路推送尽可能多的流量，直到残余网络中无负回路为止。为什么最小平均回路消去是多项式时间？因为每次迭代消去的回路具有特殊的“最小平均费用”性质，保证了迭代次数为 \( O(nm \log(nW)) \)，其中 \( W \) 是最大费用绝对值。整体复杂度为 \( O(nm^2 \log n \cdot \log(nW)) \)，属于强多项式时间算法。 3. 算法步骤详解步骤1：建立初始可行流首先需要找到一个初始可行流（例如，可以用最大流算法在扩展网络上求出一个满足供需的可行流）。更简单的方法：如果所有容量非负且供需平衡，可以先设所有流为零，然后通过添加人工边（大费用）构造一个初始可行流，但通常直接假设初始可行流存在或使用两阶段法。步骤2：构造残余网络 \( G_ f \) 对原图中每条边 \( e = (u, v) \)：若 \( f_ e < c_ e \)，则在残余网络中加一条前向边 \( (u, v) \)，容量为 \( c_ e - f_ e \)，费用为 \( w_ e \)。若 \( f_ e > 0 \)，则在残余网络中加一条反向边 \( (v, u) \)，容量为 \( f_ e \)，费用为 \( -w_ e \)。残余网络中的边费用可能是负的，负费用回路表示可以通过沿该回路增流来降低总费用。步骤3：寻找最小平均回路定义回路 \( C \) 的平均费用为： \[ \mu(C) = \frac{\sum_ {e \in C} w_ e}{|C|} \] 目标：在残余网络中找到平均费用最小的回路 \( C_ {\min} \)（即使 \( \mu(C_ {\min}) \) 最小）。寻找最小平均回路可以用 Karp 算法（1978）在 \( O(nm) \) 时间内完成：令 \( d_ k(v) \) 表示从某个起点到顶点 \( v \) 恰好经过 \( k \) 条边的最小费用路径长度（允许负边）。通过动态规划计算 \( d_ k(v) \) 对所有 \( k=0,1,\dots,n \) 和所有顶点 \( v \)。最小平均回路值由下式给出： \[ \mu^* = \min_ {v \in V} \max_ {0 \le k \le n-1} \frac{d_ n(v) - d_ k(v)}{n - k} \] 同时可以回溯找到对应的回路。步骤4：沿回路增流对找到的最小平均回路 \( C_ {\min} \)，计算其能推送的最大流量： \[ \Delta = \min_ {e \in C_ {\min}} r_ e \] 其中 \( r_ e \) 是残余网络中边 \( e \) 的容量。沿 \( C_ {\min} \) 推送 \( \Delta \) 单位流量：对前向边：增加流量。对反向边：减少流量。更新残余网络。步骤5：重复与终止重复步骤 2–4，直到残余网络中不存在负费用回路（此时流是最小费用流）。注意：最小平均回路可能费用为零（非负），此时算法终止。 4. 为什么最小平均回路消去能保证多项式时间？关键引理：设 \( \mu(f) \) 是当前流 \( f \) 对应的残余网络中最小平均回路的值（若无非负回路，则 \( \mu(f) \ge 0 \)）。每次消去最小平均回路后，\( \mu(f) \) 不会减小，并且每经过 \( m \) 次迭代，\( \mu(f) \) 至少增加一个因子 \( (1 - 1/n) \) 或变为非负。因此，负回路消去的总次数为 \( O(nm \log(nW)) \)。 5. 实例演示考虑一个有向图：顶点：\( s, a, b, t \)，净需求：\( b_ s = 4, b_ a = 0, b_ b = 0, b_ t = -4 \)。边与参数： \( (s, a) \): 容量 5，费用 2 \( (s, b) \): 容量 3，费用 4 \( (a, b) \): 容量 2，费用 -1 \( (a, t) \): 容量 3，费用 3 \( (b, t) \): 容量 4，费用 1 步骤1 ：初始可行流设为 \( f = 0 \)，满足容量约束但不满足供需。需先找可行流（比如从 s 到 t 送 4 单位）。为简化，假设我们已通过某种方法得到初始流： \( f_ {sa} = 3, f_ {sb} = 1, f_ {ab} = 0, f_ {at} = 3, f_ {bt} = 1 \)。检查平衡：s 流出 4，t 流入 4，中间点平衡，可行。步骤2 ：构造残余网络（略去具体数值），计算边费用。步骤3 ：在残余网络中找最小平均回路。可能找到回路 \( a \to b \to a \)（通过残余边 \( (a,b) \) 和反向边 \( (b,a) \)），其平均费用为 \( (-1 + (-4))/2 = -2.5 \)，为负。步骤4 ：沿此回路推流，例如推 1 单位，更新流： \( f_ {ab} \) 增加 1，\( f_ {sb} \) 减少 1（因为反向边推流相当于减少原流），同时调整相关边以满足平衡。步骤5 ：重新计算残余网络，继续寻找最小平均回路，直到无负回路。最终得到最小费用流： \( f_ {sa} = 4, f_ {sb} = 0, f_ {ab} = 1, f_ {at} = 3, f_ {bt} = 2 \)，总费用 \( 4 \times 2 + 0 \times 4 + 1 \times (-1) + 3 \times 3 + 2 \times 1 = 8 - 1 + 9 + 2 = 18 \)。 6. 算法总结输入：有向图 \( G \)，容量 \( c \)，费用 \( w \)，净需求 \( b \)。输出：最小费用流 \( f \)。步骤：找初始可行流（可借助辅助网络）。构建残余网络 \( G_ f \)。在 \( G_ f \) 中用 Karp 算法找最小平均回路 \( C \)。若 \( \mu(C) \ge 0 \)，停止；否则沿 \( C \) 推送最大可能流量。更新流，返回步骤 2。时间复杂度：\( O(nm^2 \log n \cdot \log(nW)) \)。特点：强多项式时间，不依赖费用值的大小；适合理论分析，实际中可能不如成本缩放算法快，但保证了多项式收敛性。