Реализация метод форда фалкерсона

Обновлено: 18.05.2024

Впервые был предложен в 1956г. До этого времени задача решалась с помощью методов линейного программирования, что было крайне не эффективно. Алгоритм является псевдополиномиальным и имеет оценку O ( nm log U ), где m = | E |, n = | V |, U = max ( C_ij ).

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

Увеличивающей цепью является цепь из источника в сток, все дуги которой допустимы. Дугу из вершины a в вершину b назовем допустимой, если выполняется одно из следующих условий:

1. f ( e ) c ( e ) и дуга согласованна

2. f ( e ) > 0 и дуга несогласованна

По увеличивающей цепи можно пустить поток величины Q , где Q = min < q ( e_i ), 1 ≤ i ≤ l > и q ( e ) = <с( e ) – f ( e ), если дуга согласованна, f ( e ), если дуга не согласованна>. Для того, чтобы увеличить величину потока сети на Q , необходимо увеличить на Q поток на каждой согласованной дуге цепи и уменьшить на каждой несогласованной.

В своей работе [3] Форд и Фалкерсон (Ford and Fulkerson) доказали, что поток в сети, для которой нельзя построить увеличивающую цепь, является максимальным.

Для нахождения увеличивающей цепи ими был предложен “Метод расстановки пометок”. Процесс расстановки меток начинается в источнике сети и заканчивается в ее стоке. Как только сток оказался помеченным, мы можем говорить о существовании увеличивающей цепи из источника в сток. Метка, “наносимая” на вершины сети, содержит необходимый минимум информации, достаточный для того, чтобы восстановить эту цепь и определить величину, на которую можно изменить поток в ней. Вершина сети может находиться в одном из 3-х состояний: “непомеченная”, “помеченная” и “просмотренная”.

Этап 1. Расстановка меток.

Все вершины получают статус непомеченных.

Процедура расстановки меток.

Возьмем произвольный помеченный, но не просмотренный узел x . Пусть он имеет пометку [ i , +, e ( x )], где i – вершина из которой был помечен x ; флаг, показывающий, что дуга ( i , x ) согласованна; e – величина потока, который можно пропустить по этой дуге. Рассмотрим все непомеченные смежные вершины y , такие что дуга ( x , y ) согласованна. Пометим вершину y меткой [ x , +, e ( y )], где e ( y ) = min < e ( x ) , c ( x , y ) – f ( x , y )>. Затем рассмотрим все непомеченные смежные вершины y , соединенные с ней несогласованной дугой. Пометим их меткой [ x , -, e ( y )], где e ( y ) = min < e ( x ), f ( y , x )>. Теперь все рассмотренные узлы y имеют статус помеченных, а узел x - просмотренный.

Эта общая для всех узлов сети процедура. Пометим источник меткой [~, ~, ∞] и будем последовательно вызывать ее для всех смежных узлов, постепенно двигаясь по сети. Как только процедура будет вызвана для стока, будет получена увеличивающая цепь и следует перейти ко второму этапу. В противном случае процедура будет вызываться, пока все помеченные вершины не станут просмотренными, и если сток сети не был достигнут – увеличивающая цепь не может быть построена и по теореме Форда-Фалкерсона имеющийся поток сети является максимальным.

Этап 2. Изменение потока.

Процедура изменения потока дуги.

Возьмем узел x . Если он имеет метку [ y , +, e ], то увеличим поток по дуге ( y , x ) на e . Если он имеет метку [ y , -, e ], то уменьшим поток по дуге ( y , x ) на e . Если y не является источником, то вызовем процедуру для узла y .

Эта процедура, будучи вызвана для стока сети, позволяет пройти по найденной увеличивающей цепи к стоку, изменяя поток на ее дугах.

Следует особо отметить, что узлы, имеющие статус “помеченных”, больше не участвуют в процессе поиска увеличивающей цепи, весьма эффективно с вычислительной точки зрения. [1]

Алгоритм Форда-Фалкерсона гарантирует нахождение максимального потока только в сетях с целочисленными пропускными способностями. На практике “чистый” алгоритм Форда-Фалкерсона не применяется, т.к. оценка его производительности зависит от величины пропускных способностей дуг сети. Все дело в том, что в нем не дается каких либо правил выбора увеличивающей цепи.

