|
Алгоритм Форда–ФалкерсонаАлгоритм Форда–Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь. Неформальное описание:
Важно, что алгоритм не конкретизирует, какой именно путь мы ищем на шаге 2 или как мы это делаем. По этой причине алгоритм гарантированно сходится только для целых пропускных способностей, но даже для них при больших значениях пропускных способностей он может работать очень долго. Если пропускные способности вещественны, алгоритм может работать бесконечно долго, не сходясь к оптимальному решению (см. пример ниже). Если искать не любой путь, а кратчайший, получится алгоритм Эдмондса-Карпа или алгоритм Диница. Эти алгоритмы сходятся для любых вещественных весов за время O( | V | | E | 2) и O( | V |2 | E | ) соответственно. Дан граф G(V,E) с пропускной способностью c(u,v) и потоком f(u,v) = 0 для ребер из u в v. Необходимо найти максимальный поток из источника s в сток t. На каждом шаге алгоритма действуют те же условия, что и для всех потоков:
Остаточная сеть Gf(V,Ef) — сеть с пропускной способностью cf(u,v) = c(u,v) − f(u,v) и без потока.
Вход Граф с
пропускной способностью ,
источник и
сток
Путь может быть найден, например, поиском в ширину (алгоритм Эдмондса-Карпа) или поиском в глубину в Gf(V,Ef). Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено O(E*f), где E — число рёбер в графе, f — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за O(E) и увеличивает поток как минимум на 1. Рассмотрим приведённую справа сеть, с источником , стоком , пропускными способностями рёбер , и соответственно , и и пропускной способностью всех остальных рёбер, равной целому числу . Константа выбрана так, что . Мы используем пути из остаточного графа, приведённые в таблице, причём , и .
Заметим, что после шага 1, как и после шага 5, остаточные способности рёбер e1, e2 и e3 имеют форму rn, rn + 1 и 0, соответственно, для какого-то натурального n. Это значит, что мы можем использовать увеличивающие пути p1, p2, p1 и p3 бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме.Полный поток после шага 5 равен 1 + 2(r1 + r2). За бесконечное время полный поток сойдётся к , тогда как максимальный поток равен 2M + 1. Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению. Следующий пример показывает первые шаги алгоритма Форда–Фалкерсона в транспортной сети с четырьмя узлами, источником A и стоком D. Этот пример показывает худший случай. При использовании поиска в ширину алгоритму потребуется всего лишь 2 шага.
Лит.: Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1. |
Loading
|