1632
правки
Изменения
м
Такой Тогда, если <tex>C_{max}</tex> и <tex>C_{min}</tex> {{---}} максимальная и минимальная возможные величины среднего веса цикла соответственно, такой алгоритм для вещественных значений весов ребер будет работать за <tex>O\left(\texttt{log} \dfrac{1C_{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)
rollbackEdits.php mass rollback
{{Определение
|definition='''Средним весом''' (англ. ''mean weight'') цикла будем называть отношение его стоимости к его длине <tex>\mu (C)=\dfrac{p(C)}{\texttt{len}(C)}</tex>}}
Данный алгоритм заключается в последовательной отмене циклов минимального среднего веса в [[Дополняющая сеть, дополняющий путь|остаточной сети]] посредством их насыщения. Алгоритм работает до тех пор, пока минимальный средний вес циклов не окажется положительным, что будет означать, что поток минимальной стоимости найден. Более формально:* '''Шаг <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\log{CV})</tex>, с вещественными {{---}} <tex>O(VE\cdot VE^{2}\log{V})</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>-фиксированным''' (англ. ''reduced cost<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'(uuv) + p< f(uv) \})</tex> и, соответственно, циклом в <tex>G_{f}</tex>. По свойству антисимметричности, стоимость <tex>\overline{C}</tex> меньше, чем <tex>- V\varphivarepsilon</tex> и, таким образом, <tex>\mu(v\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>O(VE\cdot VEvarepsilon'^{*}</tex>-оптимальности. Выбор <tex>k</tex> и [[#lemma5|лемма <tex>5</tex>]] дают нам следующее неравенство: <tex>\varepsilon'^{*} \leqslant \varepsilon^{2*}\logleft(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>Op_{\varphi'}(VEuv)\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>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>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>---------> <!----чуть не забыла про отступы, дура тупая----->
==См. также==
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
==Примечания==
<references/>
==Источники информации==
* [https://youtu.be/bykbw7HovSo?t=4287 Лекция 14 | Дополнительные главы алгоритмов | Андрей Станкевич | CSC | Лекториум]
* [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]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Задача о потоке минимальной стоимости]]
