Алгоритм Комлоса - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:41:04Z

rollbackEdits.php mass rollback

217.79.179.7 в 03:44, 1 сентября 2022

2022-09-01T03:44:09Z

VerlorenMind в 13:08, 25 января 2022

2022-01-25T13:08:24Z

VerlorenMind в 13:04, 25 января 2022

2022-01-25T13:04:27Z

VerlorenMind: Перенос части про алгоритм Комлоса в отдельную статью из статьи про алгоритм Кинг

2022-01-25T12:35:13Z

Перенос части про алгоритм Комлоса в отдельную статью из статьи про алгоритм Кинг

Новая страница

{{в разработке}}

'''Алгоритм Комло́са''' {{---}} алгоритм, разработанный Яношем Комлосом (''венг. Komlós János''). Алгоритм предназначен для поиска ребра с наибольшим весом на путях между каждой парой вершин в подвешенных деревьях. Поиск таких рёбер используется при верификации [[Лемма о безопасном ребре#Необходимые определения | минимального остовного дерева]] путем проверки [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]].

== Описание алгоритма ==
=== Случай полного ветвящегося дерева ===
==== Общее описание подхода ====
Рассмотрим полное ветвящееся дерево <math>T</math>, т.е. такое дерево, у вершин которого либо 0, либо 2 и более потомков, и все листья находятся на одном уровне. Для такого дерева Комлосом был показан вариант алгоритма, который находит ребро с максимальным весом на пути для каждой пары листьев, используя <math>O\left(n\log\left(\frac{m+n}{n}\right)\right)</math> операций сравнения. Алгоритм разбивает путь между листьями на две части, начинающихся в листе и заканчивающихся в наименьшем общем предке этих листьев, и находит ребро с наибольшим весом в каждой части. После чего, одно из двух рёбер с большим весом выбирается ребром с наибольшим весом на пути из одной вершины в другую.

Алгоритм вычисляет вес для каждой части пути следующим образом. Пусть <math>A(v, l)</math> {{---}} ребро максимального веса на пути из корня в некоторый лист <math>l</math>, проходящий через вершину <math>v</math>, ограниченном на отрезке <math>[v, l]</math> (т.е. удалены все вершины от корня до предка v). Обозначим <math>A(v) = \{A(v, l) | l \text{ содержится в поддереве с корнем } v\}</math>.
Предположим, что <math>s</math> {{---}} вершина-потомок <math>v</math>, и известно множество <math>A(s) = \{A(s, l_1), A(s, l_2),\dots\}</math>. Рассмотрим случай одного листа <math>l_i</math>. Очевидно, что все пути из корня в <math>l_i</math>, проходящие через <math>s</math>, также проходят через <math>v</math>. Так как ребро <math>\{v, s\}</math> связывает <math>v</math> и <math>s</math>, получим, что <math>A(v, l_i) = \arg\max\{w(A(s, l_i)), w(\{v, s\})\}</math>, где <math>w(e)</math> - вес ребра <math>e</math>. Следовательно, для того, чтобы найти <math>A(v)</math>, достаточно сравнить веса рёбер из <math>A(s)</math> с весом ребра <math>\{v, s\}</math>. Данное сравнение можно эффективно выполнить с помощью двоичного поиска. Итоговое множество <math>A(v)</math> получается путем объединением множеств рёбер, полученных для каждого потомка.

Комлос показал, что <math>\sum\limits_{v\in T} \log |A(v)| = O\left(|V_T|\log\left(\frac{|E_T|+|V_T|}{|V_T|}\right)\right)</math>, что дает верхнюю границу для количества операций сравнений, используемых алгоритмом.
==== Эффективная реализация при помощи битового сжатия ====
В работе Валери Кинг был предложен [[Алгоритм Кинг|метод сведения общего случая остовного дерева к полному ветвящемуся дереву]], а также предложена эффективная реализация алгоритма Комлоса с использованием битового сжатия<ref name="kingalg">King, V. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263–270 (1997). https://doi.org/10.1007/BF02526037</ref>. Описанные в работе структуры данных и битовые операции, которые возможно предвычислить и сохранить в таблице, обращение к которой занимает константное количество операций, позволяют выполнить алгоритм Комлоса за линейное время.

Обозначим за <math>T=(V, E)</math> полное ветвящееся дерево, полученное с помощью [[Алгоритм Кинг|алгоритма Кинг]]. Вершины в дереве нумеруются битовыми словами следующим образом:
# Каждый лист помечается порядковым номером 0, 1, 2... в двоичном представлении в порядке встречи листов при [[Обход_в_глубину,_цвета_вершин|обходе в глубину]].
# Каждый не-лист помечается номером своего потомка, содержащим наибольшее количество ведущих нулей.
Рёбра в дереве получают тег, который формируется следующим образом. Рассмотрим ребро <math>e = \{u, v\}</math>, где <math>v</math> находится дальше от корня. Пусть <math>d(v)</math> обозначает расстояние от вершины <math>v</math> до корня, а <math>i(v)</math> {{---}} номер младшей единицы в номере вершины <math>v</math>. Тогда тег ребра <math>e</math> {{---}} строка размера <math>\lceil\lg\lg |V|\rceil</math>, записанная как последовательность <math><d(v), i(v)></math>. В оригинальной работе было показано, что имея тег ребра и номер вершины, можно обнаружить ребро в графе за константное время.

Для каждой вершины <math>v</math> создается вектор длины <math>\lceil\lg|V|\rceil</math>, обозначаемый как <math>LCA(v)</math>, чей бит с номером i равен 1 тогда, когда существует путь из листа в поддереве с корнем <math>v</math> в лист в другом поддереве, наивысшая по уровню вершина которого (иначе говоря, наименьший общий предок двух листьев) находится на расстоянии <math>i</math> от <math>v</math>.

Далее, вершины делятся на два класса. Если <math>|A(v)|>\frac{\lceil\lg|V|\rceil}{\lceil\lg\lg |V|\rceil}</math>, то вершина <math>v</math> считается ''большой''; в противном случае вершина считается ''малой''. Для больших вершин создаются списки <math>bigList</math>, для малых {{---}} <math>smallList</math>. <math>BigList</math> содержит теги рёбер из <math>A(v)</math> в порядке неубывания длин путей из корня в листья, соответствующих рёбрам. Для хранения такого списка требуется <math>\frac{|A(v)|\lceil\lg\lg |V|\rceil}{\lceil\lg|V|\rceil}=O(\log\log |V|)</math> памяти.

Для малой вершины <math>v</math> обозначим за <math>a</math> ближайшего большого предка. Список <math>smallList</math> содержит либо теги рёбер из <math>A(v)</math>, либо, если ребро <math>e</math> из <math>A(v)</math> содержится в интервале от корня до <math>a</math>, указатель на <math>bigList</math> вершины <math>a</math>, содержащий тег для <math>e</math>. Для каждой малой вершины запоминается номер первого элемента в <math>smallList</math>, являющимся тегом. Элементы списка, идущие после первого тега, тоже являются тегами. Для хранения <math>smallList</math> требуется одно битовое слово.

==== Анализ сложности ====
Было показано, что в реализации с битовым сжатием операции для малых вершин выполняются за константное время. Если вершина большая, то стоимость предвычислений для неё составляет <math>|A(v)|\frac{\lceil\lg\lg |V|\rceil}{\lceil\lg|V|\rceil} = \Omega\left(\log |A(v)|\right)</math> операций. Следовательно, общая сложность предвычислений составляет <math>O(\log |A(v)|)</math> операций. Дополнительно алгоритм тратит <math>O(|V|+|E|)</math> операций для построения списков <math>LCA(v)</math>, <math>O(|V|)</math> операций для обработки таблиц с предвычисленными значениями и <math>O(|E|)</math> операций сравнения для нахождения ребра с максимальным весом из двух половин.

В завершении алгоритма, требуется сравнить веса рёбер графа, которые не входят в остовное дерево, с найденными в остовном дереве рёбрами наибольшего веса, что потребует дополнительных <math>O(m)</math> операций сравнения, где <math>m</math> {{---}} количество рёбер в исходном графе.
== Источники информации ==
* Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443

== Примечания ==
<references/>

← Предыдущая		Версия 16:41, 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 Майкл Наки].
−	\|}
−
	{{в разработке}}		{{в разработке}}

