Лекции - Структуры и алгоритмы компьютерной обработки данных / 20.Алгоритмы построения максимального потока. Максимальный поток минимальной стоимости
.docПотоки в сетях
Сеть – ориентированный взвешенный граф с неотрицательными весами ребер. Будем считать вес ребра cij его пропускной способностью. В сети выделяются две вершины - исток s и сток t.
Поток в сети – функция F: E → R+, удовлетворяющая трем условиям:
1. fij ≤ cij - поток ограничен пропускной способностью
2.
3.
Максимальный поток
Величина потока – суммарный поток из истока.
Задача – найти поток максимальной величины.
Применения – трубопровод, транспортная сеть грузоперевозок, задачи распределения.
Остаточная сеть
Остаточная сеть для некоторого потока f – ориентированный граф, множество вершин которого совпадает с V, множество ребер определяется следующими условиями:
для пары вершин i,j
Если fij < cij, то сеть содержит прямое ребро i→j с весом cij –fij.
Если fij >0, то сеть содержит обратное ребро j→i с весом fij.
Метод Форда-Фалкерсона
Если в остаточной сети существует путь из истока в сток, то можно увеличить поток вдоль пути следующим образом:
-
найдем ребро с минимальным весом в пути,
-
увеличим поток вдоль всех прямых ребер на величину этого веса, уменьшим поток вдоль обратных ребер на величину веса.
Метод Форда-Фалкерсона: Пока в остаточной сети существует путь из истока в сток увеличивать поток вдоль пути.
Анализ метода
Если выбирается произвольный путь, то сложность метода зависит от величины пропускных способностей ребер
Пример:
Максимальный поток - 2x109.
Если увеличивать поток вдоль путей 1-2-3-4 и 1-3-2-4, то на каждом шаге поток будет увеличиваться на 1 и понадобится 2x109 шагов.
Алгоритм Эдмондса-Карпа
Алгоритм Эдмондса-Карпа – модификация метода Форда-Фалкерсона, когда для поиска пути используется поиск в ширину. Можно показать, что для построения максимального потока достаточно найти mn/2 путей. Общая сложность алгоритма – O(nm2).
Существуют алгоритмы (проталкивания предпотока) со сложностью O(n3)
Процедура поиска максимального потока
C[1..n,1..n] – матрица пропускных способностей
F[1..n,1..n] – поток
P[1..n] – путь из истока в сток, найденный поиском в ширину
MaxFlow:=0;
While BFS(S,T) do
begin
{Search min arc} m:=oo; k:=T;
While k>S do
begin m:=min(m,c[p[k],k]-f[p[k],k]); k:=p[k];
end;
MaxFlow:=MaxFlow+m;
{Increase Flow} k:=T;
While k>S do
begin f[p[k],k]:=f[p[k],k]+m; f[k,p[k]]:=f[k,p[k]]-m;
k:=p[k];
end;
end;
Максимальный поток минимальной стоимости
Каждому ребру соответствуют два числа – пропускная способность cij и стоимость sij.
Стоимость потока по ребру i-j вычисляется как произведение fijsij. Суммарная стоимость потока вычисляется как Σ fijsij.
Потоки одинаковой величины могут иметь разную стоимость. Задача – найти максимальный поток минимальной стоимости.