Minimum Mean Weight Cycle - Intuitive Explanation
backtracking, c++, cycle, graph-theory, pruning
Solution
Lets optimal solution for given graph be a cycle with avg edge weight X.
There is some optimal cycle with edges `e_1`, `e_2` ... `e_n`, such that `avg(e_i) = X`.
For my proof, I assume all indexes modulo n, so `e_(n + 1)` is `e_1`.
Lets say that our heuristic can't find this solution, that means: for each `i` (whatever edge we took first) exists such `j` (we followed all edges from `i` to `j` so far) that average edge weight in the sequence `e_i` ... `e_j` is greater than X (heuristic prunes this solution).
Then we can show that average edge weight cannot be equal to X. Lets take a longest contiguos subsequence that is not pruned by heuristic (having average edge weight not greater than X for every element). At least one `e_i <= X`, so such subsequence exists. For the first element `e_k` of such subsequence, there is `p` such that `avg(e_k ... e_p) > X`. We take first such `p`. Now lets take `k' = p + 1` and get another `p'`. We will repeat this process until we hit our initial `k` again. Final `p` may not outrun initial `k`, this mean that final subsequence contains initial `[e_k, e_p - 1]`, which contradicts with our construction for `e_k`. Now our sequence `e_1` ... `e_n` is completely covered by non-overlapping subsequences `e_k ... e_p`, `e_k'...e_p'` etc, each of those has average edge weight greater than X. So we have a contradiction that `avg(e_i) = X`.
As for your question:
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?
Of course it is. But we can safely prune this solution, as later we will discover the same cycle starting from another edge, which will not be pruned. My proof states that if we consider every possible cycle in the graph, sooner or later we will find an optimal cycle.
Problem
In a directed graph, we are looking for the cycle that had the lowest average edge weights. For instance, a graph with nodes 1 and 2 with path from 1 to 2 of length 2 and from 2 to 1 of length 4 would have minimum mean cycle of 3. Not looking for a complicated method(Karp), but a simple backtracking wtih pruning solution. An explanation is given as "Solvable with backtracking with important pruning when current running mean is greater than the best found mean weight cycle cost." However, why does this method work? 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? Edit: Here is a sample problem: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2031