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

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

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

Алгоритм

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

Ограничения мощности	${\displaystyle \forall (u,v)\in 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 к т максимальной стоимости

1. ${\displaystyle f(u,v)\leftarrow 0}$ для всех краев ${\displaystyle (u,v)}$
2. Пока есть путь п от s к т в ${\displaystyle G_{f}}$, так что ${\displaystyle c_{f}(u,v)>0}$ для всех краев ${\displaystyle (u,v)\in p}$:
   1. найти ${\displaystyle c_{f}(p)=\min\{c_{f}(u,v):(u,v)\in p\}}$
   2. Для каждого края ${\displaystyle (u,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{ is a sink}}\}}$ и ${\displaystyle S=\{s\mid s{\text{ is a source}}\}}$. Добавить новый источник ${\displaystyle s^{*}}$ с краю ${\displaystyle (s^{*},s)}$ от ${\displaystyle s^{*}}$ к каждому узлу ${\displaystyle s\in S}$, с емкостью ${\displaystyle c(s^{*},s)=d_{s}\;(d_{s}=\sum _{(s,u)\in E}c(s,u))}$. И добавить новую раковину ${\displaystyle t^{*}}$ с краю ${\displaystyle (t,t^{*})}$ из каждого узла ${\displaystyle t\in T}$ к ${\displaystyle t^{*}}$, с емкостью ${\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 (u_{\mathrm {in} },u_{\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{aligned}&\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\end{aligned}}}$
${\displaystyle A,C,B,D}$	${\displaystyle {\begin{aligned}&\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\end{aligned}}}$
После 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 r^{n}}$, ${\displaystyle r^{n+1}}$ и ${\displaystyle 0}$соответственно для некоторых ${\displaystyle n\in \mathbb {N} }$. Это означает, что мы можем использовать дополнительные пути ${\displaystyle p_{1}}$, ${\displaystyle p_{2}}$, ${\displaystyle p_{1}}$ и ${\displaystyle p_{3}}$ бесконечно много раз, и остаточные емкости этих ребер всегда будут в одном и том же виде. Общий поток в сети после шага 5 составляет ${\displaystyle 1+2(r^{1}+r^{2})}$. Если мы продолжим использовать дополнительные пути, как указано выше, общий поток сходится к ${\displaystyle \textstyle 1+2\sum _{i=1}^{\infty }r^{i}=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

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

• Приближенная теорема о максимальном расходе и минимальном сокращении
• Маршрутизация с ограничением поворотов

Заметки

1. Лаунг-Тернг Ван, Яо-Вэнь Чанг, Кван-Тинг (Тим) Ченг (2009). Автоматизация электронного проектирования: синтез, проверка и тестирование. Морган Кауфманн. стр.204. ISBN  0080922007.
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-О.

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

• Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (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.

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

• Учебное пособие, объясняющее метод Форда – Фулкерсона для решения задачи о максимальном расходе.
• Еще одна Java-анимация
• Приложение Java Web Start

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