Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Алгоритм Форда-Фалкерсона

Лекция



Привет, сегодня поговорим про алгоритм форда-фалкерсона, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое алгоритм форда-фалкерсона , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

алгоритм форда-фалкерсона  — решает задачу нахождения максимального потока в транспортной сети.

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

Ключевую роль в методе Форда-Фалкерсона играют два понятия: остаточные сети и дополняющие пути. Пусть дана сеть и поток в ней. Тогда остаточная сеть состоит из тех ребер (называемых также остаточными), поток по которым можно увеличить. Заметим, что остаточное ребро не обязано быть ребром исходной сети. Такие "странные" ребра появляются когда имеется поток вещества в обратном направлении — ведь этот поток можно уменьшить. Назовем дополняющим путем простой путь из истока в сток в остаточной сети. Из определения остаточной сети вытекает, что по всем ребрам дополняющего пути можно переслать еще сколько-то вещества, не превысив их пропускную способность. Величину наибольшего потока, который можно переслать по дополняющему пути назовем остаточной пропускной способностью пути. Очевидно, она равна значению минимального остаточного ребра, входящего в данный путь.

При выполнении каждой итерации метода Форда-Фалкерсона мы находим некоторый увеличивающий путь р, и поток 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 в остаточной сети G
f
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 Алгоритм Форда-Фалкерсона

На этом все! Теперь вы знаете все про алгоритм форда-фалкерсона, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое алгоритм форда-фалкерсона и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов

Из статьи мы узнали кратко, но содержательно про алгоритм форда-фалкерсона
создано: 2014-10-13
обновлено: 2021-03-13
132756



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов