最小平均权重环问题（Minimum Mean Weight Cycle Problem）
字数 4531 2025-12-17 20:27:09

最小平均权重环问题（Minimum Mean Weight Cycle Problem）

问题描述

给定一个有向图（可能存在负权边，但不能存在权值总和为负的环路，否则最小平均值会趋向负无穷，问题无解），图中每条边都有一个实数的权重（可正、可负、可零）。
我们需要找出图中所有环路中，平均权重最小的那一个环路的平均权重值。
形式化定义：对于一个环路 \(C = (v_0, v_1, \dots, v_{k-1}, v_0)\)，其总权重为

\[w(C) = \sum_{i=0}^{k-1} w(v_i, v_{(i+1) \bmod k}) \]

环的长度（边数）为 \(|C| = k\)，则其平均权重为

\[\mu(C) = \frac{w(C)}{|C|} \]

问题的目标是计算

\[\mu^* = \min_{C \text{ 是环路}} \mu(C) \]

背景与难点

  • 如果图中存在负权环（总权重为负），则平均权重可以为负数，但若存在负权环，其平均权重可能很小，但不会无限制地小，因为这里我们要求是“最小平均权重”，而不是“最小总权重”。
  • 不过，如果存在总权重为负的环，则最小平均权重可能为负数，我们需要找到那个平均值最小的环。
  • 直接枚举所有环路是不可能的，因为环路数量可能指数级增长。
  • 该问题在调度、电路设计、网络流中有应用。

核心思路

1. 转化为判定问题

假设我们猜测一个平均值 \(\mu\)，想判断“是否存在一个环路 \(C\) 使得 \(\mu(C) < \mu\)”。
对图中每条边的权重进行变换：

