Алгоритм Голдберга-Тарьяна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Поиск пути: typo)
 
(не показано 48 промежуточных версий 3 участников)
Строка 1: Строка 1:
  
'''Алгоритм Голдберга-Тарьяна''' (англ ''Goldberg-Tarjan'') - алгоритм, решающий задачу нахождения максимального потока в транспортной сети за <tex>O(VE \log(VE))</tex>. Можно считать модификацией Алгоритма Диница.
+
'''Алгоритм Голдберга-Тарьяна''' (англ. ''Goldberg-Tarjan'') {{---}} алгоритм, решающий задачу нахождения максимального потока в транспортной сети за <tex>O(VE \log(V))</tex>. Можно считать модификацией алгоритма Диница.
==Идея==
+
==Алгоритм==
Вспомним [[Схема алгоритма Диница|Алгоритм Диница]]. Пусть есть сеть <tex>G^0_f </tex>  {{---}} некоторый ациклический граф, <tex>S</tex>, <tex>T</tex> {{---}} исток и сток соответственно. Схема Алгоритма Диница :
+
===Идея===
 +
Вспомним [[Схема алгоритма Диница|алгоритм Диница]]. Пусть есть сеть <tex>G^0_f </tex>  {{---}} некоторый ориентированный ациклический граф, <tex>S</tex>, <tex>T</tex> {{---}} исток и сток соответственно. Схема алгоритма Диница:
 
# При помощи [[Обход в глубину, цвета вершин|обхода в глубину]] находим путь из <tex>S</tex> в <tex>T</tex>.
 
# При помощи [[Обход в глубину, цвета вершин|обхода в глубину]] находим путь из <tex>S</tex> в <tex>T</tex>.
 
# Находим ребро с минимальной пропускной способностью
 
# Находим ребро с минимальной пропускной способностью
Строка 9: Строка 10:
 
Попытаемся ускорить процесс поиска пути из <tex>S</tex> в <tex>T</tex>. Для этого, для каждой вершины зафиксируем какое-либо, не более, чем одно, исходящее из нее ребро. Граф ацикличен, значит зафиксированные ребра будут образовывать лес корневых деревьев. Корнем каждого дерева будет вершина, у которой нет зафиксированного ребра.
 
Попытаемся ускорить процесс поиска пути из <tex>S</tex> в <tex>T</tex>. Для этого, для каждой вершины зафиксируем какое-либо, не более, чем одно, исходящее из нее ребро. Граф ацикличен, значит зафиксированные ребра будут образовывать лес корневых деревьев. Корнем каждого дерева будет вершина, у которой нет зафиксированного ребра.
 
В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра.
 
В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра.
 +
 +
[[Файл:Голдберг-Тарьян.граф.png |500px |thumb|center| Желтым выделены зафиксированные ребра. Тогда <tex>T</tex> {{---}} корень дерева]]
  
 
Пусть каждое дерево поддерживает следующие операции:
 
Пусть каждое дерево поддерживает следующие операции:
# Вычислить минимум на пути от вершины до корня
+
# Вычислить минимум на пути от вершины до корня (1).
# Прибавить константу к числам на пути от вершины до корня.
+
# Прибавить константу к числам на пути от вершины до корня (2).
# Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева.
+
# Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева (3).
# Подвесить дерево. Пусть есть дерево с корнем <tex>А</tex>, дерево с вершиной <tex>В</tex>. Операция позволяет Создать ребро из <tex>A</tex> в <tex>B</tex> и тем самым подвесить дерево к вершине.
+
# Подвесить дерево. Пусть есть дерево с корнем <tex>A</tex>, дерево с вершиной <tex>B</tex>. Операция позволяет Создать ребро из <tex>A</tex> в <tex>B</tex> и тем самым подвесить дерево к вершине (4).
  
Заметим, что именно эти операции поддерживает [[Link-Cut Tree|Linking-Cutting Tree]] и умеет их выполнять за <tex>O(\log(N))</tex>
+
Заметим, что именно эти операции поддерживает [[Link-Cut Tree|Link-Cut tree]] и умеет их выполнять за <tex>O(\log(N))</tex>.
  
==Поиск пути==
+
===Поиск пути===
 
Научимся находить путь из <tex>S</tex> в <tex>T</tex> в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями.
 
Научимся находить путь из <tex>S</tex> в <tex>T</tex> в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями.
  
Пусть <tex>U</tex> {{---}} корень дерева, в котором лежит <tex>S</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>S</tex>, <tex>T</tex> лежат в разных деревьях. Просмотрим все ненасыщенные исходящие ребра. Будем рассматривать их также, как и в Алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло - больше его не рассматриваем. Пусть просматриваем какое-то ненасыщенное ребро, ведущее в некоторую вершину <tex>V</tex>:
 
# Подвесим корень <tex>U</tex> через это ребро к вершине V (Операция 3).
 
#В <tex>U</tex> записываем число, равное остаточной пропускной способности ребра.
 
 
 
* Будем повторять, пока <tex>S</tex> и <tex>T</tex> не окажутся в одном дереве.
 
 
 
==Улучшение пути==
 
 
Путь из <tex>S</tex> в <tex>T</tex> найден, теперь научимся улучшать путь. Нужно обновить значения пропускных способностей и потоков через вершины этого пути. Тогда:
 
Путь из <tex>S</tex> в <tex>T</tex> найден, теперь научимся улучшать путь. Нужно обновить значения пропускных способностей и потоков через вершины этого пути. Тогда:
# При помощи <tex>(1)</tex> запроса можно найти узкое место на этом пути и его пропускную способность.
+
* При помощи <tex>(1)</tex> запроса можно найти узкое место (ребро с минимальной остаточной пропускной способностью) на этом пути и его пропускную способность.
# При помощи <tex>(2)</tex> запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.
+
* При помощи <tex>(2)</tex> запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.
  
Пусть после <tex>(2)</tex> запроса появилось нулевое ребро. Запрос минимума от <tex>S</tex> до корня будет возвращать 0. Поэтому, такие ребра нужно отрезать, выполнив <tex>(4)</tex> запрос по этому ребру.
+
Пусть после <tex>(2)</tex> запроса появилось нулевое ребро. Запрос минимума от <tex>S</tex> до корня будет возвращать <tex>0</tex>. Поэтому, такие ребра нужно отрезать, выполнив <tex>(4)</tex> запрос по этому ребру. Стоит заметить, что нулевых ребер может получиться несколько, в случае нескольких минимумов.
  
==Алгоритм==
+
===Итоговый алгоритм===
  
Объединим вышесказанное в Алгоритм Голдберга-Татьяна.  
+
Объединим вышесказанное в алгоритм Голдберга-Тарьяна.  
 
Пусть дана сеть. Требуется в этой сети найти поток <tex>f(S, T) </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>:
+
* '''Шаг 1'''.  Для каждого ребра <tex>(u, v)</tex> данной сети <tex>G</tex> зададим <tex>f(u, v) = 0</tex>.
## Выполняем запрос <tex>(1)</tex>, находим узкое место и пропускную способность
+
* '''Шаг 2'''.  Если есть путь из <tex>S</tex> в <tex>T</tex> {{---}} переходим к '''шагу 3'''.
## Обновляем значения потока и пропускной способности при помощи запроса <tex>(2)</tex>
+
* '''Шаг 3'''.  Выполняем <tex>(1)</tex> запрос, узкое место и пропускную способность. Если пропускная способность положительна, переходим  к '''шагу 4''', иначе к '''шагу 5'''.
## Обрезаем нулевые ребра при помощи запроса <tex>(4)</tex>
+
* '''Шаг 4'''.  ''Улучшение пути''. Обновляем значения потока и пропускной способности при помощи <tex>(2)</tex> запроса.
 +
* '''Шаг 5'''.  ''Удаление нулевых ребер''. Обрезаем нулевые ребра при помощи <tex>(3)</tex> запроса. Переходим к '''шагу 2'''.
 +
* Конец.
  
 
==Время работы==
 
==Время работы==
[[Link-Cut Tree|Linking-Cutting Tree]]  выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма.
+
[[Link-Cut Tree|Link-Cut tree]]  выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма.
  
Очевидно, что просмотров ребер суммарно <tex>O(\log(E))</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:
+
Очевидно, что просмотров ребер суммарно <tex>O(E)</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:
# просматриваемое ребро насыщено
+
# Просматриваемое ребро насыщено.
# дерево разрезается по нулевому ребру
+
# Дерево разрезается по нулевому ребру.
# ребро не лежит в сети кратчайших путей
+
# Ребро не лежит в сети кратчайших путей.
  
 
На каждый просмотр тратится не <tex>O(1)</tex> а <tex>O(\log(V))</tex>, потому что перед тем, как посмотреть на следующее ребро делается запрос. Значит время работы этой части {{---}}  <tex>O(E \log(V))</tex>.
 
На каждый просмотр тратится не <tex>O(1)</tex> а <tex>O(\log(V))</tex>, потому что перед тем, как посмотреть на следующее ребро делается запрос. Значит время работы этой части {{---}}  <tex>O(E \log(V))</tex>.
  
Следующий шаг в алгоритме Диница - сумма длин путей. Раньше считалось за <tex>O(V^2)</tex>. Потому, что на каждый путь DFS тратил время, пропорциональное длине этого пути. Сейчас тратится только <tex>O(\log(V))</tex>  на каждый путь. Если путь найден, значит до него дошли, значит это соответствует одному запросу. Поэтому тратим на каждый путь тоже логарифм <tex>O(\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 {{---}} Лекция А.С. Станкевича]
  
Тогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O(VE \log(VE))</tex>
+
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Задача о максимальном потоке ]]

Текущая версия на 22:15, 31 марта 2017

Алгоритм Голдберга-Тарьяна (англ. Goldberg-Tarjan) — алгоритм, решающий задачу нахождения максимального потока в транспортной сети за [math]O(VE \log(V))[/math]. Можно считать модификацией алгоритма Диница.

Алгоритм[править]

Идея[править]

Вспомним алгоритм Диница. Пусть есть сеть [math]G^0_f [/math] — некоторый ориентированный ациклический граф, [math]S[/math], [math]T[/math] — исток и сток соответственно. Схема алгоритма Диница:

  1. При помощи обхода в глубину находим путь из [math]S[/math] в [math]T[/math].
  2. Находим ребро с минимальной пропускной способностью
  3. Вдоль пути увеличиваем поток на минимальную пропускную способность

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

Желтым выделены зафиксированные ребра. Тогда [math]T[/math] — корень дерева

Пусть каждое дерево поддерживает следующие операции:

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

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

Поиск пути[править]

Научимся находить путь из [math]S[/math] в [math]T[/math] в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями.

  • Начало.
  • Шаг 1. Пусть [math]U[/math] — корень дерева, в котором лежит [math]S[/math].
  • Шаг 2. Если вершина [math]U[/math] совпала с вершиной [math]T[/math] переходим к шагу 6, иначе к шагу 3.
  • Шаг 3. Выберем следующее ненасыщенное исходящее ребро. Если ребра нет — переходим к шагу 7. Ребра рассматриваем также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло — больше его не рассматриваем.
  • Шаг 4. Пусть просматриваем ненасыщенное ребро, ведущее в некоторую вершину [math]V[/math]. Подвесим корень [math]U[/math] через это ребро к вершине [math]V[/math], выполнив [math](4)[/math] запрос.
  • Шаг 5. В [math]U[/math] записываем число, равное остаточной пропускной способности ребра. Переходим к шагу 1.
  • Шаг 6. Возвращаем найденный путь.
  • Шаг 7. Пути из [math]S[/math] в [math]T[/math] нет.
  • Конец.

Улучшение пути[править]

Путь из [math]S[/math] в [math]T[/math] найден, теперь научимся улучшать путь. Нужно обновить значения пропускных способностей и потоков через вершины этого пути. Тогда:

  • При помощи [math](1)[/math] запроса можно найти узкое место (ребро с минимальной остаточной пропускной способностью) на этом пути и его пропускную способность.
  • При помощи [math](2)[/math] запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.

Пусть после [math](2)[/math] запроса появилось нулевое ребро. Запрос минимума от [math]S[/math] до корня будет возвращать [math]0[/math]. Поэтому, такие ребра нужно отрезать, выполнив [math](4)[/math] запрос по этому ребру. Стоит заметить, что нулевых ребер может получиться несколько, в случае нескольких минимумов.

Итоговый алгоритм[править]

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

  • Начало.
  • Шаг 1. Для каждого ребра [math](u, v)[/math] данной сети [math]G[/math] зададим [math]f(u, v) = 0[/math].
  • Шаг 2. Если есть путь из [math]S[/math] в [math]T[/math] — переходим к шагу 3.
  • Шаг 3. Выполняем [math](1)[/math] запрос, узкое место и пропускную способность. Если пропускная способность положительна, переходим к шагу 4, иначе к шагу 5.
  • Шаг 4. Улучшение пути. Обновляем значения потока и пропускной способности при помощи [math](2)[/math] запроса.
  • Шаг 5. Удаление нулевых ребер. Обрезаем нулевые ребра при помощи [math](3)[/math] запроса. Переходим к шагу 2.
  • Конец.

Время работы[править]

Link-Cut tree выполняет все вышеописанные запросы за [math]O(\log(N))[/math], оценим время работы алгоритма.

Очевидно, что просмотров ребер суммарно [math]O(E)[/math], как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:

  1. Просматриваемое ребро насыщено.
  2. Дерево разрезается по нулевому ребру.
  3. Ребро не лежит в сети кратчайших путей.

На каждый просмотр тратится не [math]O(1)[/math] а [math]O(\log(V))[/math], потому что перед тем, как посмотреть на следующее ребро делается запрос. Значит время работы этой части — [math]O(E \log(V))[/math].

Следующий шаг в алгоритме Диница — сумма длин путей. Раньше считалось за [math]O(V^2)[/math], так как на каждый путь обход в глубину тратил время, пропорциональное длине этого пути. Сейчас тратится только [math]O(\log(V))[/math] на каждый путь. Если путь найден, значит до него дошли, значит это соответствует одному запросу. Поэтому тратим на каждый путь тоже логарифм [math]O(\log(V))[/math].

Тогда имеем ассимптотику [math]O(E\log(V) + V \log(V)) = O((V + E) \log(V))[/math]. И, суммарно, если подставить в алгоритм Диница будем иметь ассимптотику [math]O(VE \log(V)) [/math].

См. также[править]

Источники информации[править]