Алгоритм Форда – Фулкерсона - Ford–Fulkerson algorithm

В Метод Форда – Фулкерсона или Алгоритм Форда – Фулкерсона (FFA) это жадный алгоритм который вычисляет максимальный поток в проточная сеть. Иногда его называют «методом», а не «алгоритмом», так как подход к поиску дополнительных путей в остаточном графе не полностью определен.^[1] или он указан в нескольких реализациях с разным временем работы.^[2] Он был опубликован в 1956 г. Л. Р. Форд-младший и Д. Р. Фулкерсон.^[3] Название «Форд – Фулкерсон» также часто используется для обозначения Алгоритм Эдмондса – Карпа, который является полностью определенной реализацией метода Форда – Фулкерсона.

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

Алгоритм

Позволять ${ Displaystyle G (V, E)}$ - граф, и для каждого ребра из $ты$ к $v$ , позволять ${ Displaystyle с (и, v)}$ быть вместимостью и ${ Displaystyle f (и, v)}$ быть потоком. Мы хотим найти максимальный поток от источника $s$ к раковине $т$ . После каждого шага в алгоритме сохраняется следующее:

Ограничения мощности	${ Displaystyle forall (u, v) в E: f (u, v) leq c (u, v)}$	Поток по ребру не может превышать его пропускную способность.
Косая симметрия	${ displaystyle forall (u, v) in E: f (u, v) = - f (v, u)}$	Чистый поток от $ты$ к $v$ должен быть противоположен чистому потоку из $v$ к $ты$ (см. пример).
Сохранение потока	${ displaystyle forall u in V: u neq s { text {and}} u neq t Rightarrow sum _ {w in V} f (u, w) = 0}$	Чистый поток к узлу равен нулю, за исключением источника, который «производит» поток, и стока, который «потребляет» поток.
Значение (f)	${ displaystyle sum _ {(s, u) in E} f (s, u) = sum _ {(v, t) in E} f (v, t)}$	Поток, уходящий из $s$ должен быть равен потоку, приходящему на $т$ .

Это означает, что поток через сеть юридический поток после каждого раунда в алгоритме. Мы определяем остаточная сеть ${ displaystyle G_ {f} (V, E_ {f})}$ быть сетью с пропускной способностью ${ displaystyle c_ {f} (u, v) = c (u, v) -f (u, v)}$ и никакого потока. Обратите внимание, что может случиться так, что поток из $v$ к $ты$ разрешено в остаточной сети, но запрещено в исходной сети: если ${ displaystyle f (u, v)> 0}$ и ${ displaystyle c (v, u) = 0}$ тогда ${ Displaystyle c_ {f} (v, u) = c (v, u) -f (v, u) = f (u, v)> 0}$ .

Алгоритм Форд – Фулкерсон

Входы Учитывая сеть

{ Displaystyle G = (V, E)}

с пропускной способностью

c

, исходный узел

s

, и приемный узел

т

Вывод Вычислить поток

ж

от

s

к

т

максимальной стоимости

${ displaystyle f (u, v) leftarrow 0}$ для всех краев ${ Displaystyle (и, v)}$
Пока есть путь п от s к т в ${ displaystyle G_ {f}}$ $G_ {f}$ , так что ${ displaystyle c_ {f} (u, v)> 0}$ $c_ {f} (u, v)> 0$ для всех краев ${ displaystyle (u, v) in p}$ $(и, v) in p$ :
1. найти ${ Displaystyle c_ {f} (p) = min {c_ {f} (u, v) :( u, v) in p }}$
2. Для каждого края ${ displaystyle (u, v) in p}$ $(и, v) in p$
  1. ${ displaystyle f (u, v) leftarrow f (u, v) + c_ {f} (p)}$ (Отправьте поток по пути)
  2. ${ displaystyle f (v, u) leftarrow f (v, u) -c_ {f} (p)}$ (Поток может быть "возвращен" позже)

«←» означает назначение. Например, "самый большой ← предмет"означает, что стоимость самый большой изменяет стоимость предмет.
"вернуть"завершает алгоритм и выводит следующее значение.

Путь на шаге 2 можно найти, например, с помощью поиск в ширину (BFS) или поиск в глубину в ${ displaystyle G_ {f} (V, E_ {f})}$ . Если вы используете первое, алгоритм называется Эдмондс-Карп.

Когда больше нет путей на шаге 2, $s$ не сможет добраться $т$ в остаточной сети. Если $S$ это набор узлов, достижимых $s$ в остаточной сети, то общая емкость в исходной сети ребер из $S$ к остатку $V$ с одной стороны, равна общему потоку, который мы нашли из $s$ к $т$ , а с другой стороны, служит верхней границей для всех таких потоков, что доказывает, что найденный поток максимален. Смотрите также Теорема о максимальном расходе и минимальном разрезе.