Рассмотрим сеть на рис. 1. Предположим, что реализован алгоритм, отдающий предпочтение увеличивающим цепям максимальной длины. В этом случае на первом шаге мы пустим дополнительный поток по цепи (0,1),(1,2),(2,3).

На втором шаге выберем цепь (0,2),(2,1),(1,3). Так как дуга (2,1) несогласованна, величина пущенного по ней потока будет вычитаться из величины потока, полученного на предыдущем шаге. Мы получили сеть (рис. 3) практически эквивалентную исходной.

Очевидно, что для нахождения максимального потока понадобиться 1000 итераций! В то время, как если бы мы на первом шаге выбрали цепь (0,1),(1,3), то результат был бы получен за одну итерацию! На практике, величина пропускных способностей часто зависит от единиц измерения, и может принимать огромные значения. Если же допустить иррациональные пропускные способности дуг, то можно привести пример невычислимой сети [4]. Величина потока в такой сети не превысит даже четверти истинного значения. Подобная неопределенность длилась не долго, уже в начале 70-х г. были предложены сразу 2 правила выбора увеличивающих цепей, которые существенно улучшают алгоритм Форда-Фалкерсона.

[1] Существует множество модификаций метода расстановки пометок. Fong и Rao [12] предложили хранить помеченные вершины в дереве, в этом случае на следующей итерации можно использовать часть содержащейся в дереве информации. Lin и Leon [13] разработали модификацию алгоритма, проводящую сканирование и маркирование вершин одновременно из источника и из стока. Это позволяет получить вместо одного большого дерева меток, два меленьких, что более эффективно. Srinivasan [14] и Johnson [15] в своих работах рассматривали метки разнообразной структуры.

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

$u,v \in V$

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Содержание

Алгоритм

Неформальное описание

Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.

Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:

На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью c_min .
Для каждого ребра на найденном пути увеличиваем поток на c_min , а в противоположном ему - уменьшаем на c_min .
Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.

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

Если искать не любой путь, а кратчайший, получится алгоритм Эдмондса-Карпа или алгоритм Диница. Эти алгоритмы сходятся для любых вещественных весов за время O( | V | | E | 2 ) и O( | V | 2 | E | ) соответственно.

Формальное описание

Дан граф G(V,E) с пропускной способностью c(u,v) и потоком f(u,v) = 0 для ребер из u в v. Необходимо найти максимальный поток из источника s в сток t. На каждом шаге алгоритма действуют те же условия, что и для всех потоков:

Остаточная сеть G_f(V,E_f) — сеть с пропускной способностью c_f(u,v) = c(u,v) − f(u,v) и без потока.

Сложность

Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено O(E*f), где E — число рёбер в графе, f — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за O(E) и увеличивает поток как минимум на 1.

Пример не сходящегося алгоритма

Рассмотрим приведённую справа сеть, с источником , стоком , пропускными способностями рёбер , и соответственно , -1)/2" width="" height="" />
и и пропускной способностью всех остальных рёбер, равной целому числу . Константа выбрана так, что . Мы используем пути из остаточного графа, приведённые в таблице, причём " width="" height="" />
, " width="" height="" />
и " width="" height="" />
.

Шаг	Найденный путь	Добавленный поток	Остаточные пропускные способности
Шаг	Найденный путь	Добавленный поток	e₁	e₂	e₃
0	r 0 = 1	r	1
1	s,v₂,v₃,t>	1	r 0	r 1	0
2	p₁	r 1	r 2	0	r 1
3	p₂	r 1	r 2	r 1	0
4	p₁	r 2	0	r 3	r 2
5	p₃	r 2	r 2	r 3	0

$\textstyle 1 + 2\sum_<i=1> Заметим, что после шага 1, как и после шага 5, остаточные способности рёбер e1 , e2 и e3 имеют форму r n , r n + 1 и 0 , соответственно, для какого-то натурального n . Это значит, что мы можем использовать увеличивающие пути p1 , p2 , p1 и p3 бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме.Полный поток после шага 5 равен 1 + 2(r 1 + r 2 ) . За бесконечное время полный поток сойдётся к ^\infty r^i = 3 + 2r$
, тогда как максимальный поток равен 2M + 1 . Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению. [1]

