Алгоритм отмены — различия между версиями
Строка 26: | Строка 26: | ||
Такой алгоритм будет работать за <tex>O(\texttt{log} \frac{1}{\varepsilon} \cdot EV)</tex>, где <tex>\varepsilon</tex> {{---}} точность выбора величины среднего веса цикла. | Такой алгоритм будет работать за <tex>O(\texttt{log} \frac{1}{\varepsilon} \cdot EV)</tex>, где <tex>\varepsilon</tex> {{---}} точность выбора величины среднего веса цикла. | ||
====способ убрать <tex>\texttt{log} \frac{1}{\varepsilon}</tex> из оценки==== | ====способ убрать <tex>\texttt{log} \frac{1}{\varepsilon}</tex> из оценки==== | ||
+ | |||
+ | Добавим к нашему графу вершину <tex>s</tex> и ребра из нее во все остальные вершины. | ||
+ | Рассмотрим алгоритм Форда-Беллмана и попросим его построить нам следущую квадратную матрицу: | ||
+ | <code> | ||
+ | d[i][u] // длина минимального пути от s до u ровно из i ребер | ||
+ | </code> | ||
+ | Тогда длина оптимального цикла <tex>\mu^{*}</tex> минимального среднего веса вычисляется как <tex>\min\limits_{u} {\max\limits_{k} {\frac{d[n][u]-d[k][u]}{n-k}}}</tex>. | ||
+ | |||
+ | Почему это так? Грубо говоря, достаточно доказать для <tex>\mu^{*}=0</tex>, так как для других <tex>\mu^{*}</tex> можно просто отнять его величину от всех ребер и получить рассматриваемый случай. | ||
+ | |||
+ | --- | ||
+ | как же найти сам цикл | ||
+ | Запомним, при каких <tex>u</tex> и <tex>k</tex> достигается этот минимум, и, используя <tex>d[n][u]</tex>, по указателям предков поднимаемся. Как только мы зациклимся {{---}} мы нашли цикл минимального среднего веса. | ||
+ | |||
+ | Этот алогоритм работает за <tex>O(VE)</tex>. |
Версия 22:58, 25 декабря 2016
Содержание
Алгоритм отмены цикла минимального среднего веса
Приведенный алгоритм принадлежит к классу сильно полиномиальных алгоритмов.
Определение: |
Сильно полиномиальными в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от | — числа вершин и — числа ребер графа.
Описание алгоритма
Рассмотрим некоторый цикл
. Обозначим его стоимость за , а его длину (число ребер, входящих в цикл) за .
Определение: |
Средним весом цикла называется отношение его стоимости к его длине |
Сам алгоритм
Рассмотрим некоторый поток
. Находим цикл , обладающий наименьшим средним весом. Если , то — поток минимальной стоимости и алгоритм завершается. Иначе, отменим цикл : , где — остаточная пропускная способность цикла . Вернемся к началу алгоритма.Время работы алгоритма
, при этом времени тратится на поиск цикла минимального среднего веса.
Алгоритм поиска цикла минимального среднего веса
наивный способ
Устроим двоичный поиск. установим нижнюю и верхнюю границы
и , вычислим середину и отнимем величину от всех ребер. Если теперь в нашем графе есть отрицательный цикл, значит существует цикл с меньшим средним весом, чем . Тогда сдвигаем правую границу на , иначе — левую. Такой алгоритм будет работать за , где — точность выбора величины среднего веса цикла.способ убрать из оценки
Добавим к нашему графу вершину
d[i][u] // длина минимального пути от s до u ровно из i ребер
Тогда длина оптимального цикла
минимального среднего веса вычисляется как .Почему это так? Грубо говоря, достаточно доказать для
, так как для других можно просто отнять его величину от всех ребер и получить рассматриваемый случай.--- как же найти сам цикл Запомним, при каких
и достигается этот минимум, и, используя , по указателям предков поднимаемся. Как только мы зациклимся — мы нашли цикл минимального среднего веса.Этот алогоритм работает за
.