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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Алгоритм отмены цикла минимального среднего веса== Приведенный алгоритм принадлежит к...»)
 
Строка 1: Строка 1:
==Алгоритм отмены цикла минимального среднего веса==
+
В статье описывается один из сильно полиномиальных алгоритмов решения [[Поток минимальной стоимости #Задача о потоке минимальной стоимости|задачи о поиске потока минимальной стоимости]].
 
+
==Алгоритм==
Приведенный алгоритм принадлежит к классу сильно полиномиальных алгоритмов.
+
Приведенный алгоритм основан на идее [[Поток минимальной стоимости #Метод устранения отрицательных циклов в остаточной сети|алгоритма Клейна отмены цикла отрицательного веса]]. Выбор цикла минимального среднего веса вместо случайного делает алгоритм сильно полиномиальным.
 
{{Определение
 
{{Определение
 
|definition='''Сильно полиномиальными''' в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от <tex>V</tex> {{---}} числа вершин и <tex>E</tex> {{---}} числа ребер графа.}}
 
|definition='''Сильно полиномиальными''' в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от <tex>V</tex> {{---}} числа вершин и <tex>E</tex> {{---}} числа ребер графа.}}
 
+
===Описание===
===Описание алгоритма===
+
Обозначим как <tex>c_{f}(C)</tex> остаточную пропускную способность цикла <tex>C</tex> при протекании в сети потока <tex>f</tex>.
Рассмотрим некоторый цикл <tex>C</tex>. Обозначим его стоимость за <tex>p(C)</tex>, а его длину (число ребер, входящих в цикл) за <tex>\texttt{len}(C)</tex>.
+
Cтоимость цикла <tex>C</tex> обозначим за <tex>p(C)</tex>, а длину (число входящих в него ребер) {{---}} за <tex>\texttt{len}(C)</tex>.
 
 
 
{{Определение
 
{{Определение
|definition='''Средним весом цикла''' называется отношение его стоимости к его длине <tex>\mu (C)=\frac{p(C)}{\texttt{len}(C)}</tex>}}
+
|definition='''Средним весом цикла''' будем называть отношение его стоимости к его длине <tex>\mu (C)=\frac{p(C)}{\texttt{len}(C)}</tex>}}
 
+
* '''Шаг1'''. Рассмотрим некоторый поток <tex>f</tex>.  
====Сам алгоритм====
+
* '''Шаг2'''. Найдем цикл <tex>C</tex>, обладающий наименьшим средним весом. Если <tex>\mu (C) \geq 0</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости и алгоритм завершается.
Рассмотрим некоторый поток <tex>f</tex>. Находим цикл <tex>C</tex>, обладающий наименьшим средним весом. Если <tex>\mu (C) \geq 0</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости и алгоритм завершается.
+
* '''Шаг3'''. Отменим цикл <tex>C</tex>, пустив по нему максимально возможный поток: <tex>f = f + c_{f}(C)\cdot f_{C}</tex>. Перейдем к '''шагу 1'''.
Иначе, отменим цикл <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\cdot VE^{2}\log{V})</tex>, при этом
 
<tex>O(VE)</tex> времени тратится на поиск цикла минимального среднего веса.
 
<tex>O(VE)</tex> времени тратится на поиск цикла минимального среднего веса.
 
+
==Алгоритм поиска цикла минимального среднего веса==
===Алгоритм поиска цикла минимального среднего веса===
+
===Наивный способ===
====наивный способ====
+
Устроим [[Вещественный двоичный поиск |двоичный поиск]].
Устроим двоичный поиск.
+
Установим нижнюю и верхнюю границы величины среднего веса цикла <tex>l</tex> и <tex>r</tex> соответственно, вычислим серединное значение <tex>m</tex> и отнимем полученную величину <tex>m</tex> от всех ребер сети. Если теперь в нашей сети есть отрицательный цикл, значит существует цикл с меньшим средним весом, чем <tex>m</tex>. Тогда сдвигаем правую границу на <tex>m</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>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> и ребра из нее во все остальные вершины.
 
Добавим к нашему графу вершину <tex>s</tex> и ребра из нее во все остальные вершины.

Версия 01:26, 26 декабря 2016

В статье описывается один из сильно полиномиальных алгоритмов решения задачи о поиске потока минимальной стоимости.

Алгоритм

Приведенный алгоритм основан на идее алгоритма Клейна отмены цикла отрицательного веса. Выбор цикла минимального среднего веса вместо случайного делает алгоритм сильно полиномиальным.

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

Описание

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

Определение:
Средним весом цикла будем называть отношение его стоимости к его длине [math]\mu (C)=\frac{p(C)}{\texttt{len}(C)}[/math]
  • Шаг1. Рассмотрим некоторый поток [math]f[/math].
  • Шаг2. Найдем цикл [math]C[/math], обладающий наименьшим средним весом. Если [math]\mu (C) \geq 0[/math], то [math]f[/math] — поток минимальной стоимости и алгоритм завершается.
  • Шаг3. Отменим цикл [math]C[/math], пустив по нему максимально возможный поток: [math]f = f + c_{f}(C)\cdot f_{C}[/math]. Перейдем к шагу 1.

Сложность

[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].