Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Лекции - Структуры и алгоритмы компьютерной обработки данных / 20.Алгоритмы построения максимального потока. Максимальный поток минимальной стоимости

.doc
Скачиваний:
100
Добавлен:
06.02.2015
Размер:
77.82 Кб
Скачать

Потоки в сетях

Сеть – ориентированный взвешенный граф с неотрицательными весами ребер. Будем считать вес ребра cij его пропускной способностью. В сети выделяются две вершины - исток s и сток t.

Поток в сети – функция F: E → R+, удовлетворяющая трем условиям:

1. fijcij - поток ограничен пропускной способностью

2.

3.

Максимальный поток

Величина потока – суммарный поток из истока.

Задача – найти поток максимальной величины.

Применения – трубопровод, транспортная сеть грузоперевозок, задачи распределения.

Остаточная сеть

Остаточная сеть для некоторого потока f – ориентированный граф, множество вершин которого совпадает с V, множество ребер определяется следующими условиями:

для пары вершин i,j

Если fij < cij, то сеть содержит прямое ребро i→j с весом cijfij.

Если 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.

Потоки одинаковой величины могут иметь разную стоимость. Задача – найти максимальный поток минимальной стоимости.

Соседние файлы в папке Лекции - Структуры и алгоритмы компьютерной обработки данных