Изменения

'''Алгоритм Голдберга-Тарьяна''' (англ. ''Goldberg-Tarjan'') {{---}} алгоритм, решающий задачу нахождения максимального потока в транспортной сети за <tex>O(VE \log(V))</tex>. Можно считать модификацией алгоритма Диница.==Linking Cutting treesАлгоритм=====Идея===Вспомним [[Схема алгоритма Диница|алгоритм Диница]]. Пусть есть лес деревьев. Каждая вершина знает своих родителей. Во всех вершинах записаны числа.Требуется структура данныхсеть <tex>G^0_f </tex> {{---}} некоторый ориентированный ациклический граф, которую будем использовать для поиска блокирующего потока<tex>S</tex>, которая может выполнять следующие операции<tex>T</tex> {{---}} исток и сток соответственно. Схема алгоритма Диница:# Нахождение минимума на пути от вершины до корня# Прибавление константы на пути ото вершины до корня# link. Пусть есть дерево с корнем АПри помощи [[Обход в глубину, дерево с вершиной В. Операция позволяет "подвесить" первое дерево ко второму, т.е создать ребро цвета вершин|обхода в глубину]] находим путь из А <tex>S</tex> в В<tex>T</tex>.# cut. Для некоторой выбранной вершины обрезать Находим ребро от нее к ее родителю, сделав ее новым корнем. При этом отрезанное поддерево отделяется и существует независимо от исходного дерева.с минимальной пропускной способностью# Вдоль пути увеличиваем поток на минимальную пропускную способность

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

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

Пусть нет операций link, cut. Все пути статичные, остаются 2 каждое дерево поддерживает следующие операции: # Минимум Вычислить минимум на суффиксепути от вершины до корня (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>).

Для cut и link можно использовать Декартовы деревья или Splay-деревья, операции также за ===Поиск пути===Научимся находить путь из <tex>S</tex> в <tex>O(\log(N))T</tex>в описанной выше сети при помощи леса корневых деревьев. Merge = link, split = cutБудем отдельно хранить дерево с потоками и дерево с пропускными способностями.

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

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

Научились делать делать для путейПусть после <tex>(2)</tex> запроса появилось нулевое ребро. Обе операции за logЗапрос минимума от <tex>S</tex> до корня будет возвращать <tex>0</tex>. Поэтому, такие ребра нужно отрезать, выполнив <tex>(n4)</tex> запрос по этому ребру. Стоит заметить, что нулевых ребер может получиться несколько, в случае нескольких минимумов.

===ДеревьяИтоговый алгоритм===Проблема в том, что дерево не путь и его нельзя так просто свести к структурам данных, в силу нелинейности индексов. Но можно дерево нарезать на пути. Рассмотрим корневое дерево, на котором хотим выполнять операции. Забудем про (link), (cut). Только первые 2 операции.Существует подход, который позволяет сделать за log(n)^2.

HeavyОбъединим вышесказанное в алгоритм Голдберга-Light DecompositionТарьяна. Пусть дана сеть. Требуется в этой сети найти поток <tex>f(S, T) </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'''. Тогда несложно заметить* Конец.

Лемма. На пути от любой вершины до корня не больше log(N) легких ребер. Потому что каждый раз когда мы идем по легкому ребру, размер поддерева той вершины, в которой мы находимся, размер поддерева увеличивается хотя бы в два раза. Потому что если увеличился меньше, чем в два раза, значит здесь было больше половины потомков следующей вершины, значит это ребро было тяжелым. Значит легких ребер мало, а тяжелых много. Тяжелые ребра образуют разбиение дерева на пути. Чтобы решить наши задачи делаем так:# Начинаем в какой-то вершине, берем тот путь к которому она принадлежит (Тот фрагмент от вершины до конца тяжелого пути)# Делаем шаг по легкому пути# Берем снова часть тяжелого пути# и т.д, пока не дойдем до корня. Тогда запрос на суффиксе пути будет за log(N). Каждый раз, когда меняем путь - проходим по легкому пути. Т.к по лемме их не больше log(N), то суммарное время запроса log(n)^2. Если добавить link, cut, то тяжело поддерживать, какое ребро легкое какое тяжелое. Жд этого нужно аккуратно следить за деревьями. Потому что при подвешивании дерева, абсолютно любое ребро на пути от вершины до корня может стать легким или тяжелым. Это неудобно. Применим метод как в TANGO-деревьях. Когда есть запрос для какого-то пути, мы сначала перестроим пути так, чтоб путь от вершины до корня был полностью из жирных (solid) ребер. ==ИдеяВремя работы==Рассмотрим [[Схема алгоритма ДиницаLink-Cut Tree|Алгоритм ДиницаLink-Cut tree]]. Его схема такова:# При помощи [[Обход в глубину, цвета вершин|обхода в глубину]] находим путь.# Вдоль него увеличиваем потом на минимальную пропускную способность  Рассмотрим сеть выполняет все вышеописанные запросы за <tex>G^0_f O(\log(N))</tex> {{---}} некоторый ациклический граф, S, T {{---}} исток и сток соответственно. Попытаемся ускорить поиск пути из S в Tоценим время работы алгоритма.

* Для каждой вершины зафиксируем какое-либоОчевидно, не более чем одночто просмотров ребер суммарно <tex>O(E)</tex>, исходящее из нее ребро. Ткак и в алгоритме Диница.Переход к граф ацикличен, то зафиксированные ребра будут образовывать лес корневых деревьев, где следующему ребру происходит в корне находится вершина, у которой зафиксированного ребра нетследующих случаях:# Просматриваемое ребро насыщено.# Дерево разрезается по нулевому ребру.* В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра# Ребро не лежит в сети кратчайших путей.

==Linking Cutting trees==* Пусть каждое дерево поддерживает следующие операции:# Вычисление минимума на пути от вершины до корня# Прибавить константу к числам на пути от вершины до корня.* Предположим, что S, T лежат в одном дереве:# Можно быстро найти пусть из S в T На каждый просмотр тратится не <tex>O(Пусть по дереву до корня1)# При помощи </tex> а <tex>O(1\log(V)) запроса можно найти узкое место </tex>, потому что перед тем, как посмотреть на этом путиследующее ребро делается запрос.# При помощи Значит время работы этой части {{---}} <tex>O(2E \log(V) запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, прибавить ее к потоку)</tex>. (Будем отдельно хранить дерево с потоками и дерево с пропускными способностями)

НоСледующий шаг в алгоритме Диница {{---}} сумма длин путей. Раньше считалось за <tex>O(V^2)</tex>, даже если S и T попали так как на каждый путь обход в одно деревоглубину тратил время, пропорциональное длине этого пути. Сейчас тратится только <tex>O(\log(V))</tex> на следующем шаге запрос минимумакаждый путь. Если путь найден, очевиднозначит до него дошли, выдаст 0значит это соответствует одному запросу. Потому что Поэтому тратим на предыдущем шаге этот минимум был вычтен и при помощи текущего дерева ничего улучшить уже не удастсякаждый путь тоже логарифм <tex>O(\log(V))</tex>.

Дополнительные операцииТогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O((V + E) \log(V))</tex>.# Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева.# Подвесить дерево. Пусть есть дерево с корнем АИ, суммарно, дерево с вершиной В. Операция позволяет Создать ребро из A если подставить в B и тем самым подвесить дерево к вершине.==Алгоритм==Предположим, что такое дерево существует и умеет выполнять все операции за алгоритм Диница будем иметь ассимптотику <tex>O(VE \log(NV))</tex>.

Хотим найти путь из S в T. Делаем (1) запрос== См. Получаем корень, минимум до корня, его расположение. Если корень {{также ==* [[Алгоритм Форда---}} TФалкерсона, то делаем как раньше. Иначе: Просматриваем все ненасыщенные исходящие ребра (как и реализация с помощью поиска в алгоритме Диница, если просматривали раньше и не подошлоглубину|Алгоритм Форда-Фалкерсона, то не рассматриваем больше. Т.е реализация с глобальным итератором, начиная с последнего подошедшего). Пусть просматриваем какое-то ненасыщеюнное ребро, ведущее в некоторую вершину. Подвешиваем наше дерево к этому ребру и помощью поиска в бывший корень записываем число, равное остаточной пропускной способности этого ребра. ( Это легко сделать при помощи выполнения (2) операции к самому корню до подвешивания. Пусть было INF, прибавим Value глубину]]* [[Алоритм Эдмондса- INF Карпа|Алоритм Эдмондса-> PROFIT).Карпа]]* [[Алгоритм масштабирования потока|Алгоритм масштабирования потока]]* [[Метод проталкивания предпотока|Метод проталкивания предпотока]]

Далее, снова пополняем запрос из S... и ТД, пока не доберемся до T. Добрались до T. Делаем операцию улучшения пути, появилось нулевое ребро. Обрезаем его. Продолжаем спрашивать из S. Нулевых ребер может быть несколько, значит нужно предусмотреть и для обычного шага. Если запрос из S до корня дал 0, то нужно это ребро отрезать. ==Время работыИсточники информации ==Из предположения, что есть структура данных.Просмотров ребра суммарно О(Е), аналогично алгоритму Диница*[https://www. Переход к следующему, когда смотрим на ребро и оно насыщено, когда ребро разрезаем, когда смотрим на ребро и оно не лежит в сети кратчайших путейlektorium. На каждый просмотр тратится не О(1) а О(log), потому что делаем запрос перед тем как посмотреть на следующее реброtv/lecture/14408 Lektorium {{---}} Лекция А. Значит O(E log(V))С.Станкевича]