Центральный Дом Знаний - Алгоритм Эдмондса — Карпа

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Я учусь (закончил(-а) в
Всего ответов: 2653

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

Алгоритм Эдмондса — Карпа

Алгоритм Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время O(VE2). Впервые был опубликован в 1970 году советским учёным Е. А. Диницом. Позже, в 1972 году, был независимо открыт Эдмондсом и Карпом.

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

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

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

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

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

    2. Для каждого ребра на найденном пути увеличиваем поток на cmin , а в противоположном ему — уменьшаем на cmin .

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

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

Чтобы найти кратчайший путь в графе, используем поиск в ширину:

  1. Создаём очередь вершин О. Вначале О состоит из единственной вершины s.

  2. Отмечаем вершину s как посещённую, без предка, а все остальные как непосещённые.

  3. Пока очередь непуста, выполняем следующие шаги:

    1. Удаляем первую в очереди вершину u.

    2. Для всех рёбер (u, v), исходящих из вершины u, таких что вершина v ещё не посещена, выполняем следующие шаги:

      1. Отмечаем вершину v как посещённую, с предком u.

      2. Добавляем вершину v в конец очереди

      3. Если v=t, выходим из обоих циклов: мы нашли кратчайший путь.

  4. Если очередь пуста, возвращаем ответ, что пути нет вообще и останавливаемся.

  5. Если нет, идём от t к s, каждый раз переходя к предку. Возвращаем путь в обратном порядке. 

В процессе работы А.Э.-К. будет находить каждый дополняющий путь за время O(E). Ниже мы докажем, что общее число увеличений потока, выполняемое данным алгоритмом, составляет O(VE). Таким образом, сложность А.Э.-К. равна O(VE2). 

Назовём расстоянием от вершины x до вершины у длину кратчайшего пути от x до y в остаточной сети. Если такого пути нет, будем считать расстояние бесконечным. Будем говорить, что y приблизилась к x (отдалилась от x), если расстояние от x до y уменьшилось (увеличилось). Будем говорить, что y ближе к x (дальше от x), чем z, если расстояние от x до y меньше (больше), чем расстояние от x до z.

Лемма. В ходе работы алгоритма ни одна вершина никогда не приближается к источнику. Доказательство. Пусть это не так, тогда при каком-то увеличении потока некоторые вершины приблизилась к источнику. Назовём их неправильными. Выберем ту из неправильных вершин, которая после увеличения потока оказалась ближе всех к источнику (если таких больше одной, то любую из них). Обозначим выбранную вершину через v. Рассмотрим кратчайший путь от s до v. Обозначим предпоследнюю вершину на этом пути через u, таким образом, путь имеет вид s-...-u-v. Поскольку u ближе к s, чем v, а v - ближайшая к s из неправильных вершин, u - вершина правильная. Обозначив расстояния от s до u и v до и после увеличения потока соответственно через , имеем:

d_v^' < d_v

d_u^' \ge d_u

d_v^' = d_u^' + 1

, откуда

d_v^ \ge d_u^ + 2

Следовательно, до увеличения потока ребро (u, v) отсутствовало в остаточной сети. Чтобы оно появилось, увеличивающий путь должен был содержать ребро (v, u). Но в А.Э.-К. увеличивающий путь всегда кратчайший, следовательно,

du = dv + 1

, что противоречит предыдущему неравенству. Значит, наше предположение было неверным. Лемма доказана.

Назовём критическим то из ребёр увеличивающего пути, у которого остаточная пропускная способность минимальна. Оценим, сколько раз некое ребро (u, v) может оказываться критическим. Пускай это произошло на итерации t1, а в следующий раз на итерации t2. Обозначая через Dy(t) расстояние от s до y на итерации t, имеем:

Dv(t1) = Du(t1) + 1

Dv(t2) = Du(t2) + 1

Заметим, что критическое ребро исчезает из остаточной сети. Чтобы ребро (u, v) в ней вновь появилось, необходимо, чтобы на какой-то промежуточной итерации t3 был выбран увеличивающий путь, содержащий ребро (v, u). Следовательно,

Du(t3) = Dv(t3) + 1

Используя ранее доказанную лемму, получаем:

D_v(t_2) = D_u(t_2)+1 \ge D_u(t_3)+1 = D_v(t_3)+2 \ge D_v(t_1)+2

Поскольку изначально Dv > 0 (иначе v=s, но ребро, ведущее в s, не может появиться на кратчайшем пути из s в t), и всегда, когда Dv конечно, оно не превышает V (кратчайший путь не содержит циклов, и, следовательно, содержит менее V ребёр), ребро может оказаться критическим не более \frac{(V-1)-1}{2} + 2 = V/2+1 раз. Поскольку каждый увеличивающий путь содержит хотя бы одно критическое ребро, а всего рёбер, которые могут когда-то стать критическими, 2E (все рёбра исходной сети и им противоположные), то мы можем увеличить путь не более Е(V+2) раз. Следовательно, количество итераций не превышает O(EV), что и требовалось доказать. 

Пусть задана сеть с истоком в вершине A и стоком в вершине G. На рисунке парой f / c обозначен поток по этому ребру и его пропускная способность.

Edmonds-Karp flow example 0.svg

Опишем поиск в ширину на первом шаге.

  1. Очередь состоит из единственной вершины A. Посещена вершина A. Предков нет.

  2. Очередь состоит (от начала к концу) из вершин B и D. Посещены вершины A,B,D. Вершины B,D имеют предка А.

  3. Очередь состоит из вершин D и C. Посещены A,B,C,D. Вершины B,D имеют предка А, вершина C — предка B.

  4. Очередь состоит из вершин C,E,F. Посещены A,B,C,D,E,F. Вершины B,D имеют предка А, вершина C — предка B, вершины E,F — предка D.

  5. Вершина C удаляется из очереди: рёбра из неё ведут только в уже посещённые вершины.

  6. Обнаруживается ребро (E,G) и цикл останавливается. В очереди вершины (F,G). Посещены все вершины. Вершины B,D имеют предка А, вершина C — предка B, вершины E,F — предка D, вершина G — предка E.

  7. Идём по предкам: G->E->D->A. Возвращаем пройденный путь в обратном порядке: А->D->E->G.

Заметим, что в очередь последовательно добавляли вершины, достижимые из A ровно за 1 шаг, ровно за 2 шага, ровно за 3 шага. Кроме того, предком каждой вершины является вершина, достижимая из A ровно на 1 шаг быстрее. 

Пропускная способность пути

Путь


min(cf(A,D),cf(D,E),cf(E,G)) =

min(3 − 0,2 − 0,1 − 0) =
min(3,2,1) = 1

A,D,E,G

min(cf(A,D),cf(D,F),cf(F,G)) =

min(3 − 1,6 − 0,9 − 0) =
min(2,6,9) = 2

A,D,F,G

min(cf(A,B),cf(B,C),cf(C,D),cf(D,F),cf(F,G)) =

min(3 − 0,4 − 0,1 − 0,6 − 2,9 − 2) =
min(3,4,1,4,7) = 1

A,B,C,D,F,G

min(cf(A,B),cf(B,C),cf(C,E),cf(E,D),cf(D,F),cf(F,G)) =

min(3 − 1,4 − 1,2 − 0,0 − − 1,6 − 3,9 − 3) =
min(2,3,2,1,3,6) = 1

A,B,C,E,D,F,G

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

Улучшенной версией А.Э.-К. является алгоритм Диница, требующий O( | V | 2 | E | ) операций.

Назовём вспомогательной бесконтурной сетью графа G с источником s его подграф, содержащий только такие рёбра (u, v), для которых минимальное расстояние от s до v на единицу больше минимального расстояния от s до u.

Алгоритм Диница:

  1. Строим минимальную бесконтурную сеть остаточного графа.

  2. Пока в сети есть путь из s в t, выполнить следующие шаги:

    1. Находим кратчайший путь из s в t. Если его нет, выйти из цикла.

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

    3. Для каждого ребра на найденном пути увеличиваем поток на cmin , а в противоположном ему — уменьшаем на cmin .

    4. Удаляем все рёбра, достигшие насыщения.

    5. Удаляем все тупики (то есть вершины, кроме стока, откуда не выходит рёбер, и вершины, кроме источника, куда рёбер не входит) вместе со всеми инцидентными им рёбрами.

    6. Повторяем предыдущий шаг, пока есть что удалять.

  3. Если найденный поток ненулевой, добавляем его к общему потоку и возвращаемся на шаг 1.

Loading

Календарь

«  Июнь 2019  »
ПнВтСрЧтПтСбВс
     12
3456789
10111213141516
17181920212223
24252627282930

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24