Если график ${ Displaystyle G (V, E)}$ имеет несколько источников и приемников, мы действуем следующим образом: Предположим, что ${ displaystyle T = {t mid t { text {это раковина}} }}$ и ${ displaystyle S = {s mid s { text {является источником}} }}$ . Добавить новый источник ${ displaystyle s ^ {*}}$ с краю ${ displaystyle (s ^ {*}, s)}$ от ${ displaystyle s ^ {*}}$ к каждому узлу ${ displaystyle s in S}$ , с емкостью ${ Displaystyle с (s ^ {*}, s) = d_ {s} ; (d_ {s} = sum _ {(s, u) in E} c (s, u))}$ . И добавить новую раковину ${ Displaystyle т ^ {*}}$ с краю ${ Displaystyle (т, т ^ {*})}$ из каждого узла ${ displaystyle t in T}$ к ${ Displaystyle т ^ {*}}$ , с емкостью ${ displaystyle c (t, t ^ {*}) = d_ {t} ; (d_ {t} = sum _ {(v, t) in E} c (v, t))}$ . Затем примените алгоритм Форда – Фулкерсона.

Также, если узел $ты$ имеет ограничение мощности ${ displaystyle d_ {u}}$ , мы заменяем этот узел двумя узлами ${ displaystyle u _ { mathrm {in}}, u _ { mathrm {out}}}$ , и край ${ Displaystyle (и _ { mathrm {in}}, и _ { mathrm {out}})}$ , с емкостью ${ displaystyle c (u _ { mathrm {in}}, u _ { mathrm {out}}) = d_ {u}}$ . Затем примените алгоритм Форда – Фулкерсона.

Сложность

Путем добавления пути увеличения потока к потоку, уже установленному на графике, максимальный поток будет достигнут, когда на графике больше не будет путей увеличения потока. Однако нет уверенности в том, что эта ситуация когда-либо будет достигнута, поэтому лучшее, что можно гарантировать, - это то, что ответ будет правильным, если алгоритм завершится. В случае, если алгоритм работает вечно, поток может даже не сходиться к максимальному потоку. Однако такая ситуация возникает только при иррациональных значениях расхода.^{[нужна цитата ]} Когда емкости являются целыми числами, время выполнения Форда – Фулкерсона ограничено ${ displaystyle O (Ef)}$ (увидеть нотация большой O ), где ${ displaystyle E}$ - количество ребер в графе и ${ displaystyle f}$ - максимальный поток на графике. Это потому, что каждый путь увеличения можно найти в ${ displaystyle O (E)}$ времени и увеличивает поток на целое число не менее ${ displaystyle 1}$ , с верхней границей ${ displaystyle f}$ .

Вариантом алгоритма Форда – Фулкерсона с гарантированным завершением и временем выполнения, не зависящим от максимального значения потока, является алгоритм Алгоритм Эдмондса – Карпа, который работает в ${ displaystyle O (VE ^ {2})}$ время.

Интегральный пример

В следующем примере показаны первые шаги Форда – Фулкерсона в потоковой сети с 4 узлами, источник ${ displaystyle A}$ и тонуть ${ displaystyle D}$ . Этот пример показывает наихудшее поведение алгоритма. На каждом этапе только поток ${ displaystyle 1}$ отправляется по сети. Если бы вместо этого использовался поиск в ширину, потребовалось бы всего два шага.

Дорожка	Вместимость	Результирующая поточная сеть
Сеть начального потока
${ displaystyle A, B, C, D}$	${ Displaystyle { begin {align} & 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 конец {выровнено}}}$
${ displaystyle A, C, B, D}$	${ Displaystyle { begin {align} & 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 конец {выровнено}}}$
После 1998 года больше шагов ...
Сеть конечного потока

Обратите внимание, как поток "отталкивается" от ${ displaystyle C}$ к ${ displaystyle B}$ при поиске пути ${ displaystyle A, C, B, D}$ .

Пример без завершения

Рассмотрим проточную сеть, показанную справа, с источником ${ displaystyle s}$ , тонуть ${ displaystyle t}$ , емкости кромок ${ displaystyle e_ {1}}$ , ${ displaystyle e_ {2}}$ и ${ displaystyle e_ {3}}$ соответственно ${ displaystyle 1}$ , ${ displaystyle r = ({ sqrt {5}} - 1) / 2}$ и ${ displaystyle 1}$ а мощность всех остальных ребер некоторое целое число ${ displaystyle M geq 2}$ . Постоянная ${ displaystyle r}$ было выбрано так, что ${ displaystyle r ^ {2} = 1-r}$ . Мы используем дополнительные пути в соответствии со следующей таблицей, где ${ displaystyle p_ {1} = {s, v_ {4}, v_ {3}, v_ {2}, v_ {1}, t }}$ , ${ displaystyle p_ {2} = {s, v_ {2}, v_ {3}, v_ {4}, t }}$ и ${ displaystyle p_ {3} = {s, v_ {1}, v_ {2}, v_ {3}, t }}$ .