\[w'(u,v) = w(u,v) - \mu \]

那么

\[w'(C) = w(C) - |C| \mu \]

因此

\[\frac{w(C)}{|C|} < \mu \iff w'(C) < 0 \]

也就是说，原图中平均权重小于 \(\mu\) 的环路 等价于 新图中存在总权重为负的环路。

于是，原问题转化为：
找到最小的 \(\mu\)，使得在权重 \(w - \mu\) 的图中不存在负权环。

2. 利用二分查找

由于平均权重的最小值一定在某个环路上取得，并且这个平均值必然在边的最小权重和最大权重之间，我们可以二分查找 \(\mu\)。

设边权最小值为 \(L\)，最大值为 \(R\)。
二分查找精度达到足够小（比如 \(10^{-8}\)）时停止。

每次猜测 \(\mu = (L+R)/2\)，建新图 \(w' = w - \mu\)，用 Bellman-Ford 算法 判断新图中是否存在负权环：

  • 如果存在负权环，说明原图中有平均权重小于 \(\mu\) 的环，那么 \(\mu\) 太大，调整 \(R = \mu\)
  • 如果不存在负权环，说明原图中所有环的平均权重大于等于 \(\mu\)，那么 \(\mu\) 太小，调整 \(L = \mu\)

复杂度：Bellman-Ford 一次 O(VE)，二分查找 O(log((R-L)/eps))，总复杂度 O(VE log((R-L)/eps))。

3. 更优算法：Karp 的最小平均权重环算法

Karp 在 1978 年提出一个 O(VE) 的精确算法，不需要二分查找。下面详细讲解。

Karp 算法步骤

设图有 n 个顶点（编号 0 到 n-1），m 条边。

定义：
令 \(F_k(v)\) 表示从任意起点（不固定）到顶点 v，经过恰好 k 条边的最短路径长度。
如果从起点到 v 没有恰好 k 条边的路径，则 \(F_k(v) = \infty\)。

初始化：

  • \(F_0(0) = 0\)，且对于 \(v \neq 0\)，\(F_0(v) = \infty\)。
  • 但 Karp 的原始定义是：\(F_0(v) = 0\) 当 \(v = s\)，但为了算法正确，我们需要对所有可能的起点做 n 次？ 不，Karp 算法巧妙之处是：设一个虚拟起点 s，从 s 到所有顶点有一条权重为 0 的边，然后计算从 s 出发的最短路径。但更简单的理解是：

更简单的理解：
我们定义 \(F_k(v)\) 为：从任意结点出发，经过恰好 k 条边到达 v 的最小总权重。
初始化：
\(F_0(v) = 0\) 对所有 v 成立（因为 0 条边，只能从 v 到 v，权重 0）。
然后递推：

\[F_k(v) = \min_{(u,v) \in E} \left[ F_{k-1}(u) + w(u,v) \right] \]

其中 \(k = 1, 2, \dots, n\)。

注意：这里允许重复经过点和边，因为我们要找环，可能路径会重复。

递推计算：
对 k = 1 到 n：
对每个 v，用所有入边 (u,v) 更新：

\[F_k(v) = \min_{(u,v) \in E} \{ F_{k-1}(u) + w(u,v) \} \]

复杂度 O(VE) 可以计算完 \(F_0\) 到 \(F_n\)。

关键定理（Karp 1978）：
最小平均权重 \(\mu^*\) 等于

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

其中 \(F_n(v)\) 必须是有穷的（即存在长度为 n 的路径到 v）。

理解：

  • \(F_n(v)\) 表示从某起点（任意）到 v 的恰好 n 条边的最短路径。
  • 这个路径必然包含环（因为 n 条边至少访问 n+1 个点，但只有 n 个点，必有点重复），可以分解为：一条到某点 u 的长度为 k 的路径 + 一个长度 n-k 的环路（从 u 出发又回到 u 的环）。
  • 那么环的平均权重是 \(\frac{F_n(v) - F_k(u)}{n-k}\)，但 u 是路径上的点，不一定直接是 v，不过在公式中取 min over v 和 max over k 能保证捕获到最小平均权重的环。

算法步骤总结

  1. 输入有向图 G=(V,E) 和边权 w(u,v)，V=n 个点，E=m 条边。
  2. 初始化 \(F[0][v] = 0\) 对 v=0..n-1。
  3. 对 t=1 到 n：
    • 对每个 v，计算
      \(F[t][v] = \min_{(u,v) \in E} (F[t-1][u] + w(u,v))\)
      如果没有任何入边可更新，则 \(F[t][v] = \infty\)。
  4. 如果存在 v 使得 \(F[n][v] = \infty\)，则该 v 不参与最终计算。
  5. 对每个 v，计算

\[ \mu(v) = \max_{0 \le k \le n-1} \frac{F[n][v] - F[k][v]}{n-k} \]

其中分母 n-k 必须大于 0，且 \(F[n][v]\) 和 \(F[k][v]\) 都必须有限。
6. 最终 \(\mu^* = \min_{v \in V} \mu(v)\)。

例子说明

考虑有向图 4 个点，边如下：
0→1: 1
1→2: 1
2→3: 1
3→0: 1
0→2: 4
1→3: 4

这是一个有向图，环 0→1→2→3→0 总权重 4，长度 4，平均 1。
环 0→2→3→0 总权重 1+1+1=3？ 检查：0→2:4, 2→3:1, 3→0:1，总权重 6，长度 3，平均 2。
环 0→1→3→0 总权重 1+4+1=6，长度 3，平均 2。

显然最小平均权重是 1。

我们用 Karp 算法计算：

n=4。

初始化 F[0][v]=0。

t=1:
F[1][0] = min(F[0][3]+w(3,0))=0+1=1
F[1][1] = F[0][0]+1=1
F[1][2] = min(F[0][0]+4=4, F[0][1]+1=1) → 1
F[1][3] = min(F[0][1]+4=4, F[0][2]+1=1) → 1

t=2:
F[2][0] = F[1][3]+1=1+1=2
F[2][1] = F[1][0]+1=1+1=2
F[2][2] = min(F[1][0]+4=5, F[1][1]+1=2) → 2
F[2][3] = min(F[1][1]+4=5, F[1][2]+1=2) → 2

t=3:
F[3][0] = F[2][3]+1=3
F[3][1] = F[2][0]+1=3
F[3][2] = min(F[2][0]+4=6, F[2][1]+1=3) → 3
F[3][3] = min(F[2][1]+4=6, F[2][2]+1=3) → 3

t=4:
F[4][0] = F[3][3]+1=4
F[4][1] = F[3][0]+1=4
F[4][2] = min(F[3][0]+4=7, F[3][1]+1=4) → 4
F[4][3] = min(F[3][1]+4=7, F[3][2]+1=4) → 4

现在计算 μ(v) = max_{k=0..3} (F[4][v]-F[k][v])/(4-k)

v=0:
k=0: (4-0)/4=1
k=1: (4-1)/3=1
k=2: (4-2)/2=1
k=3: (4-3)/1=1
μ(0)=1

v=1: 类似全 1。
v=2: 类似全 1。
v=3: 类似全 1。

所以 μ*=1，符合预期。

复杂度

  • 计算 F[t][v] 需要 O(n * m) 时间。
  • 第二步对每个 v 比较 n 个比值，O(n²)。
  • 总复杂度 O(nm)，适合稠密图也很好。

算法正确性理解

直观理解：F[n][v] 表示从某起点到 v 的 n 条边的最短路径，因为 n 条边至少访问 n+1 个顶点，必有环。这个环可以被“分离”出来，而剩下的是一条路径。通过枚举最后一个顶点 v 和环开始前的步数 k，我们考虑环的长度 n-k，其平均权重是 (F[n][v] - F[k][v])/(n-k)。取 max 再取 min 是为了应对可能的最坏分解，从而得到真正的最小平均权重。

应用场景

  • 检测图中是否有负平均权重环（比如在某些调度问题中表示不可行）。
  • 在离散事件系统中用于计算最大周期平均值。
  • 是求解最小平均权重环的标准算法。

总结

最小平均权重环问题可以通过 Karp 的 O(VE) 动态规划算法高效求解，避免了二分查找的精度问题和额外对数因子。算法思想是计算从任意起点到每个点恰好 k 条边的最短路径，然后通过公式直接得出最小平均值。

最小平均权重环问题（Minimum Mean Weight Cycle Problem） 问题描述 给定一个 有向图 （可能存在负权边，但不能存在权值总和为负的环路，否则最小平均值会趋向负无穷，问题无解），图中每条边都有一个实数的权重（可正、可负、可零）。 我们需要找出图中所有环路中， 平均权重最小 的那一个环路的平均权重值。 形式化定义：对于一个环路 \(C = (v_ 0, v_ 1, \dots, v_ {k-1}, v_ 0)\)，其总权重为 \[ w(C) = \sum_ {i=0}^{k-1} w(v_ i, v_ {(i+1) \bmod k}) \] 环的长度（边数）为 \(|C| = k\)，则其平均权重为 \[ \mu(C) = \frac{w(C)}{|C|} \] 问题的目标是计算 \[ \mu^* = \min_ {C \text{ 是环路}} \mu(C) \] 背景与难点 如果图中存在负权环（总权重为负），则平均权重可以为负数，但若存在 负权环 ，其平均权重可能很小，但不会无限制地小，因为这里我们要求是“最小平均权重”，而不是“最小总权重”。 不过，如果存在 总权重为负的环 ，则最小平均权重可能为负数，我们需要找到那个平均值最小的环。 直接枚举所有环路是不可能的，因为环路数量可能指数级增长。 该问题在调度、电路设计、网络流中有应用。 核心思路 1. 转化为判定问题 假设我们猜测一个平均值 \(\mu\)，想判断“是否存在一个环路 \(C\) 使得 \(\mu(C) < \mu\)”。 对图中每条边的权重进行变换： \[ w'(u,v) = w(u,v) - \mu \] 那么 \[ w'(C) = w(C) - |C| \mu \] 因此 \[ \frac{w(C)}{|C|} < \mu \iff w'(C) < 0 \] 也就是说， 原图中平均权重小于 \(\mu\) 的环路 等价于 新图中存在总权重为负的环路 。 于是，原问题转化为： 找到最小的 \(\mu\)，使得在权重 \(w - \mu\) 的图中 不存在负权环 。 2. 利用二分查找 由于平均权重的最小值一定在某个环路上取得，并且这个平均值必然在边的最小权重和最大权重之间，我们可以二分查找 \(\mu\)。 设边权最小值为 \(L\)，最大值为 \(R\)。 二分查找精度达到足够小（比如 \(10^{-8}\)）时停止。 每次猜测 \(\mu = (L+R)/2\)，建新图 \(w' = w - \mu\)，用 Bellman-Ford 算法 判断新图中是否存在负权环： 如果存在负权环，说明原图中有平均权重小于 \(\mu\) 的环，那么 \(\mu\) 太大，调整 \(R = \mu\) 如果不存在负权环，说明原图中所有环的平均权重大于等于 \(\mu\)，那么 \(\mu\) 太小，调整 \(L = \mu\) 复杂度 ：Bellman-Ford 一次 O(VE)，二分查找 O(log((R-L)/eps))，总复杂度 O(VE log((R-L)/eps))。 3. 更优算法：Karp 的最小平均权重环算法 Karp 在 1978 年提出一个 O(VE) 的精确算法，不需要二分查找。下面详细讲解。 Karp 算法步骤 设图有 n 个顶点（编号 0 到 n-1），m 条边。 定义 ： 令 \(F_ k(v)\) 表示从任意起点（不固定）到顶点 v，经过恰好 k 条边的最短路径长度。 如果从起点到 v 没有恰好 k 条边的路径，则 \(F_ k(v) = \infty\)。 初始化 ： \(F_ 0(0) = 0\)，且对于 \(v \neq 0\)，\(F_ 0(v) = \infty\)。 但 Karp 的原始定义是：\(F_ 0(v) = 0\) 当 \(v = s\)，但为了算法正确，我们需要对所有可能的起点做 n 次？ 不，Karp 算法巧妙之处是：设一个虚拟起点 s，从 s 到所有顶点有一条权重为 0 的边，然后计算从 s 出发的最短路径。但更简单的理解是： 更简单的理解 ： 我们定义 \(F_ k(v)\) 为： 从任意结点出发，经过恰好 k 条边到达 v 的最小总权重 。 初始化： \(F_ 0(v) = 0\) 对所有 v 成立（因为 0 条边，只能从 v 到 v，权重 0）。 然后递推： \[ F_ k(v) = \min_ {(u,v) \in E} \left[ F_ {k-1}(u) + w(u,v) \right ] \] 其中 \(k = 1, 2, \dots, n\)。 注意：这里允许重复经过点和边，因为我们要找环，可能路径会重复。 递推计算 ： 对 k = 1 到 n： 对每个 v，用所有入边 (u,v) 更新： \[ F_ k(v) = \min_ {(u,v) \in E} \{ F_ {k-1}(u) + w(u,v) \} \] 复杂度 O(VE) 可以计算完 \(F_ 0\) 到 \(F_ n\)。 关键定理 （Karp 1978）： 最小平均权重 \(\mu^ \) 等于 \[ \mu^ = \min_ {v \in V} \max_ {0 \le k \le n-1} \frac{F_ n(v) - F_ k(v)}{n - k} \] 其中 \(F_ n(v)\) 必须是有穷的（即存在长度为 n 的路径到 v）。 理解 ： \(F_ n(v)\) 表示从某起点（任意）到 v 的恰好 n 条边的最短路径。 这个路径必然包含环（因为 n 条边至少访问 n+1 个点，但只有 n 个点，必有点重复），可以分解为：一条到某点 u 的长度为 k 的路径 + 一个长度 n-k 的环路（从 u 出发又回到 u 的环）。 那么环的平均权重是 \(\frac{F_ n(v) - F_ k(u)}{n-k}\)，但 u 是路径上的点，不一定直接是 v，不过在公式中取 min over v 和 max over k 能保证捕获到最小平均权重的环。 算法步骤总结 输入有向图 G=(V,E) 和边权 w(u,v)，V=n 个点，E=m 条边。 初始化 \(F[ 0][ v ] = 0\) 对 v=0..n-1。 对 t=1 到 n： 对每个 v，计算 \(F[ t][ v] = \min_ {(u,v) \in E} (F[ t-1][ u ] + w(u,v))\) 如果没有任何入边可更新，则 \(F[ t][ v ] = \infty\)。 如果存在 v 使得 \(F[ n][ v ] = \infty\)，则该 v 不参与最终计算。 对每个 v，计算 \[ \mu(v) = \max_ {0 \le k \le n-1} \frac{F[ n][ v] - F[ k][ v ]}{n-k} \] 其中分母 n-k 必须大于 0，且 \(F[ n][ v]\) 和 \(F[ k][ v ]\) 都必须有限。 最终 \(\mu^* = \min_ {v \in V} \mu(v)\)。 例子说明 考虑有向图 4 个点，边如下： 0→1: 1 1→2: 1 2→3: 1 3→0: 1 0→2: 4 1→3: 4 这是一个有向图，环 0→1→2→3→0 总权重 4，长度 4，平均 1。 环 0→2→3→0 总权重 1+1+1=3？ 检查：0→2:4, 2→3:1, 3→0:1，总权重 6，长度 3，平均 2。 环 0→1→3→0 总权重 1+4+1=6，长度 3，平均 2。 显然最小平均权重是 1。 我们用 Karp 算法计算： n=4。 初始化 F[ 0][ v ]=0。 t=1: F[ 1][ 0] = min(F[ 0][ 3 ]+w(3,0))=0+1=1 F[ 1][ 1] = F[ 0][ 0 ]+1=1 F[ 1][ 2] = min(F[ 0][ 0]+4=4, F[ 0][ 1 ]+1=1) → 1 F[ 1][ 3] = min(F[ 0][ 1]+4=4, F[ 0][ 2 ]+1=1) → 1 t=2: F[ 2][ 0] = F[ 1][ 3 ]+1=1+1=2 F[ 2][ 1] = F[ 1][ 0 ]+1=1+1=2 F[ 2][ 2] = min(F[ 1][ 0]+4=5, F[ 1][ 1 ]+1=2) → 2 F[ 2][ 3] = min(F[ 1][ 1]+4=5, F[ 1][ 2 ]+1=2) → 2 t=3: F[ 3][ 0] = F[ 2][ 3 ]+1=3 F[ 3][ 1] = F[ 2][ 0 ]+1=3 F[ 3][ 2] = min(F[ 2][ 0]+4=6, F[ 2][ 1 ]+1=3) → 3 F[ 3][ 3] = min(F[ 2][ 1]+4=6, F[ 2][ 2 ]+1=3) → 3 t=4: F[ 4][ 0] = F[ 3][ 3 ]+1=4 F[ 4][ 1] = F[ 3][ 0 ]+1=4 F[ 4][ 2] = min(F[ 3][ 0]+4=7, F[ 3][ 1 ]+1=4) → 4 F[ 4][ 3] = min(F[ 3][ 1]+4=7, F[ 3][ 2 ]+1=4) → 4 现在计算 μ(v) = max_ {k=0..3} (F[ 4][ v]-F[ k][ v ])/(4-k) v=0: k=0: (4-0)/4=1 k=1: (4-1)/3=1 k=2: (4-2)/2=1 k=3: (4-3)/1=1 μ(0)=1 v=1: 类似全 1。 v=2: 类似全 1。 v=3: 类似全 1。 所以 μ* =1，符合预期。 复杂度 计算 F[ t][ v] 需要 O(n * m) 时间。 第二步对每个 v 比较 n 个比值，O(n²)。 总复杂度 O(nm)，适合稠密图也很好。 算法正确性理解 直观理解：F[ n][ v] 表示从某起点到 v 的 n 条边的最短路径，因为 n 条边至少访问 n+1 个顶点，必有环。这个环可以被“分离”出来，而剩下的是一条路径。通过枚举最后一个顶点 v 和环开始前的步数 k，我们考虑环的长度 n-k，其平均权重是 (F[ n][ v] - F[ k][ v ])/(n-k)。取 max 再取 min 是为了应对可能的最坏分解，从而得到真正的最小平均权重。 应用场景 检测图中是否有负平均权重环（比如在某些调度问题中表示不可行）。 在离散事件系统中用于计算最大周期平均值。 是求解最小平均权重环的标准算法。 总结 最小平均权重环问题可以通过 Karp 的 O(VE) 动态规划算法高效求解，避免了二分查找的精度问题和额外对数因子。算法思想是计算从任意起点到每个点恰好 k 条边的最短路径，然后通过公式直接得出最小平均值。