Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 44 промежуточные версии 10 участников) | |||
Строка 1: | Строка 1: | ||
− | Алгоритм Форда | + | '''Алгоритм Форда-Фалкерсона''' — алгоритм, решающий задачу нахождения максимального [[Определение сети, потока #Определение потока | потока]] в транспортной сети. |
== Идея == | == Идея == | ||
− | Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: <tex> f(u,v) = 0 </tex> для всех <tex> u, v </tex> из <tex> V </tex>. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать | + | Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение <tex>0</tex>: <tex> f(u,v) = 0 </tex> для всех <tex> u, v </tex> из <tex> V </tex>. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника <tex>s</tex> к стоку <tex>t</tex>, вдоль которого можно послать ненулевой поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощью [[Обход в глубину, цвета вершин|обхода в глубину (dfs)]]. Процесс повторяется, пока можно найти увеличивающий путь. |
== Реализация == | == Реализация == | ||
− | dfs(u, Cmin) { | + | '''int''' dfs('''int''' u, '''int''' Cmin): <span style="color:Green">// Cmin {{---}} пропускная способность в текущем подпотоке</span> |
− | if | + | '''if''' u = t |
− | return Cmin | + | '''return''' Cmin |
− | u | + | visited[u] = ''true'' |
− | for ( | + | '''for''' v '''in''' u.children |
− | if | + | '''auto''' uv = edge(u, v) |
− | + | '''if''' '''not''' visited[v] '''and''' uv.f < uv.c | |
− | if | + | '''int''' delta = dfs(v, min(Cmin, uv.c - uv.f)) |
− | uv.f += | + | '''if''' delta > 0 |
− | uv.backEdge.f -= | + | uv.f += delta |
− | return | + | uv.backEdge.f -= delta |
− | + | '''return''' delta | |
− | + | '''return''' 0 | |
== Оценка производительности == | == Оценка производительности == | ||
− | Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено <tex>O(E | + | Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено <tex>O(|E|f)</tex>, где <tex>E</tex> — число рёбер в графе, <tex>f</tex> — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за <tex>O(E)</tex> и увеличивает поток как минимум на <tex>1</tex>. |
=== Пример несходящегося алгоритма === | === Пример несходящегося алгоритма === | ||
− | [[Файл:F-f.5.png|thumb|right| | + | [[Файл:F-f.5.png|300px|thumb|right|Рис. 1]] |
− | Рассмотрим приведённую справа сеть | + | Рассмотрим приведённую справа сеть с источником <tex>\ s</tex>, стоком <tex>\ t</tex>, пропускными способностями рёбер <tex>\ e_1</tex>, <tex>\ e_2</tex> и <tex>\ e_3</tex> соответственно <tex>\ 1</tex>, <tex>r=\dfrac{\sqrt{5}-1}{2}</tex> и <tex>\ 1</tex> и пропускной способностью всех остальных рёбер, равной целому числу <tex>M \geqslant 2</tex>. Константа <tex>\ r</tex> выбрана так, что <tex>\ r^2 = 1 - r</tex>. Мы используем пути из остаточного графа, приведённые в таблице, причём <tex>\ p_1 = \{ s, v_4, v_3, v_2, v_1, t \}</tex>, <tex>\ p_2 = \{ s, v_2, v_3, v_4, t \}</tex> и <tex>\ p_3 = \{ s, v_1, v_2, v_3, t \}</tex>. |
{| class="wikitable" style="text-align: center" | {| class="wikitable" style="text-align: center" | ||
− | ! rowspan=2 | Шаг !! rowspan=2 | Найденный путь !! rowspan=2 | Добавленный поток !! colspan=3 | Остаточные пропускные способности | + | ! valign="top" rowspan=2 | Шаг !! valign="top" rowspan=2 | Найденный путь !! valign="top" rowspan=2 | Добавленный поток !! colspan=3 | Остаточные пропускные способности |
|- | |- | ||
− | ! < | + | ! <tex>e_1</tex> !! <tex>e_2</tex> !! <tex>e_3</tex> |
|- | |- | ||
− | | 0 || || || < | + | | <tex>0</tex> || <tex>-</tex> || <tex>-</tex> || <tex>r^0=1</tex> || <tex>r</tex> || <tex>1</tex> |
|- | |- | ||
− | | 1 || < | + | | <tex>1</tex> || <tex>\{ s, v_2, v_3, t \}</tex> || <tex>1</tex> || <tex>r^0</tex> || <tex>r^1</tex> || <tex>0</tex> |
|- | |- | ||
− | | 2 || < | + | | <tex>2</tex> || <tex>p_1</tex> || <tex>r^1</tex> || <tex>r^2</tex> || <tex>0</tex> || <tex>r^1</tex> |
|- | |- | ||
− | | 3 || < | + | | <tex>3</tex> || <tex>p_2</tex> || <tex>r^1</tex> || <tex>r^2</tex> || <tex>r^1</tex> || <tex>0</tex> |
|- | |- | ||
− | | 4 || < | + | | <tex>4</tex> || <tex>p_1</tex> || <tex>r^2</tex> || <tex>0</tex> || <tex>r^3</tex> || <tex>r^2</tex> |
|- | |- | ||
− | | 5 || < | + | | <tex>5</tex> || <tex>p_3</tex> || <tex>r^2</tex> || <tex>r^2</tex> || <tex>r^3</tex> || <tex>0</tex> |
|} | |} | ||
− | Заметим, что после шага 1, как и после шага 5, остаточные способности рёбер < | + | Заметим, что после шага <tex>1</tex>, как и после шага <tex>5</tex>, остаточные способности рёбер <tex>e_1</tex>, <tex>e_2</tex> и <tex>e_3</tex> имеют форму <tex>r^n</tex>, <tex>r^{n+1}</tex> и <tex>0</tex>, соответственно, для какого-то натурального <tex>n</tex>. Это значит, что мы можем использовать увеличивающие пути <tex>p_1</tex>, <tex>p_2</tex>, <tex>p_1</tex> и <tex>p_3</tex> бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме. Полный поток после шага <tex>5</tex> равен <tex>1 + 2(r^1 + r^2)</tex>. За бесконечное время полный поток сойдётся к <tex>\textstyle 1 + 2\sum\limits_{i=1}^\infty r^i = 3 + 2r</tex>, тогда как максимальный поток равен <tex>2M + 1</tex>. Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению. |
=== Пример медленной работы алгоритма Форда-Фалкерсона с использованием поиска в глубину по сравнению с реализацией, использующей поиск в ширину === | === Пример медленной работы алгоритма Форда-Фалкерсона с использованием поиска в глубину по сравнению с реализацией, использующей поиск в ширину === | ||
− | При использовании поиска в ширину алгоритму потребуется всего лишь | + | При использовании поиска в ширину алгоритму потребуется всего лишь два шага. |
− | Дана сеть ( | + | Дана сеть (Рис. 2). |
− | [[Файл:F-f.1.png|thumb|center| | + | [[Файл:F-f.1.png|thumb|300px|center|Рис. 2]] |
− | Благодаря двум итерациям ( | + | Благодаря двум итерациям (Рис. 3 и Рис. 4) |
− | [[Файл:F-f.2.png|thumb|center| | + | [[Файл:F-f.2.png|thumb|300px|center|Рис. 3]] |
− | [[Файл:F-f.3.png|thumb|center| | + | [[Файл:F-f.3.png|thumb|300px|center|Рис. 4]] |
− | рёбра <tex>AB, AC, BD, CD</tex> насытились лишь на 1. | + | рёбра <tex>AB, AC, BD, CD</tex> насытились лишь на <tex>1</tex>. |
− | Конечная сеть будет получена ещё через 1998 итераций ( | + | Конечная сеть будет получена ещё через 1998 итераций (Рис. 5). |
− | [[Файл:F-f.4.png|thumb|center| | + | [[Файл:F-f.4.png|thumb|300px|center|Рис. 5]] |
== См. также == | == См. также == | ||
* [[Теорема Форда-Фалкерсона]] | * [[Теорема Форда-Фалкерсона]] | ||
+ | * [[Алгоритм Эдмондса-Карпа]] | ||
− | == | + | == Источники информации == |
− | Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1 | + | * [http://ru.wikipedia.org/wiki/Алгоритм_Форда_—_Фалкерсона Википедия: Алгоритм Форда — Фалкерсона] <br> |
+ | * Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1 | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Задача о максимальном потоке ]] | [[Категория: Задача о максимальном потоке ]] |
Текущая версия на 19:35, 4 сентября 2022
Алгоритм Форда-Фалкерсона — алгоритм, решающий задачу нахождения максимального потока в транспортной сети.
Содержание
Идея
Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение обхода в глубину (dfs). Процесс повторяется, пока можно найти увеличивающий путь.
: для всех из . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника к стоку , вдоль которого можно послать ненулевой поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощьюРеализация
int dfs(int u, int Cmin): // Cmin — пропускная способность в текущем подпотоке
if u = t
return Cmin
visited[u] = true
for v in u.children
auto uv = edge(u, v)
if not visited[v] and uv.f < uv.c
int delta = dfs(v, min(Cmin, uv.c - uv.f))
if delta > 0
uv.f += delta
uv.backEdge.f -= delta
return delta
return 0
Оценка производительности
Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено
, где — число рёбер в графе, — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за и увеличивает поток как минимум на .
Пример несходящегося алгоритма
Рассмотрим приведённую справа сеть с источником
, стоком , пропускными способностями рёбер , и соответственно , и и пропускной способностью всех остальных рёбер, равной целому числу . Константа выбрана так, что . Мы используем пути из остаточного графа, приведённые в таблице, причём , и .Шаг | Найденный путь | Добавленный поток | Остаточные пропускные способности | ||
---|---|---|---|---|---|
Заметим, что после шага
, как и после шага , остаточные способности рёбер , и имеют форму , и , соответственно, для какого-то натурального . Это значит, что мы можем использовать увеличивающие пути , , и бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме. Полный поток после шага равен . За бесконечное время полный поток сойдётся к , тогда как максимальный поток равен . Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению.Пример медленной работы алгоритма Форда-Фалкерсона с использованием поиска в глубину по сравнению с реализацией, использующей поиск в ширину
При использовании поиска в ширину алгоритму потребуется всего лишь два шага. Дана сеть (Рис. 2).
Благодаря двум итерациям (Рис. 3 и Рис. 4)
рёбра
насытились лишь на . Конечная сеть будет получена ещё через 1998 итераций (Рис. 5).См. также
Источники информации
- Википедия: Алгоритм Форда — Фалкерсона
- Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1