Шаг	Расширение пути	Отправленный поток	Остаточные мощности
Шаг	Расширение пути	Отправленный поток	${ displaystyle e_ {1}}$	${ displaystyle e_ {2}}$	${ displaystyle e_ {3}}$
0			${ displaystyle r ^ {0} = 1}$	${ displaystyle r}$	${ displaystyle 1}$
1	${ displaystyle {s, v_ {2}, v_ {3}, t }}$	${ displaystyle 1}$	${ displaystyle r ^ {0}}$	${ displaystyle r ^ {1}}$	${ displaystyle 0}$
2	${ displaystyle p_ {1}}$	${ displaystyle r ^ {1}}$	${ displaystyle r ^ {2}}$	${ displaystyle 0}$	${ displaystyle r ^ {1}}$
3	${ displaystyle p_ {2}}$	${ displaystyle r ^ {1}}$	${ displaystyle r ^ {2}}$	${ displaystyle r ^ {1}}$	${ displaystyle 0}$
4	${ displaystyle p_ {1}}$	${ displaystyle r ^ {2}}$	${ displaystyle 0}$	${ displaystyle r ^ {3}}$	${ displaystyle r ^ {2}}$
5	${ displaystyle p_ {3}}$	${ displaystyle r ^ {2}}$	${ displaystyle r ^ {2}}$	${ displaystyle r ^ {3}}$	${ displaystyle 0}$

Обратите внимание, что после шага 1, а также после шага 5 остаточные мощности ребер ${ displaystyle e_ {1}}$ , ${ displaystyle e_ {2}}$ и ${ displaystyle e_ {3}}$ находятся в форме ${ Displaystyle г ^ {п}}$ , ${ Displaystyle г ^ {п + 1}}$ и ${ displaystyle 0}$ соответственно для некоторых ${ Displaystyle п в mathbb {N}}$ . Это означает, что мы можем использовать дополнительные пути ${ displaystyle p_ {1}}$ , ${ displaystyle p_ {2}}$ , ${ displaystyle p_ {1}}$ и ${ displaystyle p_ {3}}$ бесконечно много раз, и остаточные емкости этих ребер всегда будут в одном и том же виде. Общий поток в сети после шага 5 составляет ${ Displaystyle 1 + 2 (г ^ {1} + г ^ {2})}$ . Если мы продолжим использовать дополнительные пути, как указано выше, общий поток сходится к ${ Displaystyle textstyle 1 + 2 сумма _ {я = 1} ^ { infty} г ^ {я} = 3 + 2r}$ . Однако обратите внимание, что существует поток стоимости ${ displaystyle 2M + 1}$ , отправив ${ displaystyle M}$ единиц потока по ${ displaystyle sv_ {1} t}$ , 1 ед. Потока по ${ displaystyle sv_ {2} v_ {3} t}$ , и ${ displaystyle M}$ единиц потока по ${ displaystyle sv_ {4} t}$ . Следовательно, алгоритм никогда не завершается, и поток даже не сходится к максимальному потоку.^[4]

Другой пример без завершения, основанный на Евклидов алгоритм дан кем-то Бакман и Хюин (2018), где они также показывают, что в худшем случае время работы алгоритма Форда-Фулкерсона в сети ${ Displaystyle G (V, E)}$ в порядковые номера является ${ Displaystyle omega ^ { Theta (| E |)}}$ .

Реализация Python Эдмондс-Карп алгоритм

