Лекция
Привет, сегодня поговорим про алгоритм форда-фалкерсона, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое алгоритм форда-фалкерсона , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
алгоритм форда-фалкерсона — решает задачу нахождения максимального потока в транспортной сети.
Задача о максимальном потоке для данной сети состоит в следующем: найти максимально возможную скорость производства (и потребления) вещества, при которой его еще можно доставить от истока к стоку при данных пропускных способностях труб.
Ключевую роль в методе Форда-Фалкерсона играют два понятия: остаточные сети и дополняющие пути. Пусть дана сеть и поток в ней. Тогда остаточная сеть состоит из тех ребер (называемых также остаточными), поток по которым можно увеличить. Заметим, что остаточное ребро не обязано быть ребром исходной сети. Такие "странные" ребра появляются когда имеется поток вещества в обратном направлении — ведь этот поток можно уменьшить. Назовем дополняющим путем простой путь из истока в сток в остаточной сети. Из определения остаточной сети вытекает, что по всем ребрам дополняющего пути можно переслать еще сколько-то вещества, не превысив их пропускную способность. Величину наибольшего потока, который можно переслать по дополняющему пути назовем остаточной пропускной способностью пути. Очевидно, она равна значению минимального остаточного ребра, входящего в данный путь.
При выполнении каждой итерации метода Форда-Фалкерсона мы находим некоторый увеличивающий путь р, и поток f вдоль каждого ребра данного пути увеличивается на величину остаточной пропускной способности сf (р). Об этом говорит сайт https://intellect.icu . Реализация данного метода вычисляет максимальный поток в графе G = (V, Е) путем обновления потока f[u,v] между каждой парой вершин и и v, соединенных ребром. Если вершины u и v не связаны ребром ни в одном направлении, неявно предполагается, что f[u, v] = 0. Предполагается, что значения пропускных способностей задаются вместе с графом и с (u, v) = 0, если (u, v) є Е.
Остаточная пропускная способность сf (u, v) вычисляется по формуле cf (u, v) = с (u, v) - f (u, v).
Ford_Fulkerson(G, s, t) 1 for (для) каждого ребра (u, v) є E[G] 2 do f[u,v] «-0 3 f[v,u] «- 0 4 while существует путь p из s в t в остаточной сети Gf
5 do сf(р) «— min {cf(u, v) : (u, v) принадлежит р} 6 for (для) каждого ребра (u, v) in p 7 do f[u,v] «- f[u] + cf(p) 8 f[v,u] «- -f[u,v]
Строки 1-3 инициализируют поток f значением 0. В цикле while в строках 4-8 выполняется неоднократный поиск увеличивающего пути р в Gf, и поток f вдоль пути р увеличивается на остаточную пропускную способность Cf (р). Когда увеличивающих путей больше нет, поток f является максимальным.
Время выполнения процедуры Ford_Fulkerson зависит от того, как именно выполняется поиск увеличивающего пути р в строке 4. При неудачном методе поиска алгоритм может даже не завершиться: величина потока будет последовательно увеличиваться, но она не обязательно сходится к максимальному значению потока.
Выполнение строк 1-3 занимает время в (Е). Цикл while в строках 4-8 выполняется не более |f*| раз, поскольку величина потока за каждую итерацию увеличивается по крайней мере на одну единицу. Время поиска пути в остаточной сети составляет О (V + Е') = О (Е), если используется поиск в глубину или поиск в ширину. Каждая итерация цикла while занимает время О (Е), так что в результате общее время выполнения составляет О(Е|f*|), где f* — максимальный поток, найденный данным алгоритмом.
Работа базового алгоритма Форда-Фалкерсона (последовательные итерации цикла while). В левой части каждого рисунка показана остаточная сеть Gf с выделенным увеличивающим путем р; в правой части показан новый поток f, который получается в результате прибавления fр к f
На этом все! Теперь вы знаете все про алгоритм форда-фалкерсона, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое алгоритм форда-фалкерсона и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Из статьи мы узнали кратко, но содержательно про алгоритм форда-фалкерсона
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов