Изменения

'''Алгоритм Голдберга-Тарьяна''' (англ. ''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>G^0_f O(\log(N))</tex> {{---}} некоторый ациклический граф, S, T {{---}} исток и сток соответственно. Попытаемся ускорить поиск пути из S в T.

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

==Linking Cutting trees==* Начало.* '''Шаг 1'''. Пусть каждое дерево поддерживает следующие операции:<tex>U</tex> {{---}} корень дерева, в котором лежит <tex>S</tex>.# Вычисление минимума на пути от вершины до корня# Прибавить константу * '''Шаг 2'''. Если вершина <tex>U</tex> совпала с вершиной <tex>T</tex> переходим к '''шагу 6''', иначе к числам на пути от вершины до корня'''шагу 3'''.* Предположим'''Шаг 3'''. Выберем следующее ненасыщенное исходящее ребро. Если ребра нет {{---}} переходим к '''шагу 7'''. Ребра рассматриваем также, что Sкак и в алгоритме Диница, T лежат в одном дереве:с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло {{---}} больше его не рассматриваем. # Можно быстро найти пусть из S * '''Шаг 4'''. Пусть просматриваем ненасыщенное ребро, ведущее в T некоторую вершину <tex>V</tex>. Подвесим корень <tex>U</tex> через это ребро к вершине <tex>V</tex>, выполнив <tex>(Пусть по дереву до корня4)</tex> запрос.# При помощи (* '''Шаг 5'''. В <tex>U</tex> записываем число, равное остаточной пропускной способности ребра. Переходим к '''шагу 1) запроса можно найти узкое место на этом пути'''.* '''Шаг 6'''. Возвращаем найденный путь.# При помощи (2) запроса можно вычесть * '''Шаг 7'''. Пути из всех ребер на этом пути пропускную способность узкого места, прибавить ее к потоку<tex>S</tex> в <tex>T</tex> нет.* Конец. (Будем отдельно хранить дерево с потоками и дерево с пропускными способностями)

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

Дополнительные операцииПусть после <tex>(2)</tex> запроса появилось нулевое ребро.# Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо Запрос минимума от исходного дерева<tex>S</tex> до корня будет возвращать <tex>0</tex>.# Подвесить дерево. Пусть есть дерево с корнем АПоэтому, дерево с вершиной В. Операция позволяет Создать ребро из A в B и тем самым подвесить дерево к вершине.==Алгоритм==Предположимтакие ребра нужно отрезать, что такое дерево существует и умеет выполнять все операции за выполнив <tex>O(\log(N)4)</tex>запрос по этому ребру. Стоит заметить, что нулевых ребер может получиться несколько, в случае нескольких минимумов.

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

Добрались до T* Начало.* '''Шаг 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> запрос, значит нужно предусмотреть узкое место и для обычного шагапропускную способность. Если запрос из S до корня дал 0пропускная способность положительна, переходим к '''шагу 4''', то нужно это ребро отрезатьиначе к '''шагу 5'''.* '''Шаг 4'''. ''Улучшение пути''. Обновляем значения потока и пропускной способности при помощи <tex>(2)</tex> запроса.* '''Шаг 5'''. ''Удаление нулевых ребер''. Обрезаем нулевые ребра при помощи <tex>(3)</tex> запроса. Переходим к '''шагу 2'''.* Конец.

Из предположения[[Link-Cut Tree|Link-Cut 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 {{---}} Лекция А.С.Станкевича]