最小平均权重环问题（Minimum Mean Weight Cycle Problem）
字数 3232 2025-12-18 06:25:27

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

问题描述

给定一个有向带权图（允许权重为负值，且允许环的存在），我们要求找到图中所有环的“平均权重”的最小值。
具体来说，对于一个环 \(C\)，其平均权重定义为环上所有边的权重之和除以环的边数（即环的长度）。
我们要计算：

\[\lambda^* = \min_{\text{所有环 } C} \frac{\sum_{e \in C} w(e)}{|C|} \]

其中 \(w(e)\) 是边 \(e\) 的权重，\(|C|\) 是环 \(C\) 包含的边数。

这个问题在调度理论、性能分析、检测系统中有应用，比如判断一个系统中是否存在“平均收益”为负的循环过程。

解题思路

如果直接枚举所有环，计算量太大（环的数量可能是指数级的）。我们可以将其转化为一个二分答案 + 判定负环的问题。

核心观察：
假设我们猜测一个值 \(\lambda\)，考虑将图中每条边的权重减去 \(\lambda\)，得到新图 \(G'\)：

\[w'(e) = w(e) - \lambda \]

那么原图中某个环 \(C\) 的平均权重满足：

\[\frac{\sum_{e \in C} w(e)}{|C|} \leq \lambda \quad \Longleftrightarrow \quad \sum_{e \in C} (w(e) - \lambda) \leq 0 \]

即：原图中存在平均权重不超过 \(\lambda\) 的环 ⇔ 新图中存在非正权重的环。

更进一步，因为我们可以对不等式两边同时乘以 \(|C|\)，所以：

  • 如果新图中存在负环（即总权重 < 0 的环），那么原图存在平均权重 < λ 的环。
  • 如果新图中存在零环（总权重 = 0），那么原图存在平均权重 = λ 的环。
  • 如果新图中所有环的权重都 > 0，那么原图所有环的平均权重 > λ。

因此，我们可以二分搜索 λ，每次判断新图中是否存在非正环（即总权重 ≤ 0 的环）。
但是“非正环”不容易直接检测，常见的做法是：判断是否存在负环（<0 的环）。因为如果存在零环，那么在数值处理上可以近似为“非常接近 0 的负环”，我们通过二分精度控制即可。

算法步骤

步骤 1：确定二分搜索范围

假设图中所有边的权重在 \([L, R]\) 之间，那么平均权重的最小值也在 \([L, R]\) 之间。
我们可以取初始下界 \(lo = L\)，上界 \(hi = R\)。
更简单且安全的做法：

  • 下界 \(lo = \min_{e} w(e)\)
  • 上界 \(hi = \max_{e} w(e)\)

因为最小平均权重不可能小于最小边权（环至少有一条边），也不可能大于最大边权。

步骤 2：二分搜索框架

我们设定一个精度 \(\epsilon\)（例如 \(10^{-6}\) 或 \(10^{-8}\)）。
当 \(hi - lo > \epsilon\) 时重复：

  1. 令 \(mid = (lo + hi) / 2\)。
  2. 构造新图：每条边的权重变为 \(w'(e) = w(e) - mid\)。
  3. 判断新图中是否存在负环。
    • 如果存在负环，说明原图存在平均权重 < \(mid\) 的环，则令 \(hi = mid\)。
    • 如果不存在负环，说明原图所有环的平均权重 ≥ \(mid\)，则令 \(lo = mid\)。

二分结束后，\(lo\)（或 \(hi\)）就是最小平均权重 \(\lambda^*\) 的近似值。

步骤 3：判断负环的方法

常用 Bellman-Ford 算法的变种（SPFA 也可用，但要注意效率与稳定性）。
对于新图 \(G'\)：

  1. 设图中顶点数为 \(n\)。
  2. 初始化所有顶点的距离 \(dist[v] = 0\)（关键！）。
    • 为什么从 0 开始？因为我们不关心从某个起点出发的最短路，而是关心整个图中是否存在负环。
      将每个顶点初始距离设为 0，相当于添加了一个“超级源点”到所有顶点有一条权重为 0 的边，这样可以保证算法能检测到整个图中的负环，即使图不连通。
  3. 运行 Bellman-Ford 算法（或队列优化的 SPFA），执行 \(n\) 轮松弛。
  4. 如果在第 \(n\) 轮后还能进行松弛，说明存在负环。

注意：如果使用标准的 Bellman-Ford 从单个源点检测负环，对于不连通图可能漏掉负环。因此我们采用所有顶点初始距离为 0 的方法，相当于从每个顶点同时开始跑最短路，确保能检测到任意连通分量中的负环。

举例说明

假设有向图如下（3 个顶点，4 条边）：

边: 0→1 权重 1
     1→2 权重 2
     2→0 权重 4
     2→1 权重 3

寻找最小平均权重环。

步骤：

  1. 边权范围 [1, 4]，设 \(lo=1, hi=4, \epsilon=0.001\)。
  2. 第一轮 \(mid = 2.5\)：
    新边权：
    0→1: 1-2.5 = -1.5
    1→2: 2-2.5 = -0.5
    2→0: 4-2.5 = 1.5
    2→1: 3-2.5 = 0.5
    检查负环：
    从所有 dist=0 开始跑 Bellman-Ford：
    发现环 0→1→2→0 的总权重 = -1.5 + (-0.5) + 1.5 = -0.5 < 0，存在负环。
    因此 \(hi = 2.5\)。
  3. 第二轮 \(mid = (1+2.5)/2 = 1.75\)：
    新边权：
    0→1: -0.75
    1→2: 0.25
    2→0: 2.25
    2→1: 1.25
    检查：环 0→1→2→0 总权重 = -0.75 + 0.25 + 2.25 = 1.75 > 0，无负环。
    因此 \(lo = 1.75\)。
  4. 继续二分，最终收敛到大约 2.0。
    验证：环 0→1→2→0 的平均权重 = (1+2+4)/3 = 7/3 ≈ 2.333...
    环 1→2→1 的平均权重 = (2+3)/2 = 2.5
    环 0→1→2→1→2→0 ... 可能更长，但平均权重不会更小。
    实际上，最小平均权重环是 0→1→2→0，平均权重 7/3 ≈ 2.333。
    二分过程中可能检测到其他组合的负环，但最终会收敛到最小值。

算法复杂度

  • 二分搜索次数：\(O(\log((R-L)/\epsilon))\)，通常几十次。
  • 每次 Bellman-Ford 判断负环：\(O(n \cdot m)\)（n 点数，m 边数）。
    总复杂度 \(O(nm \log(\frac{R-L}{\epsilon}))\)，在一般图中可行。

优化与变种

  1. Karp 算法（1978 年提出）：
    有 \(O(nm)\) 的直接算法，无需二分。
    定义 \(F_k(v)\) = 从任意起点到 v 恰好经过 k 条边的最短路径长度（允许重复顶点和边）。
    则最小平均权重 \(\lambda^* = \min_{v} \max_{0 \le k \le n-1} \frac{F_n(v) - F_k(v)}{n-k}\)。
    该算法需计算所有 \(F_k(v)\)，实现稍复杂，但理论复杂度更优。
  2. 精度控制：二分搜索中 ε 越小精度越高，但迭代次数增加。

关键点总结

  1. 问题转化：减去猜测值 λ，将平均权重比较转化为环的总权重正负判断。
  2. 负环检测：从所有顶点初始距离 0 开始跑 Bellman-Ford，可检测全图负环。
  3. 二分搜索：不断缩小 λ 的范围，直到精度满足。

这样，我们就得到了最小平均权重环的近似值，并可进一步通过记录路径还原出该环。

最小平均权重环问题（Minimum Mean Weight Cycle Problem） 问题描述 给定一个 有向带权图 （允许权重为负值，且允许环的存在），我们要求找到图中所有环的“平均权重”的最小值。 具体来说，对于一个环 \( C \)，其平均权重定义为环上所有边的权重之和除以环的边数（即环的长度）。 我们要计算： \[ \lambda^* = \min_ {\text{所有环 } C} \frac{\sum_ {e \in C} w(e)}{|C|} \] 其中 \( w(e) \) 是边 \( e \) 的权重，\( |C| \) 是环 \( C \) 包含的边数。 这个问题在调度理论、性能分析、检测系统中有应用，比如判断一个系统中是否存在“平均收益”为负的循环过程。 解题思路 如果直接枚举所有环，计算量太大（环的数量可能是指数级的）。我们可以将其转化为一个 二分答案 + 判定负环 的问题。 核心观察 ： 假设我们猜测一个值 \( \lambda \)，考虑将图中每条边的权重减去 \( \lambda \)，得到新图 \( G' \)： \[ w'(e) = w(e) - \lambda \] 那么原图中某个环 \( C \) 的平均权重满足： \[ \frac{\sum_ {e \in C} w(e)}{|C|} \leq \lambda \quad \Longleftrightarrow \quad \sum_ {e \in C} (w(e) - \lambda) \leq 0 \] 即： 原图中存在平均权重不超过 \( \lambda \) 的环 ⇔ 新图中存在非正权重的环 。 更进一步，因为我们可以对不等式两边同时乘以 \( |C| \)，所以： 如果新图中存在 负环 （即总权重 < 0 的环），那么原图存在平均权重 < λ 的环。 如果新图中存在 零环 （总权重 = 0），那么原图存在平均权重 = λ 的环。 如果新图中所有环的权重都 > 0，那么原图所有环的平均权重 > λ。 因此，我们可以 二分搜索 λ，每次判断新图中是否存在 非正环 （即总权重 ≤ 0 的环）。 但是“非正环”不容易直接检测，常见的做法是：判断是否存在负环（ <0 的环）。因为如果存在零环，那么在数值处理上可以近似为“非常接近 0 的负环”，我们通过二分精度控制即可。 算法步骤 步骤 1：确定二分搜索范围 假设图中所有边的权重在 \([ L, R]\) 之间，那么平均权重的最小值也在 \([ L, R ]\) 之间。 我们可以取初始下界 \( lo = L \)，上界 \( hi = R \)。 更简单且安全的做法： 下界 \( lo = \min_ {e} w(e) \) 上界 \( hi = \max_ {e} w(e) \) 因为最小平均权重不可能小于最小边权（环至少有一条边），也不可能大于最大边权。 步骤 2：二分搜索框架 我们设定一个精度 \( \epsilon \)（例如 \( 10^{-6} \) 或 \( 10^{-8} \)）。 当 \( hi - lo > \epsilon \) 时重复： 令 \( mid = (lo + hi) / 2 \)。 构造新图：每条边的权重变为 \( w'(e) = w(e) - mid \)。 判断新图中是否存在 负环 。 如果存在负环，说明原图存在平均权重 < \( mid \) 的环，则令 \( hi = mid \)。 如果不存在负环，说明原图所有环的平均权重 ≥ \( mid \)，则令 \( lo = mid \)。 二分结束后，\( lo \)（或 \( hi \)）就是最小平均权重 \( \lambda^* \) 的近似值。 步骤 3：判断负环的方法 常用 Bellman-Ford 算法 的变种（SPFA 也可用，但要注意效率与稳定性）。 对于新图 \( G' \)： 设图中顶点数为 \( n \)。 初始化所有顶点的距离 \( dist[ v] = 0 \)（ 关键！ ）。 为什么从 0 开始？因为我们不关心从某个起点出发的最短路，而是关心整个图中是否存在负环。 将每个顶点初始距离设为 0，相当于添加了一个“超级源点”到所有顶点有一条权重为 0 的边，这样可以保证算法能检测到整个图中的负环，即使图不连通。 运行 Bellman-Ford 算法（或队列优化的 SPFA），执行 \( n \) 轮松弛。 如果在第 \( n \) 轮后还能进行松弛，说明存在负环。 注意 ：如果使用标准的 Bellman-Ford 从单个源点检测负环，对于不连通图可能漏掉负环。因此我们采用 所有顶点初始距离为 0 的方法，相当于从每个顶点同时开始跑最短路，确保能检测到任意连通分量中的负环。 举例说明 假设有向图如下（3 个顶点，4 条边）： 寻找最小平均权重环。 步骤 ： 边权范围 [ 1, 4 ]，设 \( lo=1, hi=4, \epsilon=0.001 \)。 第一轮 \( mid = 2.5 \)： 新边权： 0→1: 1-2.5 = -1.5 1→2: 2-2.5 = -0.5 2→0: 4-2.5 = 1.5 2→1: 3-2.5 = 0.5 检查负环： 从所有 dist=0 开始跑 Bellman-Ford： 发现环 0→1→2→0 的总权重 = -1.5 + (-0.5) + 1.5 = -0.5 < 0，存在负环。 因此 \( hi = 2.5 \)。 第二轮 \( mid = (1+2.5)/2 = 1.75 \)： 新边权： 0→1: -0.75 1→2: 0.25 2→0: 2.25 2→1: 1.25 检查：环 0→1→2→0 总权重 = -0.75 + 0.25 + 2.25 = 1.75 > 0，无负环。 因此 \( lo = 1.75 \)。 继续二分，最终收敛到大约 2.0。 验证：环 0→1→2→0 的平均权重 = (1+2+4)/3 = 7/3 ≈ 2.333... 环 1→2→1 的平均权重 = (2+3)/2 = 2.5 环 0→1→2→1→2→0 ... 可能更长，但平均权重不会更小。 实际上，最小平均权重环是 0→1→2→0，平均权重 7/3 ≈ 2.333。 二分过程中可能检测到其他组合的负环，但最终会收敛到最小值。 算法复杂度 二分搜索次数：\( O(\log((R-L)/\epsilon)) \)，通常几十次。 每次 Bellman-Ford 判断负环：\( O(n \cdot m) \)（n 点数，m 边数）。 总复杂度 \( O(nm \log(\frac{R-L}{\epsilon})) \)，在一般图中可行。 优化与变种 Karp 算法 （1978 年提出）： 有 \( O(nm) \) 的直接算法，无需二分。 定义 \( F_ k(v) \) = 从任意起点到 v 恰好经过 k 条边的最短路径长度（允许重复顶点和边）。 则最小平均权重 \( \lambda^* = \min_ {v} \max_ {0 \le k \le n-1} \frac{F_ n(v) - F_ k(v)}{n-k} \)。 该算法需计算所有 \( F_ k(v) \)，实现稍复杂，但理论复杂度更优。 精度控制 ：二分搜索中 ε 越小精度越高，但迭代次数增加。 关键点总结 问题转化：减去猜测值 λ，将平均权重比较转化为环的总权重正负判断。 负环检测：从所有顶点初始距离 0 开始跑 Bellman-Ford，可检测全图负环。 二分搜索：不断缩小 λ 的范围，直到精度满足。 这样，我们就得到了最小平均权重环的近似值，并可进一步通过记录路径还原出该环。