Редактирование: Алгоритм Голдберга-Тарьяна

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 24: Строка 24:
 
Научимся находить путь из <tex>S</tex> в <tex>T</tex> в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями.
 
Научимся находить путь из <tex>S</tex> в <tex>T</tex> в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями.
  
* Начало.
+
* Начало
 
* '''Шаг 1'''. Пусть <tex>U</tex> {{---}} корень дерева, в котором лежит <tex>S</tex>.
 
* '''Шаг 1'''. Пусть <tex>U</tex> {{---}} корень дерева, в котором лежит <tex>S</tex>.
 
* '''Шаг 2'''. Если вершина <tex>U</tex> совпала с вершиной <tex>T</tex> переходим к '''шагу 6''', иначе к '''шагу 3'''.
 
* '''Шаг 2'''. Если вершина <tex>U</tex> совпала с вершиной <tex>T</tex> переходим к '''шагу 6''', иначе к '''шагу 3'''.
* '''Шаг 3'''. Выберем следующее ненасыщенное исходящее ребро. Если ребра нет {{---}} переходим к '''шагу 7'''. Ребра рассматриваем также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло {{---}} больше его не рассматриваем.  
+
* '''Шаг 3'''. Выберем следующее ненасыщеюнное исходящее ребро. Если ребра нет {{---}} переходим к '''шагу 7'''. Ребра рассматриваем также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло {{---}} больше его не рассматриваем.  
 
* '''Шаг 4'''. Пусть просматриваем ненасыщенное ребро, ведущее в некоторую вершину <tex>V</tex>. Подвесим корень <tex>U</tex> через это ребро к вершине <tex>V</tex>, выполнив <tex>(4)</tex> запрос.
 
* '''Шаг 4'''. Пусть просматриваем ненасыщенное ребро, ведущее в некоторую вершину <tex>V</tex>. Подвесим корень <tex>U</tex> через это ребро к вершине <tex>V</tex>, выполнив <tex>(4)</tex> запрос.
 
* '''Шаг 5'''. В <tex>U</tex> записываем число, равное остаточной пропускной способности ребра. Переходим к '''шагу 1'''.
 
* '''Шаг 5'''. В <tex>U</tex> записываем число, равное остаточной пропускной способности ребра. Переходим к '''шагу 1'''.
 
* '''Шаг 6'''. Возвращаем найденный путь.
 
* '''Шаг 6'''. Возвращаем найденный путь.
 
* '''Шаг 7'''. Пути из <tex>S</tex> в <tex>T</tex> нет.
 
* '''Шаг 7'''. Пути из <tex>S</tex> в <tex>T</tex> нет.
* Конец.
+
* Конец
  
 
===Улучшение пути===
 
===Улучшение пути===
Строка 39: Строка 39:
 
* При помощи <tex>(2)</tex> запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.
 
* При помощи <tex>(2)</tex> запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.
  
Пусть после <tex>(2)</tex> запроса появилось нулевое ребро. Запрос минимума от <tex>S</tex> до корня будет возвращать <tex>0</tex>. Поэтому, такие ребра нужно отрезать, выполнив <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> максимальной величины.
  
* Начало.
+
* Начало
 
* '''Шаг 1'''.  Для каждого ребра <tex>(u, v)</tex> данной сети <tex>G</tex> зададим <tex>f(u, v) = 0</tex>.
 
* '''Шаг 1'''.  Для каждого ребра <tex>(u, v)</tex> данной сети <tex>G</tex> зададим <tex>f(u, v) = 0</tex>.
 
* '''Шаг 2'''.  Если есть путь из <tex>S</tex> в <tex>T</tex> {{---}} переходим к '''шагу 3'''.
 
* '''Шаг 2'''.  Если есть путь из <tex>S</tex> в <tex>T</tex> {{---}} переходим к '''шагу 3'''.
Строка 52: Строка 52:
 
* '''Шаг 4'''.  ''Улучшение пути''. Обновляем значения потока и пропускной способности при помощи <tex>(2)</tex> запроса.
 
* '''Шаг 4'''.  ''Улучшение пути''. Обновляем значения потока и пропускной способности при помощи <tex>(2)</tex> запроса.
 
* '''Шаг 5'''.  ''Удаление нулевых ребер''. Обрезаем нулевые ребра при помощи <tex>(3)</tex> запроса. Переходим к '''шагу 2'''.
 
* '''Шаг 5'''.  ''Удаление нулевых ребер''. Обрезаем нулевые ребра при помощи <tex>(3)</tex> запроса. Переходим к '''шагу 2'''.
* Конец.
+
* Конец
  
 
==Время работы==
 
==Время работы==
[[Link-Cut Tree|Link-Cut tree]]  выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма.
+
[[Link-Cut Tree|Linking-Cutting Tree]]  выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма.
  
 
Очевидно, что просмотров ребер суммарно <tex>O(E)</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:
 
Очевидно, что просмотров ребер суммарно <tex>O(E)</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:
Строка 68: Строка 68:
 
Тогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O((V + E) \log(V))</tex>. И, суммарно, если подставить в алгоритм Диница будем иметь ассимптотику <tex>O(VE \log(V)) </tex>.
 
Тогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O((V + E) \log(V))</tex>. И, суммарно, если подставить в алгоритм Диница будем иметь ассимптотику <tex>O(VE \log(V)) </tex>.
  
== См. также ==
+
== Смотри также ==
 
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 
* [[Алоритм Эдмондса-Карпа|Алоритм Эдмондса-Карпа]]
 
* [[Алоритм Эдмондса-Карпа|Алоритм Эдмондса-Карпа]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: