Изменения

'''Алгоритм Голдберга-Тарьяна''' (англ. ''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 операции.

* Начало.* '''Шаг 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'''.* Конец.

Рассмотрим сеть <tex>G^0_f </tex> {{---}} некоторый ациклический граф, S, T {{---}} исток и сток соответственно. Попытаемся ускорить поиск пути из S в T. * Для каждой вершины зафиксируем какое-либо, не более чем одно, исходящее из нее ребро. Т.к граф ацикличен, то зафиксированные ребра будут образовывать лес корневых деревьев, где в корне находится вершина, у которой зафиксированного ребра нет.* В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра. ==Linking Cutting treesВремя работы==* Пусть каждое дерево поддерживает следующие операции:# Вычисление минимума на пути от вершины до корня# Прибавить константу к числам на пути от вершины до корня.* Предположим, что S, T лежат в одном дереве:# Можно быстро найти пусть из S в T [[Link-Cut Tree|Link-Cut tree]] выполняет все вышеописанные запросы за <tex>O(Пусть по дереву до корня)# При помощи \log(1N) запроса можно найти узкое место на этом пути.# При помощи (2) запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места</tex>, прибавить ее к потокуоценим время работы алгоритма. (Будем отдельно хранить дерево с потоками и дерево с пропускными способностями)

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

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

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

ДалееТогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O((V + E) \log(V))</tex>. И, снова пополняем запрос из S... и ТДсуммарно, пока не доберемся до Tесли подставить в алгоритм Диница будем иметь ассимптотику <tex>O(VE \log(V)) </tex>.

Добрались до T== См. Делаем операцию улучшения путитакже ==* [[Алгоритм Форда-Фалкерсона, появилось нулевое ребро. Обрезаем его. Продолжаем спрашивать из S. Нулевых ребер может быть несколько, значит нужно предусмотреть и для обычного шага. Если запрос из S до корня дал 0реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона, то нужно это ребро отрезать.реализация с помощью поиска в глубину]]* [[Алоритм Эдмондса-Карпа|Алоритм Эдмондса-Карпа]]* [[Алгоритм масштабирования потока|Алгоритм масштабирования потока]]* [[Метод проталкивания предпотока|Метод проталкивания предпотока]]

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