最小平均重量周期——直观解释
Minimum Mean Weight Cycle - Intuitive Explanation
在有向图中，我们正在寻找具有最低平均边权重的循环。例如，具有节点 1 和 2 且路径从 1 到 2 的长度为 2 和从 2 到 1 的长度为 4 的图的最小平均周期为 3。
不是寻找复杂的方法（Karp），而是寻找带有修剪解决方案的简单回溯。解释为"Solvable with backtracking with important pruning when current running mean is greater than the best found mean weight cycle cost."
但是，为什么这个方法有效呢？如果我们在一个循环的中途并且权重大于找到的最佳均值，是否有可能在权重边缘较小的情况下我们可以达到当前循环可能低于找到的最佳均值的情况？
编辑：这是一个示例问题：http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2031
让给定图的最优解是一个具有平均边权重 X 的循环。
存在一些具有边 e_1、e_2 ... e_n 的最优循环，使得 avg(e_i) = X.
为了我的证明，我假设所有索引对 n 取模，所以 e_(n + 1) 是 e_1。
假设我们的启发式算法找不到这个解决方案，这意味着：对于每个 i（无论我们先取什么边）都存在这样的 j（我们跟随 [=16 的所有边=] 到 j 为止）序列 e_i ... e_j 中的平均边权重大于 X（启发式修剪此解决方案）。
然后我们可以证明平均边权重不能等于 X。让我们取一个最长的连续子序列，它没有被启发式修剪（每个元素的平均边权重不大于 X）。至少有一个e_i <= X，所以存在这样的子序列。对于此类子序列的第一个元素 e_k，存在 p 使得 avg(e_k ... e_p) > X。我们先拿这样的p。现在让我们拿 k' = p + 1 和另一个 p'。我们将重复此过程，直到我们再次达到初始 k。 final p 可能不会超过 initial k，这意味着 final 子序列包含 initial [e_k, e_p - 1]，这与我们对 e_k 的构造相矛盾。现在我们的序列 e_1 ... e_n 完全被非重叠子序列 e_k ... e_p、e_k'...e_p' 等覆盖，每个子序列的平均边权重都大于 X。所以我们有矛盾 avg(e_i) = X.
关于你的问题：
If we are halfway through a cycle and the weight is more than the best
found mean, isn't it possible that with small weight edges we can
reach a situation where our current cycle can go lower than the best
found mean?
当然是。但是我们可以安全地修剪这个解决方案，因为稍后我们会发现从另一条边开始的相同循环不会被修剪。我的证明表明，如果我们考虑图中每个可能的循环，我们迟早会找到一个最佳循环。
在有向图中，我们正在寻找具有最低平均边权重的循环。例如，具有节点 1 和 2 且路径从 1 到 2 的长度为 2 和从 2 到 1 的长度为 4 的图的最小平均周期为 3。
不是寻找复杂的方法（Karp），而是寻找带有修剪解决方案的简单回溯。解释为"Solvable with backtracking with important pruning when current running mean is greater than the best found mean weight cycle cost."
但是，为什么这个方法有效呢？如果我们在一个循环的中途并且权重大于找到的最佳均值，是否有可能在权重边缘较小的情况下我们可以达到当前循环可能低于找到的最佳均值的情况？
编辑：这是一个示例问题：http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2031
让给定图的最优解是一个具有平均边权重 X 的循环。
存在一些具有边 e_1、e_2 ... e_n 的最优循环，使得 avg(e_i) = X.
为了我的证明，我假设所有索引对 n 取模，所以 e_(n + 1) 是 e_1。
假设我们的启发式算法找不到这个解决方案，这意味着：对于每个 i（无论我们先取什么边）都存在这样的 j（我们跟随 [=16 的所有边=] 到 j 为止）序列 e_i ... e_j 中的平均边权重大于 X（启发式修剪此解决方案）。
然后我们可以证明平均边权重不能等于 X。让我们取一个最长的连续子序列，它没有被启发式修剪（每个元素的平均边权重不大于 X）。至少有一个e_i <= X，所以存在这样的子序列。对于此类子序列的第一个元素 e_k，存在 p 使得 avg(e_k ... e_p) > X。我们先拿这样的p。现在让我们拿 k' = p + 1 和另一个 p'。我们将重复此过程，直到我们再次达到初始 k。 final p 可能不会超过 initial k，这意味着 final 子序列包含 initial [e_k, e_p - 1]，这与我们对 e_k 的构造相矛盾。现在我们的序列 e_1 ... e_n 完全被非重叠子序列 e_k ... e_p、e_k'...e_p' 等覆盖，每个子序列的平均边权重都大于 X。所以我们有矛盾 avg(e_i) = X.
关于你的问题：
If we are halfway through a cycle and the weight is more than the best found mean, isn't it possible that with small weight edges we can reach a situation where our current cycle can go lower than the best found mean?
当然是。但是我们可以安全地修剪这个解决方案，因为稍后我们会发现从另一条边开始的相同循环不会被修剪。我的证明表明，如果我们考虑图中每个可能的循环，我们迟早会找到一个最佳循环。