Алгоритм Форда

Алгоритм Форда

Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети.

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0:  f(u,v)=0 для всех u,v \in V. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Содержание

Алгоритм

Неформальное описание

  1. Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
  2. В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.
  3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
    1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью c_\min.
    2. Для каждого ребра на найденном пути увеличиваем поток на c_\min, а в противоположном ему — уменьшаем на c_\min.
    3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
  4. Возвращаемся на шаг 2.

Важно, что алгоритм не конкретизирует, какой именно путь мы ищем на шаге 2 или как мы это делаем. По этой причине алгоритм гарантированно сходится только для целых пропускных способностей, но даже для них при больших значениях пропускных способностей он может работать очень долго. Если пропускные способности вещественны, алгоритм может работать бесконечно долго, не сходясь к оптимальному решению (см. пример ниже).

Если искать не любой путь, а кратчайший, получится алгоритм Эдмондса — Карпа или алгоритм Диница. Эти алгоритмы сходятся для любых вещественных весов за время O(|V||E|^2) и O(|V|^2|E|) соответственно.

Формальное описание

Дан граф G(V,E) с пропускной способностью c(u,v) и потоком f(u,v)=0 для ребер из u в v. Необходимо найти максимальный поток из источника s в сток t. На каждом шаге алгоритма действуют те же условия, что и для всех потоков:

  • \ f(u,v) \leqslant c(u,v). Поток из u в v не превосходит пропускной способности.
  • \ f(u,v) = - f(v,u).
  • \ \sum_v f(u,v) = 0 \Longleftrightarrow f_{in}(u) = f_{out}(u) для всех узлов u, кроме s и t. Поток не изменяется при прохождении через узел.

Остаточная сеть G_f(V,E_f) — сеть с пропускной способностью c_f(u,v) = c(u,v) - f(u,v) и без потока.

Вход Граф \,G с пропускной способностью \,c, источник \,s и сток \,t
Выход Максимальный поток \,f из \,s в \,t

  1. f(u,v) \leftarrow 0 для всех ребер \,(u,v)
  2. Пока есть путь \,p из \,s в \,t в \,G_f, такой что \,c_f(u,v) > 0 для всех ребер (u,v) \in p:
    1. Найти \,c_f(p) = \min\{c_f(u,v) \;|\; (u,v) \in p\}
    2. Для каждого ребра (u,v) \in p
      1. f(u,v) \leftarrow f(u,v) + c_f(p)
      2. f(v,u) \leftarrow f(v,u) - c_f(p)

Путь может быть найден, например, поиском в ширину (алгоритм Эдмондса — Карпа) или поиском в глубину в G_f(V,E_f).

Сложность

На каждом шаге алгоритм добавлет поток увеличивающего пути к уже имеющемуся потоку. Если пропускные способности всех рёбер — целые числа, легко доказать по индукции, что и потоки через все рёбра всегда будут целыми. Следовательно, на каждом шаге алгоритм увеличивает поток по крайней мере на единицу, следовательно, он сойдётся не более чем за O(f) шагов, где f — максимальный поток в графе. Можно выполнить каждый шаг за время O(E), где E — число рёбер в графе, тогда общее время работы алгоритма ограничено O(E*f).

Если величина пропускной способности хотя бы одного из рёбер — иррациональное число, то алгоритм может работать бесконечно, даже не обязательно сходясь к правильному решению. Пример дан ниже.

Пример не сходящегося алгоритма

Ford-Fulkerson forever.svg

Рассмотрим приведённую справа сеть, с источником \ s, стоком \ t, пропускными способностями рёбер \ e_1 = \ 1, \ e_2 = r=(\sqrt{5}-1)/2, \ e_3 = \ 1 и пропускной способностью всех остальных рёбер, равной целому числу M \ge 2. Константа \ r выбрана так, что \ r^2 = 1 - r. Мы используем пути из остаточного графа, приведённые в таблице, причём \ p_1 = \{ s, v_4, v_3, v_2, v_1, t \}, \ p_2 = \{ s, v_2, v_3, v_4, t \} и \ p_3 = \{ s, v_1, v_2, v_3, t \}.