Пример

Следующий пример показывает первые шаги алгоритма Форда–Фалкерсона в транспортной сети с четырьмя узлами, источником A и стоком D. Этот пример показывает худший случай. При использовании поиска в ширину алгоритму потребуется всего лишь 2 шага.

Актуальность данной работы заключается в необходимости для любого программиста знаний в области дискретной математики и различных ее алгоритмов, для использования при реализации разрабатываемых программных продуктов и для решения поставленных задач.

Изучение представленных алгоритмов в теории, а так же их реализация на языке программирования высокого уровня позволяют судить об эффективности данных алгоритмов и дают важный опыт.

алгоритм программный дискретный математика

Формулировка задания

изучить теоретические аспекты вопроса построения алгоритма Форда-Фалкерсона;

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

Изучение алгоритма

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

Транспортная сеть - это ориентированный граф, ребра которого имеют определенную не отрицательную пропускную способность и поток. Выделяют две такие вершины s (исток) и t (сток), что любые другие вершины находятся на пути из s в t.

Целочисленная транспортная сеть - транспортная сеть, все пропускные способности ребер которой - целые числа.

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

Идея алгоритма Форда-Фалкерсона заключается в том, чтобы выбрать произвольный путь от источника (s) к стоку (t), найти на этом пути минимальное значение остаточных пропускных способностей и увеличиваем поток на каждом ребре этого пути на найденное значение. Такие действия проделываются для всех возможных путей.

Алгоритм Фода-Фалкерсона способен отыскать максимальный поток, не зависимо от того, какой метод выбран для нахождения аугументальных путей, а так же независимо от того, какой путь мы найдем, он всегда оканчивается определением сечения, поток которого равен пропускной способности, а значит, равен величине потока сети, который является максимальным потоком.

Пошаговое описание алгоритма:

1. Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью;

2. В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся;

3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток;

4. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью C_min;

5. Для каждого ребра на найденном пути увеличиваем поток на C_min, а в противоположном ему - уменьшаем на C_min;

6. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его;

7. Возвращаемся на шаг 2.

Пусть задан граф G = (V, E), где V - множество вершин графа, E - множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

1. Из множества всех белых вершин выберем любую вершину, обозначим её V₁.

2. Выполняем для неё процедуру DFS(V₁).

3. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр - вершина )

1. Перекрашиваем вершину u в черный цвет.

2. Для всякой вершины w, смежной с вершиной u и окрашенной в белый цвет, выполняем процедуру DFS(w).

Для наглядности рассмотрим пример транспортной сети, и поиск в ней максимального потока.

21 декабря 2020 mob25

На этом шаге рассмотрим программную реализацию метода Форда-Фалкерсона.

Неформально этот алгоритм может быть записан следующим образом:

Формируем нулевой поток
Пока существует путь из истока в сток, увеличивающий поток
Выбираем Cmin - минимальную из остаточных пропускных способностей найденного пути
Для каждой дуги (u,v) пути (из вершины u в вершину v)
f[u,v] := f[u,v] + Cmin
f[v,u] := -f[u,v]

Далее приводится описание одного из вариантов программной реализации метода Форда-Фалкерсона.

В процедуре MaxFlow вызываются процедура Init для инициализации нулевого потока и функция ExistPath, которая возвращает значение true, если увеличивающий путь существует, и значение false в противном случае.

Очевидно, что если функция ExistPath возвращает значение false, то процедура MaxFlow завершает свою работу (увеличивающих путей больше нет).

Если же ExistPath возвращает true (найден увеличивающий путь), то через свои параметры она возвращает также Cmin (минимальное значение из остаточных пропускных способностей дуг увеличивающего пути) и KR (количество дуг в увеличивающем пути).

В глобальном для процедуры MaxFlow массиве path возвращаются номера вершин увеличивающего пути, перечисленные в порядке
от стока к истоку.

Если путь найден, то в соответствии с алгоритмом Форда-Фалкерсона для всех
дуг увеличивающего пути пересчитывается поток f[u, v], строятся обратные дуги
с отрицательным потоком f[v, u] и пересчитываются остаточные пропускные способности cf[u, v] и cf[v, u].

Читайте также: