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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Наивный способ)
м (rollbackEdits.php mass rollback)
 
(не показаны 133 промежуточные версии 9 участников)
Строка 3: Строка 3:
 
Приведенный алгоритм основан на идее [[Поток минимальной стоимости #Метод устранения отрицательных циклов в остаточной сети|алгоритма Клейна отмены цикла отрицательного веса]]. Выбор цикла минимального среднего веса вместо случайного делает алгоритм сильно полиномиальным.
 
Приведенный алгоритм основан на идее [[Поток минимальной стоимости #Метод устранения отрицательных циклов в остаточной сети|алгоритма Клейна отмены цикла отрицательного веса]]. Выбор цикла минимального среднего веса вместо случайного делает алгоритм сильно полиномиальным.
 
{{Определение
 
{{Определение
|definition='''Сильно полиномиальными''' в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от <tex>V</tex> {{---}} числа вершин и <tex>E</tex> {{---}} числа ребер графа.}}
+
|definition='''Сильно полиномиальными''' (англ. ''strongly polynomial'') в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от <tex>V</tex> и <tex>E</tex>.}}
 
===Описание===
 
===Описание===
Обозначим как <tex>c_{f}(C)</tex> остаточную пропускную способность цикла <tex>C</tex> при протекании в сети потока <tex>f</tex>.
+
Обозначим как <tex>c_{f}(C)</tex> остаточную [[Определение сети, потока|пропускную способность]] цикла <tex>C</tex> при протекании в сети потока <tex>f</tex>.
 
Cтоимость цикла <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='''Средним весом''' (англ. ''mean weight'') цикла будем называть отношение его стоимости к его длине <tex>\mu (C)=\dfrac{p(C)}{\texttt{len}(C)}</tex>}}
* '''Шаг1'''. Рассмотрим некоторый поток <tex>f</tex>.  
+
Данный алгоритм заключается в последовательной отмене циклов минимального среднего веса в [[Дополняющая сеть, дополняющий путь|остаточной сети]] посредством их насыщения. Алгоритм работает до тех пор, пока минимальный средний вес циклов не окажется положительным, что будет означать, что поток минимальной стоимости найден.
* '''Шаг2'''. Найдем цикл <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>1</tex>'''. Рассмотрим некоторый поток <tex>f</tex>.  
 +
* '''Шаг <tex>2</tex>'''. Найдем цикл <tex>C</tex>, обладающий наименьшим средним весом. Если <tex>\mu (C) \geqslant 0</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости и алгоритм завершается.
 +
* '''Шаг <tex>3</tex>'''. Отменим цикл <tex>C</tex>, пустив по нему максимально возможный поток: <tex>f = f + c_{f}(C)\cdot f_{C}</tex>. Перейдем к '''шагу <tex>1</tex>'''.
 +
 
 
===Сложность===
 
===Сложность===
<tex>O(VE\cdot VE^{2}\log{V})</tex>, при этом
+
Для сетей с целочисленными стоимостями на ребрах <tex>O(VE\cdot VE\log{CV})</tex>, с вещественными {{---}} <tex>O(VE\cdot VE^{2}\log{V})</tex>.
<tex>O(VE)</tex> времени тратится на поиск цикла минимального среднего веса.
+
В обоих случаях <tex>O(VE)</tex> времени тратится на поиск цикла минимального среднего веса.
 +
 
 +
===Псевдокод===
 +
  '''Edge[]''' findMin('''Graph''' G)
 +
      '''while''' f
 +
          <font color="green">// найдём M(C) {{---}} вес минимального цикла</font>
 +
          C = c : M(c) = <tex>\min\limits_c</tex> M(c) 
 +
          '''if''' M(C) <tex>\geqslant</tex> 0
 +
              <font color="green">// Если величина M(C) положительна, то мы нашли f {{---}} поток минимальной стоимости, на этом алгоритм завершается</font>
 +
              '''return''' f                           
 +
          '''else'''
 +
              <font color="green">// в противном случае отменяем цикл</font>
 +
              f += c_f * f(C)
 +
 
 +
===Корректность===
 +
Пусть <tex>f</tex> {{---}} поток минимальной стоимости. Введём на нашей сети функцию [[Алгоритм Джонсона|потенциалов]] <tex>\varphi</tex>.
 +
{{Определение
 +
|definition='''Приведённой стоимостью''' (англ. ''reduced cost'') ребра назовем следующую величину: <tex>p_{\varphi}(uv)=\varphi(u) + p(uv) - \varphi(v)</tex>.}}
 +
Иными словами, приведённая стоимость {{---}} это сколько нужно потратить денег, чтобы перевезти единицу жидкости из <tex>u</tex> в <tex>v</tex> (её нужно купить в <tex>u</tex>, перевезти из <tex>u</tex> в <tex>v</tex> и продать в <tex>v</tex>).
 +
 
 +
{{Лемма
 +
|id=lemma1
 +
|about=<tex>1</tex>
 +
|statement=Если <tex>f</tex> {{---}} поток минимальной стоимости, то <tex>\exists \varphi</tex> такое, что <tex>\forall uv: \; c_{f}(uv) > 0 \implies p_{\varphi}(uv) \geqslant 0</tex>.
 +
|proof=
 +
:Рассмотрим остаточную сеть {{---}} граф <tex>G_{f}</tex>. В нем нет отрицательных циклов, так как <tex>f</tex> {{---}} поток минимальной стоимости<ref>[[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]</ref>.
 +
 
 +
:Добавим вершину <tex>a</tex> и проведем из нее ребро стоимости <tex>0</tex> во все вершины графа <tex>G_{f}</tex>. В качестве <tex>\varphi(u)</tex> выберем стоимость минимального пути из <tex>a</tex> в <tex>u</tex>.
 +
 
 +
:Рассмотрим теперь некоторое ребро <tex>uv</tex>. Понятно, что <tex>\varphi(v) \leqslant \varphi(u) + p(uv)</tex>. (Здесь сравниваются минимальный путь <tex>a \rightsquigarrow v</tex> и путь <tex>a \rightsquigarrow u \rightarrow v</tex>). Перенеся <tex>\varphi(v)</tex> в другую часть неравенства, получаем <tex>0 \leqslant \varphi(u) + p(uv) - \varphi(v)</tex> или <tex>0 \leqslant p_{\varphi}(uv)</tex>.}}
 +
 
 +
{{Определение
 +
|definition=Будем говорить, что поток <tex>f</tex> {{---}} '''<tex>\varepsilon</tex>-оптимальный''' (англ. ''<tex>\varepsilon</tex>-optimal''), если <tex>\exists \varphi</tex> такая, что <tex>\forall uv: c_{f}(uv) > 0 \implies p_{\varphi}(uv) \geqslant -\varepsilon</tex>.}}
 +
 
 +
{{Лемма
 +
|id=lemma2
 +
|about=<tex>2</tex>
 +
|statement=Если стоимости целочисленны и поток <tex>f</tex> {{---}} <tex>\varepsilon</tex>-оптимальный, где <tex>\varepsilon < \dfrac{1}{V}</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости.
 +
|proof=
 +
:Рассмотрим цикл в остаточной сети <tex>C</tex>. Заметим, что <tex>p(C)=p_{\varphi}(C)</tex> (для доказательства этого факта достаточно расписать <tex>p_{\varphi}(C)</tex> по определению).
 +
 
 +
:Возьмем <tex>\varphi</tex> такое, что стоимости всех ребер в <tex>C</tex> не меньше <tex>-\varepsilon</tex>. Тогда стоимость всего цикла <tex>p_{\varphi}(C)\geqslant -V\cdot \varepsilon</tex> (в цикле не больше <tex>V</tex> ребер). Таким образом, <tex>p_{\varphi}(C) > -1</tex>, то есть <tex>p(C) > -1</tex>. Но исходные пропускные способности были целочисленными, поэтому <tex>p(C) \geqslant 0</tex>, а это означает, что в остаточной сети нет отрицательных циклов, и, соответственно, <tex>f</tex> {{---}} поток минимальной стоимости.}}
 +
 
 +
Обозначим за <tex>\mu^{*}</tex> минимальную величину среди средних весов циклов для потока <tex>f</tex>, а за <tex>\varepsilon^{*}</tex> минимальное <tex>\varepsilon</tex> такое, что поток <tex>f</tex> {{---}} <tex>\varepsilon</tex>-оптимальный.
 +
{{Лемма
 +
|id=lemma3
 +
|about=<tex>3</tex>
 +
|statement=Если <tex>f</tex> {{---}} поток не минимальной стоимости, то <tex>\varepsilon^{*}=-\mu^{*}</tex>.
 +
|proof=
 +
:Пусть <tex>C</tex> {{---}} цикл минимального среднего веса в остаточной сети.
 +
*Покажем, что <tex>\mu^{*} \geqslant -\varepsilon^{*}</tex>.
 +
:Поскольку поток <tex>f</tex> является <tex>\varepsilon^{*}</tex>-оптимальным, верно следующее: <tex>p(C) = p_{\varphi}(C) \geqslant -\texttt{len}(C) \cdot \varepsilon^{*}</tex> или <tex>\dfrac{p(C)}{\texttt{len}(C)} \geqslant -\varepsilon^{*} </tex>, то есть <tex>\mu(C)=\mu^{*} \geqslant -\varepsilon^{*}</tex>.
 +
 
 +
*Теперь покажем, что <tex>\mu^{*} \leqslant -\varepsilon^{*}</tex>.
 +
:Пусть <tex>p'(uv)=p(uv)-\mu^{*}</tex> для любого <tex>uv \in E_{f}</tex>. Логичным будет также обозначить для некоторого цикла <tex>C</tex> за <tex>\mu'(C)</tex> величину <tex>\dfrac{p'(C)}{\texttt{len}(C)}</tex>. Таким образом, для любого цикла <tex>C</tex>, <tex>\mu'(C)=\mu(C)-\mu^{*}\geqslant 0</tex>.
 +
:Далее проведем рассуждения, аналогичные доказательству [[#lemma1|леммы <tex>1</tex>]].
 +
:Добавим вершину <tex>a</tex> и проведем из нее ребро стоимости <tex>0</tex> во все вершины графа <tex>G_{f}</tex>. В качестве <tex>\varphi(u)</tex> выберем стоимость (считая стоимостью функцию <tex>p'</tex>) минимального пути из <tex>a</tex> в <tex>u</tex>.
 +
:Таким образом, <tex>\varphi(v) \leqslant \varphi(u) + p'(uv) = \varphi(u) + p(uv) - \mu^{*}</tex>. Отсюда получаем, что <tex>p_{\varphi}(uv) \geqslant \mu^{*}</tex> для любого ребра <tex>uv</tex> из остаточной сети <tex>E_{f}</tex>, что означает, что <tex>f</tex> {{---}} <tex>(-\mu^{*})</tex>-оптимальный, и, по определению <tex>\varepsilon^{*}</tex>, <tex>\varepsilon^{*} \leqslant -\mu^{*}</tex>.
 +
}}
 +
 
 +
{{Лемма
 +
|id=lemma4
 +
|about=<tex>4</tex>
 +
|statement=Отмена цикла минимального среднего веса не увеличивает <tex>\varepsilon^{*}</tex>.
 +
|proof=
 +
:Пусть <tex>C</tex> {{---}} цикл минимального среднего веса, который мы хотим отменить на текущем шаге нашего алгоритма. Перед тем, как мы отменим этот цикл, любое ребро в остаточной сети, в том числе, любое входящее в цикл <tex>C</tex> ребро <tex>uv</tex> удовлетворяет свойству <tex>\varepsilon^{*}</tex>-оптимальности: <tex>p_{\varphi}(uv) \geqslant -\varepsilon^{*}</tex>.
 +
:По [[#lemma3|лемме <tex>3</tex>]], <tex>\varepsilon^{*}=-\mu^{*}</tex>, то есть <tex>p_{\varphi}(uv) \geqslant \mu^{*}</tex>. Но поскольку <tex>\mu^{*}</tex> {{---}} средний вес цикла, то <tex>p_{\varphi}(uv) = \mu^{*} = -\varepsilon^{*}</tex>.
 +
:По [[Поток минимальной стоимости #Свойства стоимости|свойству антисимметричности потока]], после отмены цикла <tex>C</tex>, в остаточной сети появятся ребра стоимости <tex>\varepsilon</tex>. Таким образом, свойство <tex>p_{\varphi}(uv) \geqslant -\varepsilon</tex> все еще выполняется.
 +
}}
 +
 
 +
{{Определение
 +
|definition='''Допустимым графом''' (англ. ''admissible graph'') будем называть такой подграф остаточной сети, что он включает только ребра отрицательной приведенной стоимости. <tex>H=\{uv \in E_{f}\;|\; p_{\varphi}(uv) < 0\}</tex>
 +
}}
 +
 
 +
{{Лемма
 +
|id=lemma5
 +
|about=<tex>5</tex>
 +
|statement=Пусть <tex>f</tex> {{---}} некоторый поток, а <tex>f'</tex> {{---}} поток после <tex>E</tex> отмен циклов минимального среднего веса. Тогда <tex>\varepsilon'^{*} \leqslant \left(1-\dfrac{1}{V}\right)\varepsilon^{*}</tex>, где <tex>\varepsilon'^{*}</tex> {{---}} минимальное <tex>\varepsilon</tex> такое, что поток <tex>f'</tex> <tex>\varepsilon</tex>-оптимальный.
 +
|proof=
 +
:Изначально любое ребро <tex>uv</tex> удовлетворяет свойству <tex>p_{\varphi}(uv) \geqslant -\varepsilon^{*}</tex>. Отмена цикла добавляет в остаточную сеть <tex>G_{f}</tex> только ребра положительной приведенной стоимости (см. [[#lemma4|лемму <tex>4</tex>]]) и удаляет из сети <tex>G</tex> как минимум одно ребро. Рассмотрим два случая:
 +
:#Ни один из отмененных циклов не содержал ребер, обладающих неотрицательной приведенной стоимостью. Тогда каждая отмена цикла уменьшает размер допустимого графа <tex>H</tex> и после <tex>E</tex> отмен граф <tex>H</tex> пуст, что означает, что <tex>f'</tex> {{---}} оптимальный поток, то есть <tex>\varepsilon'^{*}=0</tex>.
 +
:#Некоторые из отмененных циклов содержали ребра неотрицательной приведенной стоимости. Пусть впервые такое случилось на <tex>i</tex>-ой итерации, и, соответственно, <tex>C_{i}</tex> {{---}} первый из таких циклов. Для <tex>C_{i}</tex> имеем, что каждое его ребро обладает приведенной стоимостью как минимум <tex>-\varepsilon_{i}^{*}</tex> (при этом <tex>\varepsilon'^{*} \leqslant \varepsilon_{i}^{*} \leqslant \varepsilon^{*}</tex> по [[#lemma4|лемме <tex>4</tex>]]), хотя бы одно из ребер <tex>C_{i}</tex> обладает неотрицательной приведенной стоимостью и количество ребер в <tex>C_{i}</tex> не превышает <tex>V</tex>. Тогда средний вес этого цикла <tex>\mu(C_{i}) = \mu_{i}^{*} \geqslant -\left(1-\dfrac{1}{V}\right)\varepsilon_{i}^{*} \geqslant - \left(1-\dfrac{1}{V}\right)\varepsilon^{*}</tex>, и <tex>\varepsilon'^{*} \leqslant \varepsilon_{i}^{*} = -\mu_{i}^{*} \leqslant \left(1-\dfrac{1}{V}\right)\varepsilon^{*}</tex>.}}
 +
 
 +
{{Определение
 +
|definition='''<tex>\varepsilon</tex>-фиксированным''' (англ. ''<tex>\varepsilon</tex>-fixed'') будем называть ребро, поток через которое неизменен для любых <tex>\varepsilon</tex>-оптимальных потоков в сети.}}
 +
 
 +
{{Теорема
 +
|id=theorem1
 +
|statement=Пусть поток <tex>f</tex> является <tex>\varepsilon</tex>-оптимальным с функцией потенциалов <tex>\varphi</tex>. Также пусть для некоторого ребра <tex>uv \; \left|p_{\varphi}(uv)\right| \geqslant 2V\varepsilon</tex>. Тогда ребро <tex>uv</tex> <tex>\varepsilon</tex>-фиксировано.
 +
|proof=
 +
:По свойству антисимметричности, достаточно будет доказать теорему для случая <tex>p_{\varphi}(uv) \geqslant 2V\varepsilon</tex>.
 +
 
 +
:Рассмотрим такой поток <tex>f'</tex>, что <tex>f'(uv) \neq f(uv)</tex>. Поскольку <tex>p_{\varphi}(uv) \geqslant 2V\varepsilon > \varepsilon</tex>, поток по ребру <tex>uv</tex> должен быть как можно меньше, то есть <tex>f(uv) = -c(uv)</tex>, и тогда раз <tex>f'(uv) \neq f(uv)</tex>, то <tex>f'(uv) > f(uv)</tex>.
 +
 
 +
:Покажем теперь, что <tex>f'</tex> не <tex>\varepsilon</tex>-оптимальный.
 +
:Обозначим за <tex>G_{>}</tex> подграф <tex>G</tex> такой, что <tex>G_{>}=(V, \{uv \in E \;|\; f'(uv) > f(uv) \})</tex>. Рассмотрим некоторое ребро <tex>uv</tex> в <tex>G_{>}</tex>. Поскольку <tex>f</tex> и <tex>f'</tex> являются циркуляциями, в <tex>G_{>}</tex> должен содержаться простой цикл <tex>C</tex>, проходящий через <tex>uv</tex>. Поскольку все ребра в <tex>C</tex> {{---}} остаточные, стоимость <tex>C</tex> не меньше <tex>p_{\varphi}(uv) - (\texttt{len}(C)-1)\varepsilon \geqslant 2V\varepsilon - (V-1)\varepsilon > V\varepsilon</tex>.
 +
:Теперь рассмотрим цикл <tex>\overline{C}</tex>, который получен из <tex>C</tex> разворотом всех его ребер. Заметим, что <tex>\overline{C}</tex> является циклом в <tex>G_{<}=(V,\{uv \in E \;|\; f'(uv) < f(uv)\})</tex> и, соответственно, циклом в <tex>G_{f}</tex>. По свойству антисимметричности, стоимость <tex>\overline{C}</tex> меньше, чем <tex>-V\varepsilon</tex> и, таким образом, <tex>\mu(\overline{C}) < -\varepsilon</tex>. Откуда по [[#lemma3|лемме <tex>3</tex>]] имеем, что <tex>f'</tex> не <tex>\varepsilon</tex>-оптимален.
 +
}}
 +
 
 +
{{Лемма
 +
|about=доказательство оценки времени работы алгоритма в случае вещественных стоимостей
 +
|statement=Пусть <tex>k=VE(\lceil \log V + 1 \rceil)</tex>. Разобьем работу алгоритма на группы по <tex>k</tex> последовательных итераций. Утверждается, что каждая группа фиксирует поток на независимом ребре <tex>uv</tex>, то есть итерации из другой группы не меняют величину <tex>f(uv)</tex>.
 +
|proof=
 +
:Оценка времени работы следует непосредственно из этого утверждения.
 +
:Чтобы доказать его, рассмотрим некоторую группу итераций. Пусть <tex>f</tex> {{---}} поток до первой итерации, а <tex>f'</tex> {{---}} после последней итерации этой группы. Обозначим за <tex>\varepsilon'^{*}</tex> минимальное <tex>\varepsilon</tex> такое, что поток <tex>f'</tex> <tex>\varepsilon</tex>-оптимальный, а за <tex>\varphi'</tex> {{---}} функцию потенциалов такую, что <tex>f'</tex> удовлетворяет свойству <tex>\varepsilon'^{*}</tex>-оптимальности. Выбор <tex>k</tex> и [[#lemma5|лемма <tex>5</tex>]] дают нам следующее неравенство: <tex>\varepsilon'^{*} \leqslant \varepsilon^{*} \left(1-\dfrac{1}{V} \right)^{V(\log V + 1)} \leqslant \dfrac{\varepsilon^{*}}{2V}</tex>.
 +
:Рассмотрим цикл <tex>C</tex>, отмененный на первой итерации рассматриваемой группы. Поскольку средний вес цикла <tex>C</tex> равен <tex>-\varepsilon^{*}</tex> (см. [[#lemma3|лемму <tex>3</tex>]]), некоторое ребро <tex>uv</tex> цикла <tex>C</tex> должно иметь приведенную стоимость <tex>p_{\varphi'}(uv) \leqslant -\varepsilon^{*} \leqslant -2V\varepsilon'^{*}</tex>. Таким образом, поток на ребре <tex>uv</tex> не изменится при итерациях, происходящих после этой группы. Таким образом, по [[#theorem1|теореме]] каждая группа фиксирует поток на независимом ребре.}}
 +
 
 
==Алгоритм поиска цикла минимального среднего веса==
 
==Алгоритм поиска цикла минимального среднего веса==
 
===Наивный способ===
 
===Наивный способ===
 
Устроим [[Вещественный двоичный поиск |двоичный поиск]].
 
Устроим [[Вещественный двоичный поиск |двоичный поиск]].
 
Установим нижнюю и верхнюю границы величины среднего веса цикла <tex>l</tex> и <tex>r</tex> соответственно, вычислим серединное значение <tex>m</tex> и отнимем полученную величину <tex>m</tex> от всех ребер сети. Если теперь в нашей сети есть отрицательный цикл (этот факт можно проверить при помощи [[Алгоритм Форда-Беллмана #Нахождение отрицательного цикла|алгоритма Форда-Беллмана]]), значит существует цикл с меньшим средним весом, чем <tex>m</tex>. Тогда продолжим поиск среди значений в диапазоне от <tex>l</tex> до <tex>m</tex>, иначе {{---}} от <tex>m</tex> до <tex>r</tex>.
 
Установим нижнюю и верхнюю границы величины среднего веса цикла <tex>l</tex> и <tex>r</tex> соответственно, вычислим серединное значение <tex>m</tex> и отнимем полученную величину <tex>m</tex> от всех ребер сети. Если теперь в нашей сети есть отрицательный цикл (этот факт можно проверить при помощи [[Алгоритм Форда-Беллмана #Нахождение отрицательного цикла|алгоритма Форда-Беллмана]]), значит существует цикл с меньшим средним весом, чем <tex>m</tex>. Тогда продолжим поиск среди значений в диапазоне от <tex>l</tex> до <tex>m</tex>, иначе {{---}} от <tex>m</tex> до <tex>r</tex>.
Такой алгоритм будет работать за <tex>O(\texttt{log} \frac{1}{\varepsilon} \cdot EV)</tex>, где <tex>\varepsilon</tex> {{---}} точность выбора величины среднего веса цикла.
 
  
===способ убрать <tex>\texttt{log} \frac{1}{\varepsilon}</tex> из оценки===
+
Тогда, если <tex>C_{max}</tex> и <tex>C_{min}</tex> {{---}} максимальная и минимальная возможные величины среднего веса цикла соответственно, такой алгоритм для вещественных значений весов ребер будет работать за <tex>O\left(\log \dfrac{C_{max}-C_{min}}{\varepsilon} \cdot EV\right)</tex>, где <tex>\varepsilon</tex> {{---}} точность выбора среднего веса цикла.
 +
При этом для целочисленных значений на ребрах точность выбора величины среднего веса цикла не может превысить <tex>\dfrac{1}{V}</tex>, что дает нам оценку <tex>O\left(\log (V(C_{max}-C_{min})) \cdot EV\right)</tex>.
 +
 
 +
====Псевдокод====
 +
 
 +
  '''func''' findMinCycleBinarySearch('''int''' l, '''int''' r)
 +
      <font color="green">// находим среднюю величину <tex>m</tex></font>
 +
      m = (l + r) / 2
 +
      <font color="green">// вычитаем её из веса каждого ребра в сети</font>
 +
      '''for''' e '''in''' edges
 +
          e.weight -= m
 +
      '''while''' l > r - 1
 +
      <!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
 +
          '''if''' <tex>\exists</tex>C : M(C) < 0 <!--- cho-t xz za4em C: mb exists? eee ugadala)0))--->
 +
              <font color="green">// если есть отрицательный цикл, то веса циклов находятся в диапазоне <tex>[l;m]</tex>
 +
              // рассмотрим этот промежуток</font>
 +
              findMinCycleBinarySearch (l, m)
 +
          '''else'''
 +
              <font color="green">// иначе запускаем двоичный поиск на отрезке <tex>[m;r]</tex></font>
 +
              findMinCycleBinarySearch (m, r)
 +
 
 +
===Продвинутый алгоритм===
 +
Добавим к нашему графу вершину <tex>s</tex> и рёбра из неё во все остальные вершины.
 +
Запустим [[алгоритм Форда-Беллмана]] и попросим его построить нам квадратную матрицу со следующим условием: <tex>d[i][u]</tex> {{---}} длина минимального пути от <tex>s</tex> до <tex>u</tex> ровно из <tex>i</tex> ребер.
 +
Тогда длина оптимального цикла <tex>\mu^{*}</tex> минимального среднего веса вычисляется как <tex>\min\limits_{u} {\max\limits_{k} {\dfrac{d[n][u]-d[k][u]}{n-k}}}</tex>.
 +
 
 +
Достаточно будет доказать это правило для <tex>\mu^{*}=0</tex>, так как для других <tex>\mu^{*}</tex> можно просто отнять эту величину от всех ребер и получить снова случай с <tex>\mu^{*}=0</tex>.
 +
 
 +
Чтобы найти цикл после построения матрицы <tex>d[k][u]</tex>, запомним, при каких <tex>u</tex> и <tex>k</tex> достигается оптимальное значение <tex>\mu^{*}</tex>, и, используя <tex>d[n][u]</tex>, поднимемся по указателям предков. Как только мы попадем в уже посещенную вершину {{---}} мы нашли цикл минимального среднего веса.
 +
 
 +
Этот алгоритм работает за <tex>O(VE)</tex> <ref>[[Алгоритм Форда-Беллмана #Сложность| Сложность алгоритма Форда-Беллмана]]</ref>.
 +
 
 +
====Псевдокод====
 +
  '''func''' findMinCycle('''Graph''' G)
 +
      <font color="green">// вводим мнимую вершину <tex>s</tex>, от которой проведём рёбра нулевого веса в каждую вершину графа</font>
 +
      '''Node''' s
 +
      '''Edge[]''' e
 +
      insert(s) 
 +
      i = 0                                     
 +
      '''for''' u '''in''' G
 +
          e[i].begin = s
 +
          e[i].end = u
 +
          e[i].weight = 0
 +
          i++
 +
      <font color="green">// строим матрицу кратчайших расстояний, запустив алгоритм Форда-Беллмана из вершины <tex>s</tex></font>
 +
      fordBellman(s)
 +
      <font color="green">// <tex>m</tex> {{---}} длина оптимального цикла</font>
 +
      m = <tex>\min\limits_{u} {\max\limits_{k} }</tex>((d[n][u] - d[k][u]) / (n - k))
 +
      <!-----<font color="green">// запомнив значения <tex>u</tex> и <tex>k</tex>, дающих оптимальный результат, найдём цикл</font>--------->
 +
      <!----чуть не забыла про отступы, дура тупая----->
  
Добавим к нашему графу вершину <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> можно просто отнять его величину от всех ребер и получить рассматриваемый случай.
+
==Примечания==
 +
<references/>
  
---
+
==Источники информации==
как же найти сам цикл
+
* [https://youtu.be/bykbw7HovSo?t=4287 Лекция 14 | Дополнительные главы алгоритмов | Андрей Станкевич | CSC | Лекториум]
Запомним, при каких <tex>u</tex> и <tex>k</tex> достигается этот минимум, и, используя <tex>d[n][u]</tex>, по указателям предков поднимаемся. Как только мы зациклимся {{---}} мы нашли цикл минимального среднего веса.
+
* [http://sirius.cs.put.poznan.pl/~inf84789/acm/p873-goldberg.pdf A.V.Goldberg and R.E.Tarjan {{---}} Finding Minimum-Cost Circulations by Cancelling Negative Cycles (Journal of the Association for Computing Machinery. Vol. 36, No. 4. October 1989. pp. 873-886.)]
 +
*[https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2008/lecture-notes/lec4.pdf Lecture by M.X.Goemans on Goldberg-Tarjan Min-Cost Circulation Algorithm]
  
Этот алогоритм работает за <tex>O(VE)</tex>.
+
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Задача о потоке минимальной стоимости]]

Текущая версия на 19:26, 4 сентября 2022

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

Алгоритм

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

Определение:
Сильно полиномиальными (англ. strongly polynomial) в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от [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].

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

Данный алгоритм заключается в последовательной отмене циклов минимального среднего веса в остаточной сети посредством их насыщения. Алгоритм работает до тех пор, пока минимальный средний вес циклов не окажется положительным, что будет означать, что поток минимальной стоимости найден.

Более формально:

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

Сложность

Для сетей с целочисленными стоимостями на ребрах [math]O(VE\cdot VE\log{CV})[/math], с вещественными — [math]O(VE\cdot VE^{2}\log{V})[/math]. В обоих случаях [math]O(VE)[/math] времени тратится на поиск цикла минимального среднего веса.

Псевдокод

 Edge[] findMin(Graph G)
     while f
         // найдём M(C) — вес минимального цикла
         C = c : M(c) = [math]\min\limits_c[/math] M(c)  
         if M(C) [math]\geqslant[/math] 0
             // Если величина M(C) положительна, то мы нашли f — поток минимальной стоимости, на этом алгоритм завершается
             return f                             
         else
             // в противном случае отменяем цикл
             f += c_f * f(C)

Корректность

Пусть [math]f[/math] — поток минимальной стоимости. Введём на нашей сети функцию потенциалов [math]\varphi[/math].

Определение:
Приведённой стоимостью (англ. reduced cost) ребра назовем следующую величину: [math]p_{\varphi}(uv)=\varphi(u) + p(uv) - \varphi(v)[/math].

Иными словами, приведённая стоимость — это сколько нужно потратить денег, чтобы перевезти единицу жидкости из [math]u[/math] в [math]v[/math] (её нужно купить в [math]u[/math], перевезти из [math]u[/math] в [math]v[/math] и продать в [math]v[/math]).

Лемма ([math]1[/math]):
Если [math]f[/math] — поток минимальной стоимости, то [math]\exists \varphi[/math] такое, что [math]\forall uv: \; c_{f}(uv) \gt 0 \implies p_{\varphi}(uv) \geqslant 0[/math].
Доказательство:
[math]\triangleright[/math]
Рассмотрим остаточную сеть — граф [math]G_{f}[/math]. В нем нет отрицательных циклов, так как [math]f[/math] — поток минимальной стоимости[1].
Добавим вершину [math]a[/math] и проведем из нее ребро стоимости [math]0[/math] во все вершины графа [math]G_{f}[/math]. В качестве [math]\varphi(u)[/math] выберем стоимость минимального пути из [math]a[/math] в [math]u[/math].
Рассмотрим теперь некоторое ребро [math]uv[/math]. Понятно, что [math]\varphi(v) \leqslant \varphi(u) + p(uv)[/math]. (Здесь сравниваются минимальный путь [math]a \rightsquigarrow v[/math] и путь [math]a \rightsquigarrow u \rightarrow v[/math]). Перенеся [math]\varphi(v)[/math] в другую часть неравенства, получаем [math]0 \leqslant \varphi(u) + p(uv) - \varphi(v)[/math] или [math]0 \leqslant p_{\varphi}(uv)[/math].
[math]\triangleleft[/math]


Определение:
Будем говорить, что поток [math]f[/math][math]\varepsilon[/math]-оптимальный (англ. [math]\varepsilon[/math]-optimal), если [math]\exists \varphi[/math] такая, что [math]\forall uv: c_{f}(uv) \gt 0 \implies p_{\varphi}(uv) \geqslant -\varepsilon[/math].


Лемма ([math]2[/math]):
Если стоимости целочисленны и поток [math]f[/math][math]\varepsilon[/math]-оптимальный, где [math]\varepsilon \lt \dfrac{1}{V}[/math], то [math]f[/math] — поток минимальной стоимости.
Доказательство:
[math]\triangleright[/math]
Рассмотрим цикл в остаточной сети [math]C[/math]. Заметим, что [math]p(C)=p_{\varphi}(C)[/math] (для доказательства этого факта достаточно расписать [math]p_{\varphi}(C)[/math] по определению).
Возьмем [math]\varphi[/math] такое, что стоимости всех ребер в [math]C[/math] не меньше [math]-\varepsilon[/math]. Тогда стоимость всего цикла [math]p_{\varphi}(C)\geqslant -V\cdot \varepsilon[/math] (в цикле не больше [math]V[/math] ребер). Таким образом, [math]p_{\varphi}(C) \gt -1[/math], то есть [math]p(C) \gt -1[/math]. Но исходные пропускные способности были целочисленными, поэтому [math]p(C) \geqslant 0[/math], а это означает, что в остаточной сети нет отрицательных циклов, и, соответственно, [math]f[/math] — поток минимальной стоимости.
[math]\triangleleft[/math]

Обозначим за [math]\mu^{*}[/math] минимальную величину среди средних весов циклов для потока [math]f[/math], а за [math]\varepsilon^{*}[/math] минимальное [math]\varepsilon[/math] такое, что поток [math]f[/math][math]\varepsilon[/math]-оптимальный.

Лемма ([math]3[/math]):
Если [math]f[/math] — поток не минимальной стоимости, то [math]\varepsilon^{*}=-\mu^{*}[/math].
Доказательство:
[math]\triangleright[/math]
Пусть [math]C[/math] — цикл минимального среднего веса в остаточной сети.
  • Покажем, что [math]\mu^{*} \geqslant -\varepsilon^{*}[/math].
Поскольку поток [math]f[/math] является [math]\varepsilon^{*}[/math]-оптимальным, верно следующее: [math]p(C) = p_{\varphi}(C) \geqslant -\texttt{len}(C) \cdot \varepsilon^{*}[/math] или [math]\dfrac{p(C)}{\texttt{len}(C)} \geqslant -\varepsilon^{*} [/math], то есть [math]\mu(C)=\mu^{*} \geqslant -\varepsilon^{*}[/math].
  • Теперь покажем, что [math]\mu^{*} \leqslant -\varepsilon^{*}[/math].
Пусть [math]p'(uv)=p(uv)-\mu^{*}[/math] для любого [math]uv \in E_{f}[/math]. Логичным будет также обозначить для некоторого цикла [math]C[/math] за [math]\mu'(C)[/math] величину [math]\dfrac{p'(C)}{\texttt{len}(C)}[/math]. Таким образом, для любого цикла [math]C[/math], [math]\mu'(C)=\mu(C)-\mu^{*}\geqslant 0[/math].
Далее проведем рассуждения, аналогичные доказательству леммы [math]1[/math].
Добавим вершину [math]a[/math] и проведем из нее ребро стоимости [math]0[/math] во все вершины графа [math]G_{f}[/math]. В качестве [math]\varphi(u)[/math] выберем стоимость (считая стоимостью функцию [math]p'[/math]) минимального пути из [math]a[/math] в [math]u[/math].
Таким образом, [math]\varphi(v) \leqslant \varphi(u) + p'(uv) = \varphi(u) + p(uv) - \mu^{*}[/math]. Отсюда получаем, что [math]p_{\varphi}(uv) \geqslant \mu^{*}[/math] для любого ребра [math]uv[/math] из остаточной сети [math]E_{f}[/math], что означает, что [math]f[/math][math](-\mu^{*})[/math]-оптимальный, и, по определению [math]\varepsilon^{*}[/math], [math]\varepsilon^{*} \leqslant -\mu^{*}[/math].
[math]\triangleleft[/math]
Лемма ([math]4[/math]):
Отмена цикла минимального среднего веса не увеличивает [math]\varepsilon^{*}[/math].
Доказательство:
[math]\triangleright[/math]
Пусть [math]C[/math] — цикл минимального среднего веса, который мы хотим отменить на текущем шаге нашего алгоритма. Перед тем, как мы отменим этот цикл, любое ребро в остаточной сети, в том числе, любое входящее в цикл [math]C[/math] ребро [math]uv[/math] удовлетворяет свойству [math]\varepsilon^{*}[/math]-оптимальности: [math]p_{\varphi}(uv) \geqslant -\varepsilon^{*}[/math].
По лемме [math]3[/math], [math]\varepsilon^{*}=-\mu^{*}[/math], то есть [math]p_{\varphi}(uv) \geqslant \mu^{*}[/math]. Но поскольку [math]\mu^{*}[/math] — средний вес цикла, то [math]p_{\varphi}(uv) = \mu^{*} = -\varepsilon^{*}[/math].
По свойству антисимметричности потока, после отмены цикла [math]C[/math], в остаточной сети появятся ребра стоимости [math]\varepsilon[/math]. Таким образом, свойство [math]p_{\varphi}(uv) \geqslant -\varepsilon[/math] все еще выполняется.
[math]\triangleleft[/math]


Определение:
Допустимым графом (англ. admissible graph) будем называть такой подграф остаточной сети, что он включает только ребра отрицательной приведенной стоимости. [math]H=\{uv \in E_{f}\;|\; p_{\varphi}(uv) \lt 0\}[/math]


Лемма ([math]5[/math]):
Пусть [math]f[/math] — некоторый поток, а [math]f'[/math] — поток после [math]E[/math] отмен циклов минимального среднего веса. Тогда [math]\varepsilon'^{*} \leqslant \left(1-\dfrac{1}{V}\right)\varepsilon^{*}[/math], где [math]\varepsilon'^{*}[/math] — минимальное [math]\varepsilon[/math] такое, что поток [math]f'[/math] [math]\varepsilon[/math]-оптимальный.
Доказательство:
[math]\triangleright[/math]
Изначально любое ребро [math]uv[/math] удовлетворяет свойству [math]p_{\varphi}(uv) \geqslant -\varepsilon^{*}[/math]. Отмена цикла добавляет в остаточную сеть [math]G_{f}[/math] только ребра положительной приведенной стоимости (см. лемму [math]4[/math]) и удаляет из сети [math]G[/math] как минимум одно ребро. Рассмотрим два случая:
  1. Ни один из отмененных циклов не содержал ребер, обладающих неотрицательной приведенной стоимостью. Тогда каждая отмена цикла уменьшает размер допустимого графа [math]H[/math] и после [math]E[/math] отмен граф [math]H[/math] пуст, что означает, что [math]f'[/math] — оптимальный поток, то есть [math]\varepsilon'^{*}=0[/math].
  2. Некоторые из отмененных циклов содержали ребра неотрицательной приведенной стоимости. Пусть впервые такое случилось на [math]i[/math]-ой итерации, и, соответственно, [math]C_{i}[/math] — первый из таких циклов. Для [math]C_{i}[/math] имеем, что каждое его ребро обладает приведенной стоимостью как минимум [math]-\varepsilon_{i}^{*}[/math] (при этом [math]\varepsilon'^{*} \leqslant \varepsilon_{i}^{*} \leqslant \varepsilon^{*}[/math] по лемме [math]4[/math]), хотя бы одно из ребер [math]C_{i}[/math] обладает неотрицательной приведенной стоимостью и количество ребер в [math]C_{i}[/math] не превышает [math]V[/math]. Тогда средний вес этого цикла [math]\mu(C_{i}) = \mu_{i}^{*} \geqslant -\left(1-\dfrac{1}{V}\right)\varepsilon_{i}^{*} \geqslant - \left(1-\dfrac{1}{V}\right)\varepsilon^{*}[/math], и [math]\varepsilon'^{*} \leqslant \varepsilon_{i}^{*} = -\mu_{i}^{*} \leqslant \left(1-\dfrac{1}{V}\right)\varepsilon^{*}[/math].
[math]\triangleleft[/math]


Определение:
[math]\varepsilon[/math]-фиксированным (англ. [math]\varepsilon[/math]-fixed) будем называть ребро, поток через которое неизменен для любых [math]\varepsilon[/math]-оптимальных потоков в сети.


Теорема:
Пусть поток [math]f[/math] является [math]\varepsilon[/math]-оптимальным с функцией потенциалов [math]\varphi[/math]. Также пусть для некоторого ребра [math]uv \; \left|p_{\varphi}(uv)\right| \geqslant 2V\varepsilon[/math]. Тогда ребро [math]uv[/math] [math]\varepsilon[/math]-фиксировано.
Доказательство:
[math]\triangleright[/math]
По свойству антисимметричности, достаточно будет доказать теорему для случая [math]p_{\varphi}(uv) \geqslant 2V\varepsilon[/math].
Рассмотрим такой поток [math]f'[/math], что [math]f'(uv) \neq f(uv)[/math]. Поскольку [math]p_{\varphi}(uv) \geqslant 2V\varepsilon \gt \varepsilon[/math], поток по ребру [math]uv[/math] должен быть как можно меньше, то есть [math]f(uv) = -c(uv)[/math], и тогда раз [math]f'(uv) \neq f(uv)[/math], то [math]f'(uv) \gt f(uv)[/math].
Покажем теперь, что [math]f'[/math] не [math]\varepsilon[/math]-оптимальный.
Обозначим за [math]G_{\gt }[/math] подграф [math]G[/math] такой, что [math]G_{\gt }=(V, \{uv \in E \;|\; f'(uv) \gt f(uv) \})[/math]. Рассмотрим некоторое ребро [math]uv[/math] в [math]G_{\gt }[/math]. Поскольку [math]f[/math] и [math]f'[/math] являются циркуляциями, в [math]G_{\gt }[/math] должен содержаться простой цикл [math]C[/math], проходящий через [math]uv[/math]. Поскольку все ребра в [math]C[/math] — остаточные, стоимость [math]C[/math] не меньше [math]p_{\varphi}(uv) - (\texttt{len}(C)-1)\varepsilon \geqslant 2V\varepsilon - (V-1)\varepsilon \gt V\varepsilon[/math].
Теперь рассмотрим цикл [math]\overline{C}[/math], который получен из [math]C[/math] разворотом всех его ребер. Заметим, что [math]\overline{C}[/math] является циклом в [math]G_{\lt }=(V,\{uv \in E \;|\; f'(uv) \lt f(uv)\})[/math] и, соответственно, циклом в [math]G_{f}[/math]. По свойству антисимметричности, стоимость [math]\overline{C}[/math] меньше, чем [math]-V\varepsilon[/math] и, таким образом, [math]\mu(\overline{C}) \lt -\varepsilon[/math]. Откуда по лемме [math]3[/math] имеем, что [math]f'[/math] не [math]\varepsilon[/math]-оптимален.
[math]\triangleleft[/math]
Лемма (доказательство оценки времени работы алгоритма в случае вещественных стоимостей):
Пусть [math]k=VE(\lceil \log V + 1 \rceil)[/math]. Разобьем работу алгоритма на группы по [math]k[/math] последовательных итераций. Утверждается, что каждая группа фиксирует поток на независимом ребре [math]uv[/math], то есть итерации из другой группы не меняют величину [math]f(uv)[/math].
Доказательство:
[math]\triangleright[/math]
Оценка времени работы следует непосредственно из этого утверждения.
Чтобы доказать его, рассмотрим некоторую группу итераций. Пусть [math]f[/math] — поток до первой итерации, а [math]f'[/math] — после последней итерации этой группы. Обозначим за [math]\varepsilon'^{*}[/math] минимальное [math]\varepsilon[/math] такое, что поток [math]f'[/math] [math]\varepsilon[/math]-оптимальный, а за [math]\varphi'[/math] — функцию потенциалов такую, что [math]f'[/math] удовлетворяет свойству [math]\varepsilon'^{*}[/math]-оптимальности. Выбор [math]k[/math] и лемма [math]5[/math] дают нам следующее неравенство: [math]\varepsilon'^{*} \leqslant \varepsilon^{*} \left(1-\dfrac{1}{V} \right)^{V(\log V + 1)} \leqslant \dfrac{\varepsilon^{*}}{2V}[/math].
Рассмотрим цикл [math]C[/math], отмененный на первой итерации рассматриваемой группы. Поскольку средний вес цикла [math]C[/math] равен [math]-\varepsilon^{*}[/math] (см. лемму [math]3[/math]), некоторое ребро [math]uv[/math] цикла [math]C[/math] должно иметь приведенную стоимость [math]p_{\varphi'}(uv) \leqslant -\varepsilon^{*} \leqslant -2V\varepsilon'^{*}[/math]. Таким образом, поток на ребре [math]uv[/math] не изменится при итерациях, происходящих после этой группы. Таким образом, по теореме каждая группа фиксирует поток на независимом ребре.
[math]\triangleleft[/math]

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

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

Устроим двоичный поиск. Установим нижнюю и верхнюю границы величины среднего веса цикла [math]l[/math] и [math]r[/math] соответственно, вычислим серединное значение [math]m[/math] и отнимем полученную величину [math]m[/math] от всех ребер сети. Если теперь в нашей сети есть отрицательный цикл (этот факт можно проверить при помощи алгоритма Форда-Беллмана), значит существует цикл с меньшим средним весом, чем [math]m[/math]. Тогда продолжим поиск среди значений в диапазоне от [math]l[/math] до [math]m[/math], иначе — от [math]m[/math] до [math]r[/math].

Тогда, если [math]C_{max}[/math] и [math]C_{min}[/math] — максимальная и минимальная возможные величины среднего веса цикла соответственно, такой алгоритм для вещественных значений весов ребер будет работать за [math]O\left(\log \dfrac{C_{max}-C_{min}}{\varepsilon} \cdot EV\right)[/math], где [math]\varepsilon[/math] — точность выбора среднего веса цикла. При этом для целочисленных значений на ребрах точность выбора величины среднего веса цикла не может превысить [math]\dfrac{1}{V}[/math], что дает нам оценку [math]O\left(\log (V(C_{max}-C_{min})) \cdot EV\right)[/math].

Псевдокод

 func findMinCycleBinarySearch(int l, int r)
     // находим среднюю величину [math]m[/math]
     m = (l + r) / 2
     // вычитаем её из веса каждого ребра в сети
     for e in edges
         e.weight -= m
     while l > r - 1
         if [math]\exists[/math]C : M(C) < 0 
             // если есть отрицательный цикл, то веса циклов находятся в диапазоне [math][l;m][/math]
             // рассмотрим этот промежуток
             findMinCycleBinarySearch (l, m)
         else
             // иначе запускаем двоичный поиск на отрезке [math][m;r][/math]
             findMinCycleBinarySearch (m, r)

Продвинутый алгоритм

Добавим к нашему графу вершину [math]s[/math] и рёбра из неё во все остальные вершины. Запустим алгоритм Форда-Беллмана и попросим его построить нам квадратную матрицу со следующим условием: [math]d[i][u][/math] — длина минимального пути от [math]s[/math] до [math]u[/math] ровно из [math]i[/math] ребер. Тогда длина оптимального цикла [math]\mu^{*}[/math] минимального среднего веса вычисляется как [math]\min\limits_{u} {\max\limits_{k} {\dfrac{d[n][u]-d[k][u]}{n-k}}}[/math].

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

Чтобы найти цикл после построения матрицы [math]d[k][u][/math], запомним, при каких [math]u[/math] и [math]k[/math] достигается оптимальное значение [math]\mu^{*}[/math], и, используя [math]d[n][u][/math], поднимемся по указателям предков. Как только мы попадем в уже посещенную вершину — мы нашли цикл минимального среднего веса.

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

Псевдокод

 func findMinCycle(Graph G)
     // вводим мнимую вершину [math]s[/math], от которой проведём рёбра нулевого веса в каждую вершину графа
     Node s
     Edge[] e
     insert(s)   
     i = 0                                      
     for u in G
         e[i].begin = s
         e[i].end = u
         e[i].weight = 0
         i++
     // строим матрицу кратчайших расстояний, запустив алгоритм Форда-Беллмана из вершины [math]s[/math]
     fordBellman(s)
     // [math]m[/math] — длина оптимального цикла
     m = [math]\min\limits_{u} {\max\limits_{k} }[/math]((d[n][u] - d[k][u]) / (n - k))

См. также

Примечания

Источники информации