Цикл минимального среднего веса - интуитивное пояснение

Question

В ориентированном графике мы ищем цикл с наименьшими средними весами. Например, график с узлами 1 и 2 с траекторией от 1 до 2 длины 2 и от 2 до 1 длины 4 будет иметь минимальный средний цикл 3.

Не ищите сложный метод (Карп), но простой откат с решением для обрезки. Объяснение дается как «Разрешимый с обратным отслеживанием с важной обрезкой, когда текущее среднее значение больше, чем наилучшая найденная средняя стоимость жизненного цикла».

Однако, почему этот метод работает? Если мы на полпути через цикл, а вес больше, чем лучшее найденное среднее, разве не возможно, что с небольшими краями веса мы можем достичь ситуации, когда наш текущий цикл может опуститься ниже, чем лучшее найденное среднее?

Edit: Вот проблема пример: 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. Давайте возьмем самую длинную подпоследовательность contiguos, которая не обрезается эвристикой (имеющей средний вес кромки не более 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.

Что касается вашего вопроса:

Если мы на полпути через цикл и вес больше, чем лучший нашел среднее, не возможно, что с небольшими краями весом мы можем достичь ситуации где наш текущий цикл может пойти ниже, чем у лучших найдено среднее?

Конечно, это так. Но мы можем безопасно обрезать это решение, так как позже мы обнаружим тот же цикл, начиная с другого края, который не будет сокращен. В моем доказательстве говорится, что если мы рассмотрим все возможные циклы на графике, рано или поздно мы найдем оптимальный цикл.