Алгоритм отмены — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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

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

Приведенный алгоритм принадлежит к классу сильно полиномиальных алгоритмов.

Определение:
Сильно полиномиальными в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от [math]V[/math] — числа вершин и [math]E[/math] — числа ребер графа.


Описание алгоритма

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


Определение:
Средним весом цикла называется отношение его стоимости к его длине [math]\mu (C)=\frac{p(C)}{\texttt{len}(C)}[/math]


Сам алгоритм

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

Время работы алгоритма

[math]O(VE\cdot VE^{2}\log{V})[/math], при этом [math]O(VE)[/math] времени тратится на поиск цикла минимального среднего веса.

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

наивный способ

Устроим двоичный поиск. установим нижнюю и верхнюю границы [math]l[/math] и [math]r[/math], вычислим середину [math]m[/math] и отнимем величину [math]m[/math] от всех ребер. Если теперь в нашем графе есть отрицательный цикл, значит существует цикл с меньшим средним весом, чем [math]m[/math]. Тогда сдвигаем правую границу на [math]m[/math], иначе — левую. Такой алгоритм будет работать за [math]O(\texttt{log} \frac{1}{\varepsilon} \cdot EV)[/math], где [math]\varepsilon[/math] — точность выбора величины среднего веса цикла.

способ убрать [math]\texttt{log} \frac{1}{\varepsilon}[/math] из оценки

Добавим к нашему графу вершину [math]s[/math] и ребра из нее во все остальные вершины. Рассмотрим алгоритм Форда-Беллмана и попросим его построить нам следущую квадратную матрицу:

d[i][u] // длина минимального пути от s до u ровно из i ребер

Тогда длина оптимального цикла [math]\mu^{*}[/math] минимального среднего веса вычисляется как [math]\min\limits_{u} {\max\limits_{k} {\frac{d[n][u]-d[k][u]}{n-k}}}[/math].

Почему это так? Грубо говоря, достаточно доказать для [math]\mu^{*}=0[/math], так как для других [math]\mu^{*}[/math] можно просто отнять его величину от всех ребер и получить рассматриваемый случай.

--- как же найти сам цикл Запомним, при каких [math]u[/math] и [math]k[/math] достигается этот минимум, и, используя [math]d[n][u][/math], по указателям предков поднимаемся. Как только мы зациклимся — мы нашли цикл минимального среднего веса.

Этот алогоритм работает за [math]O(VE)[/math].