Метод Форда – Фулкерсона или алгоритм Форда – Фулкерсона ( FFA ) - это жадный алгоритм, который вычисляет максимальный поток в потоковой сети . Иногда его называют «методом», а не «алгоритмом», поскольку подход к поиску дополнительных путей в остаточном графе не полностью определен [1] или определен в нескольких реализациях с разным временем выполнения. [2] Он был опубликован в 1956 году Л. Р. Фордом-младшим и Д. Р. Фулкерсоном . [3] Название «Форд – Фалкерсон» часто также используется для алгоритма Эдмондса – Карпа., который является полностью определенной реализацией метода Форда – Фулкерсона.
Идея алгоритма заключается в следующем: пока существует путь от источника (начальный узел) до приемника (конечный узел) с доступной емкостью на всех ребрах пути, мы отправляем поток по одному из путей. Потом находим другой путь и так далее. Путь с доступной емкостью называется дополнительным путем .
Алгоритм
Позволять - граф, и для каждого ребра от u до v пусть быть вместимостью и быть потоком. Мы хотим найти максимальный поток от источника s до стока t . После каждого шага алгоритма сохраняется следующее:
Ограничения мощности Поток по ребру не может превышать его пропускную способность. Косая симметрия Чистый поток от u к v должен быть противоположен чистому потоку от v к u (см. Пример). Сохранение потока Чистый поток к узлу равен нулю, за исключением источника, который «производит» поток, и стока, который «потребляет» поток. Значение (f) Поток, выходящий из s, должен быть равен потоку, поступающему в t .
Это означает, что поток через сеть является законным после каждого раунда в алгоритме. Определим остаточную сеть быть сетью с пропускной способностью и никакого потока. Обратите внимание, что может случиться так, что поток от v к u разрешен в остаточной сети, но запрещен в исходной сети: if а также тогда .
Алгоритм Форда – Фулкерсона
- Входы в сети с пропускной способностью c , исходным узлом s и приемным узлом t
- Выходные данные Вычислить поток f от s до t максимального значения.
- для всех краев
- Пока есть путь p от s до t в, такое что для всех краев :
- Находить
- Для каждого края
- ( Отправьте поток по пути )
- ( Поток может быть «возвращен» позже )
- «←» обозначает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого элемента изменяется на значение элемента .
- « return » завершает алгоритм и выводит следующее значение.
Путь на шаге 2 можно найти, например, с помощью поиска в ширину (BFS) или поиска в глубину в. Если вы используете первый, алгоритм называется Эдмондс – Карп .
Если на шаге 2 больше нет путей, s не сможет достичь t в остаточной сети. Если S - это набор узлов, достижимых s в остаточной сети, то общая пропускная способность в исходной сети ребер от S до остальной части V равна, с одной стороны, общему потоку, который мы нашли от s до t , и с другой стороны, служит верхней границей для всех таких потоков. Это доказывает, что найденный нами поток максимален. См. Также теорему о максимальном расходе и минимальном отсечении .
Если график имеет несколько источников и приемников, мы действуем следующим образом: Предположим, что а также . Добавить новый источник с краю из к каждому узлу , с емкостью . И добавить новую раковину с краю из каждого узла к , с емкостью . Затем примените алгоритм Форда – Фулкерсона.
Кроме того, если узел u имеет ограничение емкости, мы заменяем этот узел двумя узлами , и край , с емкостью . Затем примените алгоритм Форда – Фулкерсона.
Сложность
При добавлении пути увеличения потока к потоку, уже установленному на графике, максимальный поток будет достигнут, когда на графике больше не будет путей увеличения потока. Однако нет уверенности в том, что эта ситуация когда-либо будет достигнута, поэтому лучшее, что можно гарантировать, - это то, что ответ будет правильным, если алгоритм завершится. В случае, если алгоритм работает бесконечно, поток может даже не сходиться к максимальному потоку. Однако такая ситуация возникает только при иррациональных значениях расхода. [ необходимая цитата ] Когда емкости являются целыми числами, время выполнения Форда – Фулкерсона ограничено(см. большие обозначения O ), где количество ребер в графе и - максимальный поток на графике. Это потому, что каждый путь увеличения можно найти в времени и увеличивает поток на целое число не менее , с верхней границей .
Вариантом алгоритма Форда – Фулкерсона с гарантированным завершением и временем выполнения, не зависящим от максимального значения потока, является алгоритм Эдмондса – Карпа , который выполняется в время.
Интегральный пример
В следующем примере показаны первые шаги Форда – Фулкерсона в потоковой сети с 4 узлами, источник и тонуть . Этот пример показывает наихудшее поведение алгоритма. На каждом этапе только потокотправляется по сети. Если бы вместо этого использовался поиск в ширину, потребовалось бы всего два шага.
Дорожка | Вместимость | Результирующая потоковая сеть |
---|---|---|
Сеть начального потока | ||
После 1998 года больше шагов ... | ||
Конечная поточная сеть |
Обратите внимание, как поток "отталкивается" от к при поиске пути .
Пример без завершения
Рассмотрим проточную сеть, показанную справа, с источником , раковина , емкости кромок , а также соответственно , а также а мощность всех остальных ребер некоторое целое число . Постоянная было выбрано так, что . Мы используем увеличивающие пути в соответствии со следующей таблицей, где, а также .
Шаг | Расширение пути | Отправленный поток | Остаточные мощности | ||
---|---|---|---|---|---|
0 | |||||
1 | |||||
2 | |||||
3 | |||||
4 | |||||
5 |
Обратите внимание, что после шага 1, а также после шага 5 остаточные мощности ребер , а также находятся в форме , а также соответственно для некоторых . Это означает, что мы можем использовать дополнительные пути., , а также бесконечно много раз и остаточные емкости этих ребер всегда будут в одном и том же виде. Общий поток в сети после шага 5 составляет. Если мы продолжим использовать дополнительные пути, как указано выше, общий поток сходится к. Однако обратите внимание, что существует поток стоимости, отправив единиц потока по , 1 ед. Протока по , а также единиц потока по . Следовательно, алгоритм никогда не завершается, и поток даже не сходится к максимальному потоку. [4]
Другой пример без завершения, основанный на алгоритме Евклида, приведен Backman & Huynh (2018) , где они также показывают, что время работы алгоритма Форда-Фулкерсона в худшем случае в сетив порядковых чисел является.
Реализация алгоритма Эдмондса – Карпа на Python
импортные коллекцииclass Graph : "" "Этот класс представляет ориентированный граф, использующий представление матрицы смежности." "" def __init__ ( self , graph ): self . graph = graph # остаточный граф self . row = len ( график ) def bfs ( self , s , t , parent ): "" "Возвращает истину, если существует путь от источника 's' к 't' в остаточном графе. Также заполняет parent [] для сохранения пути." "" # Пометить все вершины как непосещаемые посещенные = [ False ] * self . строка # Создать очередь для BFS queue = collections . deque () # Отметить исходный узел как посещенный и поставить его в очередь . добавление ( я ) посещено [ s ] = True # Стандартный цикл BFS при очереди : u = queue . поплефт () # Получить все смежные вершины исключенной из очереди вершины u # Если соседняя вершина не была посещена, то отметьте ее # посещенной и поставьте ее в очередь для ind , val в enumerate ( self . Graph [ u ]): if ( loaded [ ind ] == Ложь ) и ( val > 0 ): очередь . append ( ind ) посещено [ ind ] = истинный родитель [ ind ] = u # Если мы достигли приемника в BFS, начиная с источника, то возвращаем # true, иначе false возвращаем посещено [ t ] # Возвращает максимальный поток от s до t в заданном графе def edmonds_karp ( self , source , сток ): # Этот массив заполняется BFS и хранит путь parent = [ - 1 ] * self . строка max_flow = 0 # Изначально нет потока # Увеличьте поток, пока есть путь от источника до стока, пока есть self . bfs ( источник , приемник , родитель ): # Найти минимальную остаточную емкость ребер по # пути, заполненному BFS. Или мы можем сказать: найти максимальный поток # по найденному пути. path_flow = float ( "Inf" ) s = сток, а s ! = source : path_flow = min ( path_flow , self . graph [ parent [ s ]] [ s ]) s = parent [ s ] # Добавить поток пути к общему потоку max_flow + = path_flow # обновить остаточные емкости ребер и обратных ребер # по пути v = сток, а v ! = source : u = parent [ v ] self . граф [ u ] [ v ] - = путь_потока сам . граф [ v ] [ u ] + = path_flow v = parent [ v ] вернуть max_flow
Смотрите также
Заметки
- ^ Laung-Terng Ван Яо-Вен Чанг, Kwang-Тин (Tim) Cheng (2009). Автоматизация электронного проектирования: синтез, проверка и тестирование . Морган Кауфманн. С. 204 . ISBN 978-0080922003.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест; Клиффорд Штайн (2009). Введение в алгоритмы . MIT Press. С. 714 . ISBN 978-0262258104.
- ^ Ford, LR ; Фулкерсон, Д.Р. (1956). «Максимальный поток через сеть» (PDF) . Канадский математический журнал . 8 : 399–404. DOI : 10,4153 / CJM-1956-045-5 .
- ^ Цвик, Ури (21 августа 1995 г.). «Наименьшие сети, в которых процедура максимального потока Форда – Фулкерсона может не завершиться». Теоретическая информатика . 148 (1): 165–170. DOI : 10.1016 / 0304-3975 (95) 00022-O .
Рекомендации
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (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). ЭНГРИ 1101 . Cornell University.
- Бэкман, Спенсер; Хьюнь, Тони (2018). «Трансфинитный Форд – Фулкерсон на конечной сети». Вычислимость . 7 (4): 341–347. arXiv : 1504.04363 . DOI : 10.3233 / COM-180082 . S2CID 15497138 .
Внешние ссылки
- Учебное пособие, объясняющее метод Форда – Фулкерсона для решения задачи о максимальном расходе.
- Еще одна Java-анимация
- Приложение Java Web Start
СМИ, связанные с алгоритмом Форда-Фулкерсона, на Викискладе?