c++ - 最小平均重量周期——直观解释

Question

在有向图中，我们正在寻找具有最低平均边权重的循环。例如，具有节点 1 和 2 且路径从 1 到 2 长度为 2 和从 2 到 1 长度为 4 的图的最小平均周期为 3。

不是寻找复杂的方法(Karp)，而是寻找带有修剪解决方案的简单回溯。给出的解释是“当当前运行平均值大于找到的最佳平均权重循环成本时，可通过回溯和重要修剪解决。”

但是，为什么这个方法有效呢？如果我们在一个周期的中途并且权重大于找到的最佳均值，那么在权重边较小的情况下，我们是否有可能达到当前周期可能低于找到的最佳均值的情况？

编辑:这是一个示例问题:http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2031

Answer 1

让给定图的最优解是一个具有平均边权重 X 的循环。

存在一些带边的最优循环 e_1 , e_2 ... e_n , 这样 avg(e_i) = X .

为了证明，我假设所有索引对 n 取模，所以 e_(n + 1)是e_1 .

假设我们的启发式算法找不到这个解决方案，这意味着:对于每个 i (无论我们先采取什么优势)存在这样的 j (到目前为止，我们跟踪了从 i 到 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。再次。决赛 p可能不会超过初始 k ，这意味着最终子序列包含初始 [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?

当然可以。但是我们可以安全地修剪这个解决方案，因为稍后我们会发现从另一条边开始的相同循环不会被修剪。我的证明表明，如果我们考虑图中每个可能的循环，我们迟早会找到一个最佳循环。