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

В Метод Форда – Фулкерсона или Алгоритм Форда – Фулкерсона (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}$.

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

Путь на шаге 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

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

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

Заметки

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

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