Joh*_*yen 6 c++ graph-theory cycle backtracking pruning
在有向图中,我们正在寻找具有最低平均边权重的周期.例如,具有节点1和2的图表具有从长度2的1到2和长度4的2到1的路径将具有3的最小平均周期.
不是寻找复杂的方法(Karp),而是通过修剪解决方案进行简单的回溯.当当前运行平均值大于最佳找到的平均重量循环成本时,给出了解释为"具有重要修剪回溯的可解决方案".
但是,为什么这种方法有效呢？如果我们在一个周期的中途并且重量超过最佳找到的平均值,那么在重量较小的边缘我们是否可能达到我们当前周期可能低于最佳平均值的情况？
编辑:以下是一个示例问题:http://uva.onlinejudge.org/index.php？option = onlinejudge&page = show_problem & problem = 2031
小智 2
令给定图的最优解为平均边权重为 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。
至于你的问题：
如果我们处于一个周期的中间，并且权重大于找到的最佳平均值，那么在权重边缘较小的情况下，我们是否有可能达到当前周期低于找到的最佳平均值的情况？
当然如此。但我们可以安全地修剪这个解决方案，因为稍后我们会发现从另一条边开始的相同循环，该循环不会被修剪。我的证明表明，如果我们考虑图中每个可能的循环，迟早我们会找到最佳循环。