在有向图中，我们正在寻找具有最低平均边权重的循环。例如，具有节点 1 和 2 的图具有从 1 到 2 的长度为 2 和从 2 到 1 的长度为 4 的路径的最小平均循环为 3。
不是在寻找一个复杂的方法（Karp），而是一个简单的回溯与修剪解决方案。给出的解释是“当当前运行平均值大于最佳找到的平均重量循环成本时，可通过重要修剪进行回溯求解”。
但是，为什么这种方法有效？如果我们在一个周期的中途并且权重超过了找到的最佳均值，那么是否有可能通过小的权重边缘我们可以达到我们当前周期可能低于最佳找到的均值的情况？
编辑：这是一个示例问题：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的（我们跟踪从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值。finalp可能不会超过 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。
至于你的问题：
如果我们在一个周期的中途并且权重超过了找到的最佳均值，那么是否有可能通过小的权重边缘我们可以达到我们当前周期可能低于最佳找到的均值的情况？
当然是。但是我们可以安全地修剪这个解决方案，因为稍后我们会发现从另一条边开始的同一个循环不会被修剪。我的证明表明，如果我们考虑图中每个可能的循环，迟早我们会找到一个最佳循环。