Цикл минимального среднего веса — интуитивное объяснение
На ориентированном графике мы ищем цикл с наименьшим средним весом ребер. Например, граф с узлами 1 и 2 с путем от 1 до 2 длины 2 и от 2 до 1 длины 4 будет иметь минимальный средний цикл 3.
Не в поисках сложного метода (Карп), а в виде простого возврата назад с решением обрезки. Объяснение дано как «Разрешаемое с возвратом назад с важной обрезкой, когда текущее среднее значение больше, чем наилучшая найденная средняя стоимость цикла веса».
Однако почему этот метод работает? Если мы находимся на полпути через цикл, а вес больше, чем наилучшее найденное среднее, разве не возможно, что с небольшими краями веса мы можем достичь ситуации, когда наш текущий цикл может опуститься ниже, чем лучшее найденное среднее?
Изменить: вот пример проблемы: http://uva.onlinejudge.org/index.php?option=onlinejudge&страница = show_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 снова. окончательный 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,
Что касается вашего вопроса:
Если мы находимся в середине цикла, и вес больше, чем лучший
найденное среднее, разве не возможно, что с небольшими краями веса мы можем
достичь ситуации, когда наш текущий цикл может стать ниже, чем лучший
нашел значит?
Конечно, это. Но мы можем безопасно сократить это решение, так как позже мы обнаружим тот же цикл, начинающийся с другого края, который не будет сокращен. Мое доказательство утверждает, что, если мы рассмотрим каждый возможный цикл в графе, рано или поздно мы найдем оптимальный цикл.
Другие решения