Алгоритм отмены

2016-12-25T21:09:20Z

178.70.222.53: Удалено содержимое страницы

Алгоритм отмены цикла минимального среднего веса

2016-12-25T21:08:58Z

178.70.222.53: Новая страница: «==Алгоритм отмены цикла минимального среднего веса== Приведенный алгоритм принадлежит к...»

==Алгоритм отмены цикла минимального среднего веса==

Приведенный алгоритм принадлежит к классу сильно полиномиальных алгоритмов.
{{Определение
|definition='''Сильно полиномиальными''' в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от <tex>V</tex> {{---}} числа вершин и <tex>E</tex> {{---}} числа ребер графа.}}

===Описание алгоритма===
Рассмотрим некоторый цикл <tex>C</tex>. Обозначим его стоимость за <tex>p(C)</tex>, а его длину (число ребер, входящих в цикл) за <tex>\texttt{len}(C)</tex>.

{{Определение
|definition='''Средним весом цикла''' называется отношение его стоимости к его длине <tex>\mu (C)=\frac{p(C)}{\texttt{len}(C)}</tex>}}

====Сам алгоритм====
Рассмотрим некоторый поток <tex>f</tex>. Находим цикл <tex>C</tex>, обладающий наименьшим средним весом. Если <tex>\mu (C) \geq 0</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости и алгоритм завершается.
Иначе, отменим цикл <tex>C</tex>: <tex>f := f + c_{f}(C)\cdot f_{C}</tex>, где <tex>c_{f}(C)</tex> {{---}} остаточная пропускная способность цикла <tex>C</tex>.
Вернемся к началу алгоритма.

====Время работы алгоритма====
<tex>O(VE\cdot VE^{2}\log{V})</tex>, при этом
<tex>O(VE)</tex> времени тратится на поиск цикла минимального среднего веса.

===Алгоритм поиска цикла минимального среднего веса===
====наивный способ====
Устроим двоичный поиск.
установим нижнюю и верхнюю границы <tex>l</tex> и <tex>r</tex>, вычислим середину <tex>m</tex> и отнимем величину <tex>m</tex> от всех ребер. Если теперь в нашем графе есть отрицательный цикл, значит существует цикл с меньшим средним весом, чем <tex>m</tex>. Тогда сдвигаем правую границу на <tex>m</tex>, иначе {{---}} левую.
Такой алгоритм будет работать за <tex>O(\texttt{log} \frac{1}{\varepsilon} \cdot EV)</tex>, где <tex>\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>.

Викиконспекты - Вклад участника [ru]

Алгоритм отмены

Алгоритм отмены цикла минимального среднего веса