Алгоритм отмены цикла минимального среднего веса — различия между версиями
Penguinni (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 134 промежуточные версии 9 участников) | |||
Строка 3: | Строка 3: | ||
Приведенный алгоритм основан на идее [[Поток минимальной стоимости #Метод устранения отрицательных циклов в остаточной сети|алгоритма Клейна отмены цикла отрицательного веса]]. Выбор цикла минимального среднего веса вместо случайного делает алгоритм сильно полиномиальным. | Приведенный алгоритм основан на идее [[Поток минимальной стоимости #Метод устранения отрицательных циклов в остаточной сети|алгоритма Клейна отмены цикла отрицательного веса]]. Выбор цикла минимального среднего веса вместо случайного делает алгоритм сильно полиномиальным. | ||
{{Определение | {{Определение | ||
− | |definition='''Сильно полиномиальными''' в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от <tex>V</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='''Средним весом | + | |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^{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>r</tex> соответственно, вычислим серединное значение <tex>m</tex> и отнимем полученную величину <tex>m</tex> от всех ребер сети. Если теперь в нашей сети есть отрицательный цикл (этот факт можно проверить при помощи [[Алгоритм Форда-Беллмана #Нахождение отрицательного цикла|алгоритма Форда-Беллмана]]), значит существует цикл с меньшим средним весом, чем <tex>m</tex>. Тогда продолжим поиск среди значений в диапазоне от <tex>l</tex> до <tex>m</tex>, иначе {{---}} от <tex>m</tex> до <tex>r</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>---------> | ||
+ | <!----чуть не забыла про отступы, дура тупая-----> | ||
− | + | ==См. также== | |
− | + | * [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] | |
− | + | * [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] | |
− | |||
− | |||
− | |||
− | + | ==Примечания== | |
+ | <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] | ||
− | + | [[Категория:Алгоритмы и структуры данных]] | |
+ | [[Категория:Задача о потоке минимальной стоимости]] |
Текущая версия на 19:26, 4 сентября 2022
В статье описывается один из сильно полиномиальных алгоритмов решения задачи о поиске потока минимальной стоимости.
Алгоритм
Приведенный алгоритм основан на идее алгоритма Клейна отмены цикла отрицательного веса. Выбор цикла минимального среднего веса вместо случайного делает алгоритм сильно полиномиальным.
Определение: |
Сильно полиномиальными (англ. strongly polynomial) в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от | и .
Описание
Обозначим как пропускную способность цикла при протекании в сети потока . Cтоимость цикла обозначим за , а длину (число входящих в него ребер) — за .
остаточнуюОпределение: |
Средним весом (англ. mean weight) цикла будем называть отношение его стоимости к его длине |
Данный алгоритм заключается в последовательной отмене циклов минимального среднего веса в остаточной сети посредством их насыщения. Алгоритм работает до тех пор, пока минимальный средний вес циклов не окажется положительным, что будет означать, что поток минимальной стоимости найден.
Более формально:
- Шаг . Рассмотрим некоторый поток .
- Шаг . Найдем цикл , обладающий наименьшим средним весом. Если , то — поток минимальной стоимости и алгоритм завершается.
- Шаг . Отменим цикл , пустив по нему максимально возможный поток: . Перейдем к шагу .
Сложность
Для сетей с целочисленными стоимостями на ребрах
, с вещественными — . В обоих случаях времени тратится на поиск цикла минимального среднего веса.Псевдокод
Edge[] findMin(Graph G) while f // найдём M(C) — вес минимального цикла C = c : M(c) =M(c) if M(C) 0 // Если величина M(C) положительна, то мы нашли f — поток минимальной стоимости, на этом алгоритм завершается return f else // в противном случае отменяем цикл f += c_f * f(C)
Корректность
Пусть потенциалов .
— поток минимальной стоимости. Введём на нашей сети функциюОпределение: |
Приведённой стоимостью (англ. reduced cost) ребра назовем следующую величину: | .
Иными словами, приведённая стоимость — это сколько нужно потратить денег, чтобы перевезти единицу жидкости из
в (её нужно купить в , перевезти из в и продать в ).Лемма ( | ):
Если — поток минимальной стоимости, то такое, что . |
Доказательство: |
|
Определение: |
Будем говорить, что поток | — -оптимальный (англ. -optimal), если такая, что .
Лемма ( | ):
Если стоимости целочисленны и поток — -оптимальный, где , то — поток минимальной стоимости. |
Доказательство: |
|
Обозначим за
минимальную величину среди средних весов циклов для потока , а за минимальное такое, что поток — -оптимальный.Лемма ( | ):
Если — поток не минимальной стоимости, то . |
Доказательство: |
|
Лемма ( | ):
Отмена цикла минимального среднего веса не увеличивает . |
Доказательство: |
|
Определение: |
Допустимым графом (англ. admissible graph) будем называть такой подграф остаточной сети, что он включает только ребра отрицательной приведенной стоимости. |
Лемма ( | ):
Пусть — некоторый поток, а — поток после отмен циклов минимального среднего веса. Тогда , где — минимальное такое, что поток -оптимальный. |
Доказательство: |
|
Определение: |
-фиксированным (англ. -fixed) будем называть ребро, поток через которое неизменен для любых -оптимальных потоков в сети. |
Теорема: |
Пусть поток является -оптимальным с функцией потенциалов . Также пусть для некоторого ребра . Тогда ребро -фиксировано. |
Доказательство: |
|
Лемма (доказательство оценки времени работы алгоритма в случае вещественных стоимостей): |
Пусть . Разобьем работу алгоритма на группы по последовательных итераций. Утверждается, что каждая группа фиксирует поток на независимом ребре , то есть итерации из другой группы не меняют величину . |
Доказательство: |
|
Алгоритм поиска цикла минимального среднего веса
Наивный способ
Устроим двоичный поиск. Установим нижнюю и верхнюю границы величины среднего веса цикла и соответственно, вычислим серединное значение и отнимем полученную величину от всех ребер сети. Если теперь в нашей сети есть отрицательный цикл (этот факт можно проверить при помощи алгоритма Форда-Беллмана), значит существует цикл с меньшим средним весом, чем . Тогда продолжим поиск среди значений в диапазоне от до , иначе — от до .
Тогда, если
и — максимальная и минимальная возможные величины среднего веса цикла соответственно, такой алгоритм для вещественных значений весов ребер будет работать за , где — точность выбора среднего веса цикла. При этом для целочисленных значений на ребрах точность выбора величины среднего веса цикла не может превысить , что дает нам оценку .Псевдокод
func findMinCycleBinarySearch(int l, int r) // находим среднюю величинуm = (l + r) / 2 // вычитаем её из веса каждого ребра в сети for e in edges e.weight -= m while l > r - 1 if C : M(C) < 0 // если есть отрицательный цикл, то веса циклов находятся в диапазоне // рассмотрим этот промежуток findMinCycleBinarySearch (l, m) else // иначе запускаем двоичный поиск на отрезке findMinCycleBinarySearch (m, r)
Продвинутый алгоритм
Добавим к нашему графу вершину алгоритм Форда-Беллмана и попросим его построить нам квадратную матрицу со следующим условием: — длина минимального пути от до ровно из ребер. Тогда длина оптимального цикла минимального среднего веса вычисляется как .
и рёбра из неё во все остальные вершины. ЗапустимДостаточно будет доказать это правило для
, так как для других можно просто отнять эту величину от всех ребер и получить снова случай с .Чтобы найти цикл после построения матрицы
, запомним, при каких и достигается оптимальное значение , и, используя , поднимемся по указателям предков. Как только мы попадем в уже посещенную вершину — мы нашли цикл минимального среднего веса.Этот алгоритм работает за [2].
Псевдокод
func findMinCycle(Graph G) // вводим мнимую вершину, от которой проведём рёбра нулевого веса в каждую вершину графа 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++ // строим матрицу кратчайших расстояний, запустив алгоритм Форда-Беллмана из вершины fordBellman(s) // — длина оптимального цикла m = ((d[n][u] - d[k][u]) / (n - k))
См. также
Примечания
Источники информации
- Лекция 14 | Дополнительные главы алгоритмов | Андрей Станкевич | CSC | Лекториум
- 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.)
- Lecture by M.X.Goemans on Goldberg-Tarjan Min-Cost Circulation Algorithm