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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлен раздел)
(Перемещение части об алгоритме Комлоса в отдельную статью)
Строка 1: Строка 1:
 
{{в разработке}}
 
{{в разработке}}
  
'''Алгоритм Кинг''' {{---}} метод проверки, является ли [[Лемма о безопасном ребре#Необходимые определения | остовное дерево]] неориентированного взвешенного графа [[Лемма о безопасном ребре#Необходимые определения |минимальным]]. Алгоритм имеет линейную сложность, что является преимуществом по сравнению с ранними подходами<ref name="tarjan">Tarjan, R.E., 1979. Applications of path compression on balanced trees. Journal of the ACM (JACM), 26(4), pp.690-715.</ref><ref name="drt">B. Dixon, M. Rauch, and R. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time,SIAM J. Comput.,21(6) (1992), 1184–1192.</ref><ref name="komlos">Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443</ref>.
+
'''Алгоритм Кинг''' {{---}} алгоритм, предложенный Валери Кинг (''англ. Valerie King''), позволяющий свести проверку минимальности [[Лемма о безопасном ребре#Необходимые определения |остовного дерева]] графа к случаю полного ветвящегося дерева. Данное вспомогательное дерево может быть использовано в частном случае [[Алгоритм Комлоса| алгоритма Комлоса]], для которого также была предложена эффективная реализация, позволяющая выполнить проверку минимальности за линейное время. Алгоритм имеет линейную сложность, что является преимуществом по сравнению с ранними подходами<ref name="tarjan">Tarjan, R.E., 1979. Applications of path compression on balanced trees. Journal of the ACM (JACM), 26(4), pp.690-715.</ref><ref name="drt">B. Dixon, M. Rauch, and R. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time,SIAM J. Comput.,21(6) (1992), 1184–1192.</ref><ref name="komlos">Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443</ref>.
  
 
== Описание алгоритма ==
 
== Описание алгоритма ==
 
Пусть <math>T = (V_T, E_T)</math> {{---}} остовное дерево неориентированного взвешенного графа <math>G = (V_G, E_G)</math>.
 
Пусть <math>T = (V_T, E_T)</math> {{---}} остовное дерево неориентированного взвешенного графа <math>G = (V_G, E_G)</math>.
Описываемый метод заключается в проверке [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]]:  
+
Проверка минимальности остовного дерева заключается в проверке [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]]:  
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
Строка 42: Строка 42:
 
Если ребро <math>e</math> было выбрано алгоритмом Борувки для дерева, которое содержит <math>x</math> или <math>y</math>, тогда ребру в <math>B(f(x), f(y))</math> был присвоен вес <math>w(e)</math>. Предположим обратное {{---}} ребро <math>e</math> было выбрано алгоритмом для дерева, не содержащего вершины <math>x</math> или <math>y</math>. Одно из окончаний ребра <math>e</math> находится в этом дереве, и данная вершина является промежуточной на пути из <math>x</math> в <math>y</math>. Следовательно, это ребро прилегает к минимум двум другим рёбрам, находящимся на пути из <math>x</math> в <math>y</math>. Тогда среди этих рёбер <math>e</math> является ребром с наибольшим весом, которое не было выбрано, что является противоречием.
 
Если ребро <math>e</math> было выбрано алгоритмом Борувки для дерева, которое содержит <math>x</math> или <math>y</math>, тогда ребру в <math>B(f(x), f(y))</math> был присвоен вес <math>w(e)</math>. Предположим обратное {{---}} ребро <math>e</math> было выбрано алгоритмом для дерева, не содержащего вершины <math>x</math> или <math>y</math>. Одно из окончаний ребра <math>e</math> находится в этом дереве, и данная вершина является промежуточной на пути из <math>x</math> в <math>y</math>. Следовательно, это ребро прилегает к минимум двум другим рёбрам, находящимся на пути из <math>x</math> в <math>y</math>. Тогда среди этих рёбер <math>e</math> является ребром с наибольшим весом, которое не было выбрано, что является противоречием.
 
}}
 
}}
=== Применение алгоритма Комлоса к вспомогательному дереву ===
 
