Алгоритм Голдберга-Тарьяна - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:26:17Z

rollbackEdits.php mass rollback

103.251.167.21 в 04:58, 1 сентября 2022

2022-09-01T04:58:37Z

Vitalik: /* Поиск пути */ typo

2017-03-31T19:15:55Z

‎Поиск пути: typo

Shersh: /* Смотри также */

2016-01-04T17:49:44Z

‎Смотри также

Mr ivan777: /* Время работы */

2016-01-04T17:43:00Z

‎Время работы

Mr ivan777: /* Итоговый алгоритм */

2016-01-04T17:29:48Z

‎Итоговый алгоритм

Mr ivan777: /* Поиск пути */

2016-01-04T17:29:29Z

‎Поиск пути

Mr ivan777: /* Улучшение пути */

2016-01-04T17:29:01Z

‎Улучшение пути

Mr ivan777: /* Итоговый алгоритм */

2016-01-04T17:27:10Z

‎Итоговый алгоритм

Mr ivan777: /* Поиск пути */

2016-01-04T17:26:49Z

‎Поиск пути

← Предыдущая		Версия 16:26, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
−

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

← Предыдущая		Версия 04:58, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
		+

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

@@ Строка 27: / Строка 27: @@
 * '''Шаг 1'''. Пусть <tex>U</tex> {{---}} корень дерева, в котором лежит <tex>S</tex>.
 * '''Шаг 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> запрос.
 * '''Шаг 5'''. В <tex>U</tex> записываем число, равное остаточной пропускной способности ребра. Переходим к '''шагу 1'''.

@@ Строка 68: / Строка 68: @@
 Тогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O((V + E) \log(V))</tex>. И, суммарно, если подставить в алгоритм Диница будем иметь ассимптотику <tex>O(VE \log(V)) </tex>.
-== Смотри также ==
+== См. также ==
 * [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 * [[Алоритм Эдмондса-Карпа|Алоритм Эдмондса-Карпа]]

@@ Строка 55: / Строка 55: @@
 ==Время работы==
-[[Link-Cut Tree|Linking-Cutting Tree]]  выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма.
+[[Link-Cut Tree|Link-Cut tree]]  выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма.
 Очевидно, что просмотров ребер суммарно <tex>O(E)</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:

@@ Строка 46: / Строка 46: @@
 Пусть дана сеть. Требуется в этой сети найти поток <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'''.
@@ Строка 52: / Строка 52: @@
 * '''Шаг 4'''.  ''Улучшение пути''. Обновляем значения потока и пропускной способности при помощи <tex>(2)</tex> запроса.
 * '''Шаг 5'''.  ''Удаление нулевых ребер''. Обрезаем нулевые ребра при помощи <tex>(3)</tex> запроса. Переходим к '''шагу 2'''.
-* Конец
+* Конец.
 ==Время работы==

@@ Строка 39: / Строка 39: @@
 * При помощи <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> запрос по этому ребру. Стоит заметить, что нулевых ребер может получиться несколько, в случае нескольких минимумов.
 ===Итоговый алгоритм===

@@ Строка 43: / Строка 43: @@
 ===Итоговый алгоритм===
-Объединим вышесказанное в алгоритм Голдберга-Татьяна.
+Объединим вышесказанное в алгоритм Голдберга-Тарьяна.
 Пусть дана сеть. Требуется в этой сети найти поток <tex>f(S, T) </tex> максимальной величины.