← Предыдущая		Версия 03:44, 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 Майкл Наки].
		+	\|}
		+
	{{в разработке}}		{{в разработке}}

@@ Строка 10: / Строка 10: @@
 Рассмотрим полное ветвящееся дерево <math>T = (V, E)</math>, т.е. такое дерево, у вершин которого либо 0, либо 2 и более потомков, и все листья находятся на одном уровне. Для такого дерева Комлосом был показан вариант алгоритма, который находит ребро с максимальным весом на пути для каждой пары листьев, используя <math>O\left(n\log\left(\frac{m+n}{n}\right)\right)</math> операций сравнения. Алгоритм разбивает путь между листьями на две части, начинающихся в листе и заканчивающихся в наименьшем общем предке этих листьев, и находит ребро с наибольшим весом в каждой части. После чего, одно из двух рёбер с большим весом выбирается ребром с наибольшим весом на пути из одной вершины в другую.
-Алгоритм вычисляет вес для каждой части пути следующим образом. Пусть <math>A(v, l)</math> {{---}} ребро максимального веса на пути из корня в некоторый лист <math>l</math>, проходящий через вершину <math>v</math>, ограниченном на отрезке <math>[v, l]</math> (т.е. удалены все вершины от корня до предка v). Обозначим <math>A(v) = \{A(v, l) | l \text{ содержится в поддереве с корнем } v\}</math> и <math>w(e)</math> - вес ребра <math>e</math>.
+Алгоритм вычисляет вес для каждой части пути следующим образом. Пусть <math>A(v, l)</math> {{---}} ребро максимального веса на пути из корня в некоторый лист <math>l</math>, проходящий через вершину <math>v</math>, ограниченном на отрезке <math>[v, l]</math> (т.е. удалены все вершины от корня до предка v). Обозначим <math>A(v) = \{A(v, l) | l \text{ содержится в поддереве с корнем } v\}</math>.
 Предположим, что <math>s</math> {{---}} вершина-потомок <math>v</math>, и известно множество <math>A(s) = \{A(s, l_1), A(s, l_2),\dots\}</math>. Рассмотрим случай одного листа <math>l_i</math>. Очевидно, что все пути из корня в <math>l_i</math>, проходящие через <math>s</math>, также проходят через <math>v</math>. Так как ребро <math>\{v, s\}</math> связывает <math>v</math> и <math>s</math>, получим, что <math>A(v, l_i) = \arg\max\{w(A(s, l_i)), w(\{v, s\})\}</math>, где <math>w(e)</math> - вес ребра <math>e</math>. Следовательно, для того, чтобы найти <math>A(v)</math>, достаточно сравнить веса рёбер из <math>A(s)</math> с весом ребра <math>\{v, s\}</math>. Данное сравнение можно эффективно выполнить с помощью двоичного поиска.  Итоговое множество <math>A(v)</math> получается путем объединением множеств рёбер, полученных для каждого потомка. Таким образом, алгоритм, начиная с корня дерева, спускается до листьев графа и конструирует множества <math>A(v)</math> для каждой вершины.
 После нахождения множеств <math>A(v)</math>, алгоритм находит ребро с наибольшим весом на пути между двумя листьями следующим образом. Для всех листьев в дереве находится их наименьший общий предок, например, с помощью [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн|алгоритма Тарьяна]] со сложностью <math>O(|V| + |E|)</math>. Пусть для некоторых двух листьев <math>l_i, l_j</math> их наименьший общий предок <math>LCA(l_i, l_j) = v</math>. Тогда ребром с наибольшим весом на пути из <math>l_i</math> в <math>l_j</math> будет ребро <math>e = \arg\max\{w(A(v, l_i)), w(A(v, l_j))\}</math>.
