18
правок
Изменения
м
# * При помощи <tex>(1)</tex> запроса можно найти узкое место (ребро с минимальной остаточной пропускной способностью) на этом пути и его пропускную способность.# * При помощи <tex>(2)</tex> запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.
# * Начало.* '''Шаг 1'''. Для каждого ребра <tex>(u, v)</tex> данной сети <tex>G</tex> зададим <tex>f(u, v) = 0</tex>.# Пока * '''Шаг 2'''. Если есть путь из <tex>S</tex> в <tex>T</tex>:{{---}} переходим к '''шагу 3'''.## * '''Шаг 3'''. Выполняем запрос <tex>(1)</tex>запрос, находим узкое место и пропускную способность. Если пропускная способность положительна, переходим к '''шагу 4''', иначе к '''шагу 5'''.## * '''Шаг 4'''. ''Улучшение пути''. Обновляем значения потока и пропускной способности при помощи запроса <tex>(2)</tex>запроса.## * '''Шаг 5'''. ''Удаление нулевых ребер''. Обрезаем нулевые ребра при помощи запроса <tex>(3)</tex>запроса. Переходим к '''шагу 2'''.* Конец.
→Поиск пути: typo
'''Алгоритм Голдберга-Тарьяна''' (англ. ''Goldberg-Tarjan'') {{---}} алгоритм, решающий задачу нахождения максимального потока в транспортной сети за <tex>O(VE \log(V))</tex>. Можно считать модификацией алгоритма Диница.
==Алгоритм=====Идея===Вспомним [[Схема алгоритма Диница|алгоритм Диница]]. Пусть есть сеть <tex>G^0_f </tex> {{---}} некоторый ориентированный ациклический граф, <tex>S</tex>, <tex>T</tex> {{---}} исток и сток соответственно. Схема Алгоритма алгоритма Диница :
# При помощи [[Обход в глубину, цвета вершин|обхода в глубину]] находим путь из <tex>S</tex> в <tex>T</tex>.
# Находим ребро с минимальной пропускной способностью
Заметим, что именно эти операции поддерживает [[Link-Cut Tree|Link-Cut tree]] и умеет их выполнять за <tex>O(\log(N))</tex>.
===Поиск пути===
Научимся находить путь из <tex>S</tex> в <tex>T</tex> в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями.
* Начало.* '''Шаг 1'''. Пусть <tex>U</tex> {{---}} корень дерева, в котором лежит <tex>S</tex>. * Заметим, что если '''Шаг 2'''. Если вершина <tex>SU</tex>, совпала с вершиной <tex>T</tex> лежат в одном деревепереходим к '''шагу 6''', то путь ищется легко. Это путь по дереву до корняиначе к '''шагу 3'''. * '''Шаг 3'''. Выберем следующее ненасыщенное исходящее ребро. Если <tex>S</tex>, <tex>T</tex> лежат в разных деревьях. Просмотрим все ненасыщенные исходящие ребранет {{---}} переходим к '''шагу 7'''. Будем рассматривать их Ребра рассматриваем также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло {{---}} больше его не рассматриваем. * '''Шаг 4'''. Пусть просматриваем какое-то ненасыщенное ребро, ведущее в некоторую вершину <tex>V</tex>:# . Подвесим корень <tex>U</tex> через это ребро к вершине <tex>V </tex>, выполнив <tex>(Операция 34)</tex> запрос. #* '''Шаг 5'''. В <tex>U</tex> записываем число, равное остаточной пропускной способности ребра. Переходим к '''шагу 1'''. * '''Шаг 6'''. Возвращаем найденный путь.* Будем повторять, пока '''Шаг 7'''. Пути из <tex>S</tex> и в <tex>T</tex> не окажутся в одном деревенет.* Конец.
===Улучшение пути===
Путь из <tex>S</tex> в <tex>T</tex> найден, теперь научимся улучшать путь. Нужно обновить значения пропускных способностей и потоков через вершины этого пути. Тогда:
Пусть после <tex>(2)</tex> запроса появилось нулевое ребро. Запрос минимума от <tex>S</tex> до корня будет возвращать <tex>0</tex>. Поэтому, такие ребра нужно отрезать, выполнив <tex>(34)</tex> запрос по этому ребру. Стоит заметить, что нулевых ребер может получиться несколько, в случае нескольких минимумов.
==Алгоритм=Итоговый алгоритм===
Объединим вышесказанное в алгоритм Голдберга-ТатьянаТарьяна.
Пусть дана сеть. Требуется в этой сети найти поток <tex>f(S, T) </tex> максимальной величины.
==Время работы==
[[Link-Cut Tree|LinkingLink-Cutting TreeCut tree]] выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма.
Очевидно, что просмотров ребер суммарно <tex>O(E)</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:
# просматриваемое Просматриваемое ребро насыщено.# дерево Дерево разрезается по нулевому ребру.# ребро Ребро не лежит в сети кратчайших путей.
На каждый просмотр тратится не <tex>O(1)</tex> а <tex>O(\log(V))</tex>, потому что перед тем, как посмотреть на следующее ребро делается запрос. Значит время работы этой части {{---}} <tex>O(E \log(V))</tex>.
Следующий шаг в алгоритме Диница {{---}} сумма длин путей. Раньше считалось за <tex>O(V^2)</tex>, так как на каждый путь обход в глубину тратил время, пропорциональное длине этого пути. Сейчас тратится только <tex>O(\log(V))</tex> на каждый путь. Если путь найден, значит до него дошли, значит это соответствует одному запросу. Поэтому тратим на каждый путь тоже логарифм <tex>O(\log(V))</tex>.
Тогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O((V + E) \log(V))</tex>. И, суммарно, если подставить в алгоритм Диница будем иметь ассимптотику <tex>O(VE \log(V)) </tex>. == Смотри См. также ==
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа|Алоритм Эдмондса-Карпа]]
* [[Алгоритм масштабирования потока|Алгоритм масштабирования потока]]
* [[Метод проталкивания предпотока|Метод проталкивания предпотока]]
== Источники информации ==
