Алгоритм Комлоса — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Перенос части про алгоритм Комлоса в отдельную статью из статьи про алгоритм Кинг)
 
(не показана 1 промежуточная версия этого же участника)
Строка 2: Строка 2:
  
 
'''Алгоритм Комло́са''' {{---}} алгоритм, разработанный Яношем Комлосом (''венг. Komlós János''). Алгоритм предназначен для поиска ребра с наибольшим весом на путях между каждой парой вершин в подвешенных деревьях. Поиск таких рёбер используется при верификации [[Лемма о безопасном ребре#Необходимые определения | минимального остовного дерева]] путем проверки [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]].
 
'''Алгоритм Комло́са''' {{---}} алгоритм, разработанный Яношем Комлосом (''венг. Komlós János''). Алгоритм предназначен для поиска ребра с наибольшим весом на путях между каждой парой вершин в подвешенных деревьях. Поиск таких рёбер используется при верификации [[Лемма о безопасном ребре#Необходимые определения | минимального остовного дерева]] путем проверки [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]].
 +
 +
Пусть существует некоторый взвешенный неориентированный граф <math>G</math> и его остовное дерево <math>T</math>. Допустим, что для каждого ребра <math>\{u, v\}</math> графа <math>G</math>, не входящего в дерево <math>T</math>, существует способ найти ребро с наибольшим весом в пути между вершинами <math>u, v</math> в дереве <math>T</math>. Тогда для проверки критерия Тарьяна достаточно сравнить веса таких рёбер с весами рёбер <math>\{u, v\}</math>.
  
 
== Описание алгоритма ==
 
== Описание алгоритма ==
 
=== Случай полного ветвящегося дерева ===
 
=== Случай полного ветвящегося дерева ===
 
==== Общее описание подхода ====
 
==== Общее описание подхода ====
−
Рассмотрим полное ветвящееся дерево <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, 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>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>. Описанные в работе структуры данных и битовые операции, которые возможно предвычислить и сохранить в таблице, обращение к которой занимает константное количество операций, позволяют выполнить алгоритм Комлоса за линейное время.
 
В работе Валери Кинг был предложен [[Алгоритм Кинг|метод сведения общего случая остовного дерева к полному ветвящемуся дереву]], а также предложена эффективная реализация алгоритма Комлоса с использованием битового сжатия<ref name="kingalg">King, V. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263–270 (1997). https://doi.org/10.1007/BF02526037</ref>. Описанные в работе структуры данных и битовые операции, которые возможно предвычислить и сохранить в таблице, обращение к которой занимает константное количество операций, позволяют выполнить алгоритм Комлоса за линейное время.
Строка 30: Строка 34:
  
 
В завершении алгоритма, требуется сравнить веса рёбер графа, которые не входят в остовное дерево, с найденными в остовном дереве рёбрами наибольшего веса, что потребует дополнительных <math>O(m)</math> операций сравнения, где <math>m</math> {{---}} количество рёбер в исходном графе.
 
В завершении алгоритма, требуется сравнить веса рёбер графа, которые не входят в остовное дерево, с найденными в остовном дереве рёбрами наибольшего веса, что потребует дополнительных <math>O(m)</math> операций сравнения, где <math>m</math> {{---}} количество рёбер в исходном графе.
 +
 +
== См. также ==
 +
* [[Критерий Тарьяна минимальности остовного дерева]]
 +
* [[Алгоритм Кинг]]
 +
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]
 
== Источники информации ==
 
== Источники информации ==
 
* Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443
 
* Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443
Строка 35: Строка 44:
 
== Примечания ==
 
== Примечания ==
 
<references/>
 
<references/>
 +
 +
[[Категория:Алгоритмы на графах]]
 +
[[Категория:Построение остовных деревьев]]

Версия 16:08, 25 января 2022

Эта статья находится в разработке!

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

Пусть существует некоторый взвешенный неориентированный граф [math]G[/math] и его остовное дерево [math]T[/math]. Допустим, что для каждого ребра [math]\{u, v\}[/math] графа [math]G[/math], не входящего в дерево [math]T[/math], существует способ найти ребро с наибольшим весом в пути между вершинами [math]u, v[/math] в дереве [math]T[/math]. Тогда для проверки критерия Тарьяна достаточно сравнить веса таких рёбер с весами рёбер [math]\{u, v\}[/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]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], алгоритм находит ребро с наибольшим весом на пути между двумя листьями следующим образом. Для всех листьев в дереве находится их наименьший общий предок, например, с помощью алгоритма Тарьяна со сложностью [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|\log\left(\frac{|E|+|V|}{|V|}\right)\right)[/math], что дает верхнюю границу для количества операций сравнений, используемых алгоритмом.

Эффективная реализация при помощи битового сжатия

В работе Валери Кинг был предложен метод сведения общего случая остовного дерева к полному ветвящемуся дереву, а также предложена эффективная реализация алгоритма Комлоса с использованием битового сжатия[1]. Описанные в работе структуры данных и битовые операции, которые возможно предвычислить и сохранить в таблице, обращение к которой занимает константное количество операций, позволяют выполнить алгоритм Комлоса за линейное время.

Обозначим за [math]T=(V, E)[/math] полное ветвящееся дерево, полученное с помощью алгоритма Кинг. Вершины в дереве нумеруются битовыми словами следующим образом:

  1. Каждый лист помечается порядковым номером 0, 1, 2... в двоичном представлении в порядке встречи листов при обходе в глубину.
  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]\lt d(v), i(v)\gt [/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)|\gt \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] — количество рёбер в исходном графе.

См. также

Источники информации

Примечания

  1. ↑ King, V. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263–270 (1997). https://doi.org/10.1007/BF02526037
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Комлоса&oldid=82175»