Шаг Найденный путь Добавленный поток Остаточные пропускные способности
e_1 e_2 e_3
0 r^0=1 r 1
1 \{ s, v_2, v_3, t \} 1 r^0 r^1 0
2 p_1 r^1 r^2 0 r^1
3 p_2 r^1 r^2 r^1 0
4 p_1 r^2 0 r^3 r^2
5 p_3 r^2 r^2 r^3 0

Заметим, что после шага 1, как и после шага 5, остаточные способности рёбер e_1, e_2 и e_3 имеют форму r^n, r^{n+1} и 0, соответственно, для какого-то натурального n. Это значит, что мы можем использовать увеличивающие пути p_1, p_2, p_1 и p_3 бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме. Полный поток после шага 5 равен 1 + 2(r^1 + r^2). За бесконечное время полный поток сойдётся к \textstyle 1 + 2\sum_{i=1}^\infty r^i = 3 + 2r, тогда как максимальный поток равен 2M + 1. Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению.[1]

Пример

Следующий пример показывает первые шаги алгоритма Форда — Фалкерсона в транспортной сети с четырьмя узлами, источником A и стоком D. Этот пример показывает худший случай. При использовании поиска в ширину алгоритму потребуется всего лишь 2 шага.

Путь Пропускная способность Результат
Начальная транспортная сеть Ford-Fulkerson example 0.svg
A,B,C,D \min(c_f(A,B), c_f(B,C), c_f(C,D))=
\min(c(A,B)-f(A,B) ,c(B,C)-f(B,C), c(C,D)-f(C,D))=
\min(1000-0, 1-0, 1000-0)=1
Ford-Fulkerson example 1.svg
A,C,B,D \min(c_f(A,C), c_f(C,B), c_f(B,D))=
\min(c(A,C)-f(A,C), c(C,B)-f(C,B), c(B,D)-f(B,D))=
\min(1000-0, 0-(-1), 1000-0)=1
Ford-Fulkerson example 2.svg
После 1998 шагов …
Конечная сеть Ford-Fulkerson example final.svg

См. также

Ссылки

Литература

  • Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1

Примечания

  1. Zwick, Uri (21 August 1995). «The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate». Theoretical Computer Science 148 (1): 165–170. DOI:10.1016/0304-3975(95)00022-O.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "Алгоритм Форда" в других словарях:

  • Алгоритм Форда — Фалкерсона — решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством… …   Википедия

  • Алгоритм Форда–Фалкерсона — решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством… …   Википедия

  • Форда-Фалкерсона алгоритм — Алгоритм Форда Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно… …   Википедия

  • Алгоритм Беллмана — У этого термина существуют и другие значения, см. Алгоритм Форда. Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск …   Википедия

  • Форда-Фалкерсона теорема — Теорема Форда Фалкерсона теорема о максимальном потоке в графе. Звучит так: величина максимального потока равна величине минимального разреза. Достаточность: любой поток между вершинами t и s меньше или равен величине любого сечения. Пусть дан… …   Википедия

  • Алгоритм Беллмана — Форда — Алгоритм Беллмана  Форда  алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана … …   Википедия

  • Алгоритм Беллмана — Форда — Алгоритм Беллмана Форда алгоритм поиска кратчайшего пути во взвешенном графе. За время O(V × E) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана Форда допускает рёбра с… …   Википедия

  • Алгоритм Эдмондса — Карпа — Алгоритм Эдмондса  Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда  Фалкерсона и работает за время O(VE2). Впервые был опубликован в 1970 году советским… …   Википедия

  • Алгоритм Эдмондса — Алгоритм Эдмондса  Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда  Фалкерсона и работает за время . Впервые был опубликован в 1970 году советским учёным Е …   Википедия

  • Форда — Фалкерсона алгоритм — [Ford Fulkerson algo­rithm] способ решения задачи построения максимального потока в сети. (Поток в сети определяется пропускной способностью ее дуг от начальной вершины до конечной вершины.). Алгоритм Л.Форда и Д.Фалкерсона применяется, например …   Экономико-математический словарь


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»