Для полного ветвящегося дерева Комлосом был показан алгоритм<ref name="komlos">Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443</ref>, который находит ребро с максимальным весом на пути для каждой пары вершин, используя <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>A(v)</math>, достаточно сравнить веса рёбер из <math>A(s)</math> с весом ребра <math>\{v, s\}</math>. Данное сравнение можно эффективно выполнить с помощью двоичного поиска.  Итоговое множество <math>A(v)</math> получается путем объединением множеств рёбер, полученных для каждого потомка.  
+
Построенное вспомогательное дерево позволяет свести задачу проверки минимального остовного дерева к случаю полного ветвящегося дерева, что является частным случаем [[Алгоритм Комлоса#Случай полного ветвящегося дерева|алгоритма Комлоса]] верификации минимального остовного дерева. Кинг была предложена [[Алгоритм Комлоса#Эффективная реализация при помощи битового сжатия|эффективная реализация]] данного случая с использованием битового сжатия, позволяющая проверить минимальность остовного дерева со сложностью <math>O(|E_T|+|V_T|)</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="komlos">Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443</ref>, что дает верхнюю границу для количества операций сравнений, используемых алгоритмом.
 
 
== Особенности реализации алгоритма ==
 
=== Используемые структуры данных ===
 
Реализация алгоритма требует операций над битовыми словами размера порядка <math>O(\log|V_T|)</math>. Было показано, что рассматриваемые операции возможно предпосчитать за время <math>O(|V_T|)</math> и сохранить в таблице, обращение к которой занимает <math>O(1)</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_T|\rceil</math>, записанная как последовательность <math><d(v), i(v)></math>. В оригинальной работе было показано, что имея тег ребра и номер вершины, можно обнаружить ребро в графе за константное время.
 
 
Для каждой вершины <math>v</math> создается вектор длины <math>\lceil\lg|V_T|\rceil</math>, обозначаемый как <math>LCA(v)</math>, чей бит с номером i равен 1 тогда, когда существует путь из листа в поддереве с корнем <math>v</math> в лист в другом поддереве, наивысшая по уровню вершина которого (иначе говоря, наименьший общий предок двух листьев) находится на расстоянии <math>i</math> от <math>v</math>.
 
 
Далее, вершины делятся на два класса. Если <math>|A(v)|>\frac{\lceil\lg|V_T|\rceil}{\lceil\lg\lg |V_T|\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_T|\rceil}{\lceil\lg|V_T|\rceil}=O(\log\log |V_T|)</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>v</math> возможно за <math>O\left(\log |A(v)|\right)</math> операций. Суммируя по всем вершинам, итоговая сложность алгоритма составляет <math>O\left(|V_T|\log\left(\frac{|E_T|+|V_T|}{|V_T|}\right)\right)</math> операций, что и было показано Комлосом.
 
 
Дополнительно алгоритм тратит <math>O(|V_T|+|E_T|)</math> операций для построения списков <math>LCA(v)</math>, <math>O(n)</math> операций для обработки таблиц с предвычисленными значениями и <math>O(m)</math> операций сравнения для нахождения ребра с максимальным весом из двух половин.
 
 
В завершении алгоритма, требуется сравнить веса рёбер графа, которые не входят в остовное дерево, с найденными в дереве <math>B</math> рёбрами наибольшего веса, что потребует дополнительных <math>O(m)</math> операций сравнения.
 
 
== См. также ==
 
== См. также ==
* [[Остовные деревья: определения, лемма о безопасном ребре]]
+
* [[Алгоритм Комлоса]]
 
* [[Алгоритм Борувки]]
 
* [[Алгоритм Борувки]]
 
* [[Критерий Тарьяна минимальности остовного дерева]]  
 
* [[Критерий Тарьяна минимальности остовного дерева]]  

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

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

Алгоритм Кинг — алгоритм, предложенный Валери Кинг (англ. Valerie King), позволяющий свести проверку минимальности остовного дерева графа к случаю полного ветвящегося дерева. Данное вспомогательное дерево может быть использовано в частном случае алгоритма Комлоса, для которого также была предложена эффективная реализация, позволяющая выполнить проверку минимальности за линейное время. Алгоритм имеет линейную сложность, что является преимуществом по сравнению с ранними подходами[1][2][3].

Описание алгоритма

Пусть [math]T = (V_T, E_T)[/math] — остовное дерево неориентированного взвешенного графа [math]G = (V_G, E_G)[/math]. Проверка минимальности остовного дерева заключается в проверке критерия Тарьяна:

Утверждение:
Остовное дерево является минимальным тогда и только тогда, когда вес любого ребра графа, соединяющего вершины [math]u[/math] и [math]v[/math], не входящего в остовное дерево, больше либо равен весу ребра, имеющего максимальный вес среди ребер входящих в путь между [math]u[/math] и [math]v[/math] в остовном дереве.

Используем следующие обозначения:

  • [math]\{u, v\}[/math] — ребро, соединяющее вершины [math]u[/math] и [math]v[/math],
  • [math]T(u, v)[/math] — множество рёбер, входящих в путь между вершинами [math]u, v[/math] в дереве [math]T[/math],
  • [math]w(e)[/math] — вес ребра [math]e[/math],
  • [math]Heavy(T, u, v) = \arg\max\{w(e) | e\in T(u, v)\}[/math] — ребро с максимальным весом на пути между вершинами [math]u, v[/math] в дереве [math]T[/math].

Если найти [math]Heavy(T, u, v)[/math] для всех [math]u, v \in V_T[/math], то для проверки минимальности остовного дерева достаточно сравнить [math]w(Heavy(T, u, v))[/math] и [math]w(\{u, v\})[/math] для всех рёбер [math]\{u, v\} \in E_G \setminus E_T[/math].

Построение вспомогательного дерева

Алгоритм строит вспомогательное дерево [math]B = (V_B, E_B)[/math], являющееся подвешенным и полным ветвящимся (такое дерево, у вершин которого либо 0, либо 2 и более потомков, и в котором все листья находятся на одном уровне), для которого будет выполняться следующее: [math]w(Heavy(B, u, v)) = w(Heavy(T, u, v))[/math] для любой пары вершин [math]u, v \in V_T[/math]. Построение дерева [math]B[/math] основано на алгоритме Борувки. При инициализации алгоритма для каждой вершины [math]v \in T[/math] создается лист [math]f(v)[/math] в [math]B[/math]. Пусть на некотором шаге алгоритма Борувки алгоритм объединяет множество деревьев [math]A[/math] в одно дерево, обозначаемое [math]t[/math]. При этом алгоритм выбирает некоторые рёбра с наименьшим весом, прилегающие к деревьям из множества [math]A[/math]. Обозначим такое ребро для некоторого дерева [math]a \in A[/math] как [math]adj(a)[/math]. Тогда алгоритм создает новую вершину [math]f(t)[/math] в [math]V_B[/math] и добавляет новые рёбра в [math]E_B[/math] как [math]\{\{f(t), f(a)\} | a \in A\}[/math]. Каждому ребру [math]\{f(t), f(a)\}[/math] присваивается вес выбранного алгоритмом Борувки ребра, т.е. [math]w(\{f(t), f(a)\}) := w(adj(a))[/math].

Сложность каждой фазы алгоритма пропорциональна количеству рёбер, не выбранных ранее. Так как [math]T[/math] является деревом, количество таких рёбер равно количеству деревьев на шаге алгоритма минус один. После каждой фазы количество деревьев сокращается как минимум вдвое, поэтому можно заключить, что построение дерева [math]B[/math] имеет сложность [math]O(n)[/math].

Теорема (1):
Пусть [math]T = (V_T, E_T)[/math] — остовное дерево графа, и [math]B = (V_B, E_B)[/math] — дерево, построенное алгоритмом. Тогда для каждой пары вершин [math]x, y \in V_T[/math], [math]w(Heavy(T, x, y)) = w(Heavy(B, f(x), f(y)))[/math].
Доказательство:
[math]\triangleright[/math]

Вначале покажем, что для каждого ребра [math]e \in B(f(x), f(y))[/math] существует ребро [math]e'\in T(x,y)[/math] для которого верно [math]w(e) \leq w(e')[/math].

Пусть [math]e = \{a, b\}[/math] и, без потери общности, положим, что вершина [math]a[/math] находится дальше от корня дерева [math]B[/math], чем [math]b[/math]. Тогда [math]a = f(t)[/math] для некоторого дерева [math]t[/math], построенного на некотором шаге алгоритма Борувки, которое содержит либо [math]x[/math], либо [math]y[/math], но не обе вершины одновременно.

Пусть [math]e' \in T(x, y)[/math] — ребро, содержащее ровно одно окончание в дереве [math]t[/math]. Так как во время фазы, в которой производился выбор ребра для дерева [math]t[/math], была возможность выбрать ребро [math]e'[/math], его вес [math]w(e') \geq w(e)[/math], что и требовалось показать.

Остается доказать следующее:

Утверждение:
Пусть ребро [math]e \in T(x,y)[/math] имеет максимальный вес. Тогда существует ребро в [math]B(f(x), f(y))[/math], имеющее такой же вес.

Предположим, что существует единственное ребро в [math]T(x, y)[/math], имеющее максимальный вес. Доказательство тривиально обобщается на случай нескольких рёбер с максимальным весом.

Если ребро [math]e[/math] было выбрано алгоритмом Борувки для дерева, которое содержит [math]x[/math] или [math]y[/math], тогда ребру в [math]B(f(x), f(y))[/math] был присвоен вес [math]w(e)[/math]. Предположим обратное — ребро [math]e[/math] было выбрано алгоритмом для дерева, не содержащего вершины [math]x[/math] или [math]y[/math]. Одно из окончаний ребра [math]e[/math] находится в этом дереве, и данная вершина является промежуточной на пути из [math]x[/math] в [math]y[/math]. Следовательно, это ребро прилегает к минимум двум другим рёбрам, находящимся на пути из [math]x[/math] в [math]y[/math]. Тогда среди этих рёбер [math]e[/math] является ребром с наибольшим весом, которое не было выбрано, что является противоречием.
[math]\triangleleft[/math]

Использование вспомогательного дерева

Построенное вспомогательное дерево позволяет свести задачу проверки минимального остовного дерева к случаю полного ветвящегося дерева, что является частным случаем алгоритма Комлоса верификации минимального остовного дерева. Кинг была предложена эффективная реализация данного случая с использованием битового сжатия, позволяющая проверить минимальность остовного дерева со сложностью [math]O(|E_T|+|V_T|)[/math].

См. также

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

Примечания

  1. Tarjan, R.E., 1979. Applications of path compression on balanced trees. Journal of the ACM (JACM), 26(4), pp.690-715.
  2. B. Dixon, M. Rauch, and R. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time,SIAM J. Comput.,21(6) (1992), 1184–1192.
  3. Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443