импорт коллекциикласс График:    "" "Этот класс представляет ориентированный граф, использующий представление матрицы смежности." ""    def __в этом__(я, график):        я.график = график  # остаточный график        я.ряд = len(график)    def бойфренды(я, s, т, родитель):        "" "Возвращает истину, если существует путь от источника 's' к 't' в        остаточный граф. Также заполняет parent [] для хранения пути. "" "        # Пометить все вершины как непосещенные        посетил = [Ложь] * я.ряд        # Создаем очередь для BFS        очередь = коллекции.дек()        # Отметить исходный узел как посещенный и поставить его в очередь        очередь.добавить(s)        посетил[s] = Правда        # Стандартный цикл BFS        в то время как очередь:            ты = очередь.поплефт()            # Получить все смежные вершины исключенной из очереди вершины u            # Если соседний еще не был посещен, отметьте его            # посетил и поставил в очередь            для инд, вал в перечислять(я.график[ты]):                если (посетил[инд] == Ложь) и (вал > 0):                    очередь.добавить(инд)                    посетил[инд] = Правда                    родитель[инд] = ты        # Если мы достигли стока в BFS, начиная с источника, то возвращаем        # истина, иначе ложь        вернуть посетил[т]    # Возвращает максимальный поток от s до t в заданном графике    def edmonds_karp(я, источник, тонуть):        # Этот массив заполняется BFS и хранит путь        родитель = [-1] * я.ряд        max_flow = 0  # Изначально нет потока        # Увеличиваем поток, пока есть путь от источника до стока        в то время как я.бойфренды(источник, тонуть, родитель):            # Найти минимальную остаточную пропускную способность ребер вдоль            # путь заполнен BFS. Или мы можем сказать, найти максимальный поток            # по найденному пути.            path_flow = плавать(«Инф»)            s = тонуть            в то время как s != источник:                path_flow = мин(path_flow, я.график[родитель[s]][s])                s = родитель[s]            # Добавить поток пути к общему потоку            max_flow += path_flow            # обновить остаточные мощности кромок и обратных кромок            # по пути            v = тонуть            в то время как v != источник:                ты = родитель[v]                я.график[ты][v] -= path_flow                я.график[v][ты] += path_flow                v = родитель[v]        вернуть max_flow

Смотрите также

Заметки

^ Лаунг-Тернг Ван, Яо-Вэнь Чанг, Кван-Тинг (Тим) Ченг (2009). Автоматизация электронного проектирования: синтез, проверка и тестирование. Морган Кауфманн. стр.204. ISBN 0080922007.CS1 maint: несколько имен: список авторов (ссылка на сайт)
^ Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест; Клиффорд Штайн (2009). Введение в алгоритмы. MIT Press. стр.714. ISBN 0262258102.
^ Форд, Л. Р.; Фулкерсон, Д. (1956). «Максимальный поток через сеть» (PDF). Канадский математический журнал. 8: 399–404. Дои:10.4153 / CJM-1956-045-5.
^ Цвик, Ури (21 августа 1995 г.). «Наименьшие сети, в которых процедура максимального потока Форда – Фулкерсона может не завершиться». Теоретическая информатика. 148 (1): 165–170. Дои:10.1016 / 0304-3975 (95) 00022-О.

использованная литература

Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001). «Раздел 26.2: Метод Форда – Фулкерсона». Введение в алгоритмы (Второе изд.). MIT Press и McGraw – Hill. С. 651–664. ISBN 0-262-03293-7.
Джордж Т. Хейнеман; Гэри Поллис; Стэнли Селкоу (2008). «Глава 8: Алгоритмы сетевого потока». Об алгоритмах в двух словах. Oreilly Media. С. 226–250. ISBN 978-0-596-51624-6.
Джон Кляйнберг; Эва Тардос (2006). «Глава 7: Расширение проблемы максимального потока». Разработка алгоритма. Pearson Education. стр.378–384. ISBN 0-321-29535-8.
Самуэль Гутекунст (2009). ENGRI 1101. Корнелл Университет.
Бэкман, Спенсер; Хьюнь, Тони (2018). «Трансфинитный Форд – Фулкерсон на конечной сети». Вычислимость. 7 (4): 341–347. arXiv:1504.04363. Дои:10.3233 / COM-180082.

внешние ссылки

СМИ, связанные с Алгоритм Форда-Фулкерсона в Wikimedia Commons

[1] Лаунг-Тернг Ван, Яо-Вэнь Чанг, Кван-Тинг (Тим) Ченг (2009). Автоматизация электронного проектирования: синтез, проверка и тестирование. Морган Кауфманн. стр.204. ISBN 0080922007.CS1 maint: несколько имен: список авторов (ссылка на сайт)

[2] Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест; Клиффорд Штайн (2009). Введение в алгоритмы. MIT Press. стр.714. ISBN 0262258102.

[3] Форд, Л. Р.; Фулкерсон, Д. (1956). «Максимальный поток через сеть» (PDF). Канадский математический журнал. 8: 399–404. Дои:10.4153 / CJM-1956-045-5.

[4] Цвик, Ури (21 августа 1995 г.). «Наименьшие сети, в которых процедура максимального потока Форда – Фулкерсона может не завершиться». Теоретическая информатика. 148 (1): 165–170. Дои:10.1016 / 0304-3975 (95) 00022-О.

[1]

[2]

[3]

[4]