-Комлос показал, что <math>\sum\limits_{v\in T} \log |A(v)| = O\left(|V_T|\log\left(\frac{|E_T|+|V_T|}{|V_T|}\right)\right)</math>, что дает верхнюю границу для количества операций сравнений, используемых алгоритмом.
+Комлос показал, что <math>\sum\limits_{v\in T} \log |A(v)| = O\left(|V|\log\left(\frac{|E|+|V|}{|V|}\right)\right)</math>, что дает верхнюю границу для количества операций сравнений, используемых алгоритмом.
 ==== Эффективная реализация при помощи битового сжатия ====
 В работе Валери Кинг был предложен [[Алгоритм Кинг|метод сведения общего случая остовного дерева к полному ветвящемуся дереву]], а также предложена эффективная реализация алгоритма Комлоса с использованием битового сжатия<ref name="kingalg">King, V. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263–270 (1997). https://doi.org/10.1007/BF02526037</ref>. Описанные в работе структуры данных и битовые операции, которые возможно предвычислить и сохранить в таблице, обращение к которой занимает константное количество операций, позволяют выполнить алгоритм Комлоса за линейное время.

@@ Строка 2: / Строка 2: @@
 '''Алгоритм Комло́са''' {{---}} алгоритм, разработанный Яношем Комлосом (''венг. Komlós János''). Алгоритм предназначен для поиска ребра с наибольшим весом на путях между каждой парой вершин в подвешенных деревьях. Поиск таких рёбер используется при верификации [[Лемма о безопасном ребре#Необходимые определения | минимального остовного дерева]] путем проверки [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]].
 == Описание алгоритма ==
 === Случай полного ветвящегося дерева ===
 ==== Общее описание подхода ====
-Рассмотрим полное ветвящееся дерево <math>T</math>, т.е. такое дерево, у вершин которого либо 0, либо 2 и более потомков, и все листья находятся на одном уровне. Для такого дерева Комлосом был показан вариант алгоритма, который находит ребро с максимальным весом на пути для каждой пары листьев, используя <math>O\left(n\log\left(\frac{m+n}{n}\right)\right)</math> операций сравнения. Алгоритм разбивает путь между листьями на две части, начинающихся в листе и заканчивающихся в наименьшем общем предке этих листьев, и находит ребро с наибольшим весом в каждой части. После чего, одно из двух рёбер с большим весом выбирается ребром с наибольшим весом на пути из одной вершины в другую.
+Рассмотрим полное ветвящееся дерево <math>T = (V, E)</math>, т.е. такое дерево, у вершин которого либо 0, либо 2 и более потомков, и все листья находятся на одном уровне. Для такого дерева Комлосом был показан вариант алгоритма, который находит ребро с максимальным весом на пути для каждой пары листьев, используя <math>O\left(n\log\left(\frac{m+n}{n}\right)\right)</math> операций сравнения. Алгоритм разбивает путь между листьями на две части, начинающихся в листе и заканчивающихся в наименьшем общем предке этих листьев, и находит ребро с наибольшим весом в каждой части. После чего, одно из двух рёбер с большим весом выбирается ребром с наибольшим весом на пути из одной вершины в другую.
-Алгоритм вычисляет вес для каждой части пути следующим образом. Пусть <math>A(v, l)</math> {{---}} ребро максимального веса на пути из корня в некоторый лист <math>l</math>, проходящий через вершину <math>v</math>, ограниченном на отрезке <math>[v, l]</math> (т.е. удалены все вершины от корня до предка v). Обозначим <math>A(v) = \{A(v, l) | l \text{ содержится в поддереве с корнем } v\}</math>.
+После нахождения множеств <math>A(v)</math>, алгоритм находит ребро с наибольшим весом на пути между двумя листьями следующим образом. Для всех листьев в дереве находится их наименьший общий предок, например, с помощью [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн|алгоритма Тарьяна]] со сложностью <math>O(|V| + |E|)</math>. Пусть для некоторых двух листьев <math>l_i, l_j</math> их наименьший общий предок <math>LCA(l_i, l_j) = v</math>. Тогда ребром с наибольшим весом на пути из <math>l_i</math> в <math>l_j</math> будет ребро <math>e = \arg\max\{w(A(v, l_i)), w(A(v, l_j))\}</math>.
 Комлос показал, что <math>\sum\limits_{v\in T} \log |A(v)| = O\left(|V_T|\log\left(\frac{|E_T|+|V_T|}{|V_T|}\right)\right)</math>, что дает верхнюю границу для количества операций сравнений, используемых алгоритмом.
@@ Строка 30: / Строка 34: @@
 В завершении алгоритма, требуется сравнить веса рёбер графа, которые не входят в остовное дерево, с найденными в остовном дереве рёбрами наибольшего веса, что потребует дополнительных <math>O(m)</math> операций сравнения, где <math>m</math> {{---}} количество рёбер в исходном графе.
 == Источники информации ==
 * Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443
@@ Строка 35: / Строка 44: @@
 == Примечания ==
 <references/>