Изменения

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

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

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

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

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

* Начало.* '''Шаг 1'''. Пусть <tex>U </tex> {{- --}} корень дерева, в котором лежит <tex>S</tex>.* '''Шаг 2'''. Если вершина <tex>U</tex> совпала с вершиной <tex>T</tex> переходим к '''шагу 6''', иначе к '''шагу 3'''.* '''Шаг 3'''. Выберем следующее ненасыщенное исходящее ребро. Если ребра нет {{---}} переходим к '''шагу 7'''. Ребра рассматриваем также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло {{---}} больше его не рассматриваем. * '''Шаг 4'''. Пусть просматриваем ненасыщенное ребро, ведущее в некоторую вершину <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> нет.* Конец.

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

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

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

==АлгоритмВремя работы==[[Link-Cut Tree|Link-Cut tree]] выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма.

Объединим вышесказанное в Алгоритм Голдберга-Татьяна. Пусть дана сеть. Требуется в этой сети найти поток Очевидно, что просмотров ребер суммарно <tex>fO(S, TE) </tex> максимальной величины, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:# Просматриваемое ребро насыщено.# Дерево разрезается по нулевому ребру.# Ребро не лежит в сети кратчайших путей.

# Для каждого ребра На каждый просмотр тратится не <tex>O(u, v1)</tex> данной сети а <tex>GO(\log(V))</tex> зададим , потому что перед тем, как посмотреть на следующее ребро делается запрос. Значит время работы этой части {{---}} <tex>fO(u, vE \log(V)) = 0</tex># Пока есть путь из S в T:## Выполняем запрос (1), находим узкое место и пропускную способность## Обновляем значения потока и пропускной способности при помощи запроса (2)## Обрезаем нулевые ребра при помощи запроса (4).

==Время работы==[[LinkСледующий шаг в алгоритме Диница {{-Cut Tree|Linking-Cutting Tree]] выполняет все вышеописанные запросы -}} сумма длин путей. Раньше считалось за <tex>O(V^2)</tex>, так как на каждый путь обход в глубину тратил время, пропорциональное длине этого пути. Сейчас тратится только <tex>O(\log(NV))</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>. Переход к следующему ребру происходит в следующих случаях:# просматриваемое ребро насыщено# дерево разрезается по нулевому ребру# ребро не лежит в сети кратчайших путей

На каждый просмотр тратится не <tex>O(1)</tex> а <tex>O(\log(V))</tex>== См. также ==* [[Алгоритм Форда-Фалкерсона, потому что перед темреализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона, как посмотреть на следующее ребро делается запрос. Значит время работы этой части {{реализация с помощью поиска в глубину]]* [[Алоритм Эдмондса-Карпа|Алоритм Эдмондса--}} <tex>O(E \log(V))</tex>.Карпа]]* [[Алгоритм масштабирования потока|Алгоритм масштабирования потока]]* [[Метод проталкивания предпотока|Метод проталкивания предпотока]]

Следующий шаг в алгоритме Диница - сумма длин путей. Раньше считалось за <tex>O(V^2)<== Источники информации ==*[https://tex>www. Потому, что на каждый путь DFS тратил время, пропорциональное длине этого путиlektorium. Сейчас тратится только <tex>O(\log(V))<tv/tex> на каждый путь. Если путь найден, значит до него дошли, значит это соответствует одному запросуlecture/14408 Lektorium {{---}} Лекция А. Поэтому тратим на каждый путь тоже логарифм <tex>O(\log(V))</tex>С.Станкевича]