Изменения

Перейти к: навигация, поиск

Алгоритм Эдмондса-Карпа

295 байт добавлено, 21:40, 15 апреля 2018
Отмена правки 64925, сделанной 93.175.2.31 (обсуждение)
== Алгоритм ==
Алгоритм Эдмондса-Карпа является реализацией метода [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Форда-Фалкерсона]], в которой в качестве дополняющего пути выбирается [[Обход в ширину |кратчайший по ребрам рёбрам путь]] в остаточной сети (длины всех ребер рёбер равны <tex>1</tex>).
=== Описание ===
== Корректность алгоритма Эдмондса-Карпа ==
На каждой итерации цикла <tex>\mathrm {while}</tex> поток в графе <tex>G</tex> увеличивается вдоль одного из кратчайших путей в <tex>G_f</tex> из истока <tex>s</tex> в сток <tex>t</tex>. Этот процесс повторяется до тех пор пока существует кратчайший <tex>s \leadsto t</tex> путь в <tex>G_f</tex>. Если в <tex>G_f</tex> не существует кратчайшего пути из <tex>s</tex> в <tex>t</tex>, значит, не существует никакого вообще никакого <tex>s \leadsto t</tex> пути в <tex>G_f</tex> следовательно по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] найденный поток <tex>f</tex> максимальный.
== Оценка быстродействия ==
|statement=Пусть для некоторой сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> выполняется алгоритм Эдмондса-Карпа, тогда общее число итераций цикла <tex>\mathrm {while}</tex> составляет <tex>O(V E)</tex>.
|proof=
Рассмотрим множество ребер рёбер <tex>(u,v)</tex> остаточной сети <tex>G_f</tex>, принадлежащих увеличивающему пути <tex>p</tex>, таких что <tex>c_f(p) = c_f(u,v)</tex>. Назовем данные ребра рёбра критическими. Покажем, что каждое из <tex>|E|</tex> ребер рёбер может становиться критическим не более, чем <tex>|V| - 1</tex> раз. Заметим, что после увеличения потока вдоль пути <tex>p</tex> все критические ребра рёбра исчезают из остаточной сети, кроме того по определению остаточной пропускной способности пути хотя бы одно ребро увеличивающего пути {{---}} критическое.
Рассмотрим две вершины <tex>u</tex> и <tex>v</tex> принадлежащие <tex>V</tex>, соединенные некоторым ребром из <tex>E</tex>. Увеличение производится вдоль кратчайших путей, поэтому если ребро <tex>(u,v)</tex> становиться критическим в первый раз, верно, что <tex>\delta_f(s,v) = \delta_f(s,u) + 1</tex>. После увеличения потока ребро <tex>(u, v)</tex> исчезает из сети. Оно не появится в другом увеличивающем пути до тех, пор пока не будет уменьшен уменьшено по обратному ребру <tex>(v, u)</tex>. Это может произойти только в том случае, если ребро <tex>(v, u)</tex> встретится на некотором увеличивающем пути. Пусть в момент перед увеличением поток в сети <tex>G</tex> составлял <tex>f'</tex>, то поскольку увеличение производиться вдоль кратчайших путей, верно: <tex>\delta'_f(s,u) = \delta'_f(s, v) + 1</tex>. Согласно [[#lemma1|лемме]] <tex>\delta_f(s,v) \leqslant \delta'_f(s,v)</tex>, откуда <tex>\delta'_f(s,u) = \delta'(s,v) + 1 \geqslant \delta_f(s,v) + 1 = \delta_f(s,u) + 2</tex>.
Итак в промежуток времени между тем, когда ребро <tex>(u,v)</tex> становится критическим в первый раз, до момента, когда оно становится критическим в следующий раз, расстояние от <tex>s</tex> до <tex>u</tex> увеличивается минимум на <tex>2</tex>. Расстояние <tex>\delta(s,u)</tex> в начальный момент времени больше либо равно <tex>0</tex>. Среди промежуточных вершин на кратчайшем пути <tex>s \leadsto u</tex> не могут находиться <tex>s</tex>, <tex>u</tex> или <tex>t</tex>. Следовательно к тому моменту, когда вершина <tex>u</tex> станет недостижимой из источника расстояние до нее не превысит <tex>|V| - 2</tex>. Получаем, что ребро <tex>(u, v)</tex> могло стать критическим не более <tex>\dfrac{(|V| -2)}{2} = \dfrac{|V|}{2} - 1</tex> раз. Поскольку в графе не более <tex>O(E)</tex> пар вершин, между которыми могут существовать ребра рёбра в остаточной сети, то общее количество критических ребер рёбер в ходе выполнения алгоритма Эдмондса-Карпа равно <tex>O(V E)</tex>.
Так как каждый увеличивающий путь содержит по крайней мере одно критическое ребро, следовательно число кратчайших путей составляет <tex>O(V E)</tex>. На каждой итерации цикла <tex>\mathrm {while}</tex> рассматривается ровно один увеличивающий путь, а поскольку в случае отсутствия такого пути выполнение цикла прерывается, то число итераций цикла <tex>\mathrm {while}</tex> также составляет <tex>O(V E)</tex>.
Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <tex>\mathrm {while}</tex> можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>.
== Пример графа , на котором алгоритм дает плохую асимптотику ==[[Файл:MaxFlowWorstCase.png|365px|thumb|right| "грибок" <br/>«Грибок». Схема построения "сложного" для алгоритма Эдмондса-Карпа графа]] Заметим также, что сущетсвует существует ''сеть "грибок"''<ref>[https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-augmenting-path-algorithms-comparison/#! Cтатья на TopCoder.com ]</ref> на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет <tex>\Omega(V E^2)</tex>. Рассмотрим этот случай более подробно. Норман Заде (англ. ''Norman Zadeh'') описал примеры, которые позволяют добиться асимптотики <tex>\Omega(V^3)</tex><ref>Norman Zadeh. Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows.</ref>. В нашем примере алгоритм выполнит <tex>\Omega(V^3)</tex> улучшений пути вне зависимости от выбора этого пути.
Разделим все вершины (за исключением <tex>s</tex> и <tex>t</tex>) на подмножества:
*<tex>S={s_1,\ldots,s_k}</tex> — множество вершин, в которые входят ребра рёбра из <tex>s</tex> с пропускной способностью <tex>k</tex>,*<tex>T={t_1,\ldots,t_k}</tex> — множество вершин, из которых исходят ребра рёбра в <tex>t</tex> с пропускной способностью <tex>k</tex>, *<tex>U={u_1,\ldots,u_{2p}}</tex> — множество вершин, достижимых из <tex>s</tex> по ребрам рёбрам с бесконечной пропускной способностью(не используя иные ребрарёбра),*<tex>V={v_1,\ldots,v_{2p}}</tex> — множество вершин, из которых можно достигнуть <tex>t</tex> по ребрам рёбрам с бесконечной пропускной способностью(не используя иные ребрарёбра).
<tex>S</tex> и <tex>T</tex> содержат <tex>k</tex> вершин, <tex>U</tex> и <tex>V</tex> содержат <tex>2p</tex> вершин. Где <tex>k</tex> и <tex>p</tex> фиксированные целые числа. Каждое ребро, выделенное жирным(см. рисунок, соединяют множества <tex>S</tex> и <tex>T</tex>), имеет единичную пропускную способность; пунктирные ребра рёбра имеют бесконечную пропускную способность; остальные ребрарёбра(в форме дуги) имеют пропускную способность <tex>k</tex>.В начале работы алгоритма путь увеличиться <tex>k^2</tex> раз по пути (<tex>s</tex>, <tex>S</tex>, <tex>T</tex>, <tex>t</tex>), длина которого равна трем. После этого остаточная сеть будет содержать обратные ребра рёбра из <tex>T</tex> в <tex>S</tex>, и алгоритм выберет еще <tex>k^2</tex> путей <tex>(s, u_1, u_2, T, S, v_2, v_1, t)</tex> длины <tex>7</tex>, затем путь <tex>(s, u_1, u_2, u_3, u_4, S, T, v_4, v_3, v_2, v_1, t)</tex> длины <tex>11</tex> и так далее.:Число вершин в нашей сети: <tex>n = 2\cdot k + 4\cdot p + 2</tex>. :Число реберрёбер: <tex> m = k^2 + 2\cdot p\cdot k + 2\cdot k + 4\cdot p</tex>.
Нетрудно заметить, что число удлиняющих путей <tex> a = k^2\cdot (p+1)</tex>.
Возьмем <tex>p</tex> равным <tex>k - 1</tex>. В этом случае <tex>n = 6 \cdot k - 2</tex> и <tex>a = k^3</tex>. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути.
 
[[Файл:InGraph.png|300px|thumb|left| Изначальный граф, нулевой поток]]
[[Файл:SecondStage.png|300px|center|thumb| Граф после <tex>k^2</tex> поисков пути(в нашем случае <tex>k^2 = 4</tex>).<br/>Рёбра из между множествами <tex>S</tex> и <tex>T</tex> полностью насыщены. Поток равен четырем]]
[[Файл:ThirdStageEdmunds karp.png|300px|thumb|left| Алгоритм нашел путь через рёбра бесконечной вместимости, совершив еще <tex>k^2 = 4</tex> шагов. Поток равен восьми]]
 
 
 
 
 
 
 
 
 
 
 
== См. также ==*[[Файл:InGraph.png|600px|thumb|left| Изначальный графОпределение сети, нулевой потокпотока]]*[[Файл:SecondStage.png|600px|center|thumb| Граф после <tex>k^2</tex> поисков пути(Обход в нашем случае <tex>k^2 = 4</tex>).<br/>Ребра из между множествами <tex>S</tex> и <tex>T</tex> полностью насыщены. Поток равен четыремширину]]*[[Файл:ThirdStageEdmunds karp.png|600px|thumb|leftАлгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину| Алгоритм нашел путь через ребра бесконечной вместимости, совершив еще <tex>k^2 = 4</tex> шагов. Поток равен восьмиФорда-Фалкерсона]]
==Примечания==
== Источники информации ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
*[https://ru.wikipedia.org/wiki/Алгоритм_Эдмондса_—_Карпа Википедия: Алоритм Алгоритм Эдмондса-Карпа]* [https://en.wikipedia.org/wiki/Edmonds–Karp_algorithm Википедия: Алоритм Алгоритм Эдмондса-Карпа (англ.)]
*[https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-augmenting-path-algorithms-comparison/#! Статья на TopCoder.com]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]
Анонимный участник

Навигация