Просмотр исходного текста страницы Алгоритм Голдберга-Тарьяна


'''Алгоритм Голдберга-Тарьяна''' (англ. ''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>.
# Находим ребро с минимальной пропускной способностью
# Вдоль пути увеличиваем поток на минимальную пропускную способность

Попытаемся ускорить процесс поиска пути из <tex>S</tex> в <tex>T</tex>. Для этого, для каждой вершины зафиксируем какое-либо, не более, чем одно, исходящее из нее ребро. Граф ацикличен, значит зафиксированные ребра будут образовывать лес корневых деревьев. Корнем каждого дерева будет вершина, у которой нет зафиксированного ребра.
В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра.

[[Файл:Голдберг-Тарьян.граф.png |500px |thumb|center| Желтым выделены зафиксированные ребра. Тогда <tex>T</tex> {{---}} корень дерева]]

Пусть каждое дерево поддерживает следующие операции:
# Вычислить минимум на пути от вершины до корня (1).
# Прибавить константу к числам на пути от вершины до корня (2).
# Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева (3).
# Подвесить дерево. Пусть есть дерево с корнем <tex>A</tex>, дерево с вершиной <tex>B</tex>. Операция позволяет Создать ребро из <tex>A</tex> в <tex>B</tex> и тем самым подвесить дерево к вершине (4).

Заметим, что именно эти операции поддерживает [[Link-Cut Tree|Link-Cut tree]] и умеет их выполнять за <tex>O(\log(N))</tex>.

===Поиск пути===
Научимся находить путь из <tex>S</tex> в <tex>T</tex> в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями.

Пусть <tex>U</tex> {{---}} корень дерева, в котором лежит <tex>S</tex>.

* Заметим, что если <tex>S</tex>, <tex>T</tex> лежат в одном дереве, то путь ищется легко. Это путь по дереву до корня.

* Если  <tex>S</tex>, <tex>T</tex> лежат в разных деревьях. Просмотрим все ненасыщенные исходящие ребра. Будем рассматривать их также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло {{---}} больше его не рассматриваем. Пусть просматриваем какое-то ненасыщенное ребро, ведущее в некоторую вершину <tex>V</tex>:
# Подвесим корень <tex>U</tex> через это ребро к вершине <tex>V</tex>, выполнив запрос (3). 
#В <tex>U</tex> записываем число, равное остаточной пропускной способности ребра. 

* Будем повторять, пока <tex>S</tex> и <tex>T</tex> не окажутся в одном дереве.

===Улучшение пути===
Путь из <tex>S</tex> в <tex>T</tex> найден, теперь научимся улучшать путь. Нужно обновить значения пропускных способностей и потоков через вершины этого пути. Тогда:
* При помощи <tex>(1)</tex> запроса можно найти узкое место (ребро с минимальной остаточной пропускной способностью) на этом пути и его пропускную способность.
* При помощи <tex>(2)</tex> запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.

Пусть после <tex>(2)</tex> запроса появилось нулевое ребро. Запрос минимума от <tex>S</tex> до корня будет возвращать <tex>0</tex>. Поэтому, такие ребра нужно отрезать, выполнив <tex>(3)</tex> запрос по этому ребру.

===Итоговый алгоритм===

Объединим вышесказанное в алгоритм Голдберга-Татьяна. 
Пусть дана сеть. Требуется в этой сети найти поток <tex>f(S, T) </tex> максимальной величины.

# Для каждого ребра <tex>(u, v)</tex> данной сети <tex>G</tex> зададим <tex>f(u, v) = 0</tex>.
# Пока есть путь из <tex>S</tex> в <tex>T</tex>:
## Выполняем запрос <tex>(1)</tex>, находим узкое место и пропускную способность.
## Обновляем значения потока и пропускной способности при помощи запроса <tex>(2)</tex>.
## Обрезаем нулевые ребра при помощи запроса <tex>(3)</tex>.

==Время работы==
[[Link-Cut Tree|Linking-Cutting 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>

== Смотри также ==
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа|Алоритм Эдмондса-Карпа]]
* [[Алгоритм масштабирования потока|Алгоритм масштабирования потока]]
* [[Метод проталкивания предпотока|Метод проталкивания предпотока]]

== Источники информации ==
*[https://www.lektorium.tv/lecture/14408 Lektorium {{---}} Лекция А.С. Станкевича]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке ]]