Изменения

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

Алгоритм Шибера-Вишкина

11 051 байт добавлено, 19:07, 4 сентября 2022
м
rollbackEdits.php mass rollback
'''Алгоритм Шибера-Вишкина'' ' (англ.''Schieber-Vishkin '') применяется для нахождения [[Сведение задачи LCA к задаче RMQ|наименьшего общего предка ]] двух вершин в дереве.Он использует <tex>O(n)</tex> времени на подготовку препроцессинг и затем отвечает на каждый запрос за <tex>O(1)</tex>.
==Идея алгоритма==
Основная идея алгоритма следующая.
# Если бы дерево, в котором нужно искать <tex>LCA</tex> было бы цепочкойпростым путем, можно было бы найти <tex>LCA(u, v)</tex> просто взяв ту вершину, которая находится в дереве вышеближе к корню.# Если дерево {{---}} полное [[Дерево поиска, наивная реализация|двоичное дерево ]], высоты <tex>h</tex>, то можно сопоставить каждой вершине битовый вектор длиной <tex>h</tex> (целое число от <tex>0</tex> до <tex>2^h-1</tex>) и с помощью битовых операций над этими векторами найти <tex>LCA(u, v)</tex>
Тогда, представив данное дерево как полное [[Дерево поиска, наивная реализация|двоичное дерево]], в каждой вершине некоторых вершинах которого находится цепочкапростой путь, можно научиться искать <tex>LCA(v, u)</tex> в нем за <tex>O(1)</tex>.
==ПодготовкаПрепроцессинг==Перенумеруем вершины в порядке префиксного обхода дерева: сначала обходится текущая вершина, затем {{---}} поддеревья.Пусть <tex>\operatorname{order} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.
Обозначим за <tex>T</tex> {{---}} входное дерево с <tex>n</tex> вершинами. Для него нужно отвечать на запросы <tex>LCA</tex>.<br><tex>B</tex>\operatorname{size{---}} полное [[Дерево поиска, наивная реализация|двоичное дерево]] с не менее, чем <tex>n</tex> вершинами. Будет введено и объяснено дальше.<br><tex>S(v)</tex> количество вершин в поддереве {{---}} поддерево вершины <tex>v</tex>. Здесь и далее считаем, что вершина является и своим предком, и своим потомком.<br><tex>v</tex> ''выше'' <tex>u</tex> {{---}} то же самое, что <tex>u \in S(v)</tex>. Корень выше любой вершины. Перенумеруем вершины в порядке [[Дерево поиска, наивная реализация|префиксного обхода дерева]]. Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>.
{{Утверждение
|statement=Пусть <tex>u</tex> {{---}} вершина из поддерева <tex>\in S(v)</tex>. Тогда <tex>\operatorname{orderpreOrder} u \in [\operatorname{orderpreOrder} v; \operatorname{orderpreOrder}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{orderpreOrder}</tex>, : <tex>\operatorname{orderpreOrder} u</tex> вершин из поддерева <tex>v</tex> образуют
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с
<tex>\operatorname{orderpreOrder}v + 1</tex>, то <tex>\operatorname{orderpreOrder} u</tex> {{---}} отрезок лежит в отрезке <tex>[\operatorname{orderpreOrder} v; \operatorname{orderpreOrder} v + \operatorname{size} v - 1]</tex>.
}}
{{Утверждение
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{orderpreOrder} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=
Пусть <tex>\operatorname{chaininlabel} v = \operatorname{orderpreOrder} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.Пусть есть вершина <tex>u' \in S(iv)</tex> такая, что <tex>\operatorname{orderpreOrder} u' = k'2^b</tex>.
Так как в отрезке, соответствующем вершине <tex>v</tex> есть два числа, кратных <tex>2^b</tex>, то
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{chaininlabel} v</tex> выбран неверно.Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>2^{max} | \operatorname{orderpreOrder} u \hdots 2^{max}</tex>.
Рассмотрим два случая.
''Первый случай'' <tex>\operatorname{chain} v = \operatorname{order} v</tex>
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{chain}</tex> отличаются
от <tex>\operatorname{chain} v</tex>.
'''Первый случай''': <tex>\operatorname{inlabel} v = \operatorname{preOrder} v</tex>.&nbsp; Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inlabel}</tex> отличаютсяот <tex>\operatorname{inlabel} v</tex>. '''Второй случай'' ': <tex>\operatorname{chaininlabel} v = \operatorname{orderpreOrder} u</tex>, <tex>u \in S(v), u \ne v</tex>. Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{orderpreOrder}</tex>-ы из отрезка <tex>[\operatorname{orderpreOrder} v; \operatorname{orderpreOrder} v + \operatorname{size} v - 1]</tex>, то рассмотрим того непосредственного потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{chaininlabel} w = \operatorname{chaininlabel} v = \operatorname{orderpreOrder} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{chaininlabel} v' = \operatorname{chaininlabel} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для  Получили, что прообраз <tex>\operatorname{inlabel} v</tex> в вершине <tex>v</tex> или обрывается, или продолжается вниз ровно в одного потомка. Значит, прообраз <tex>\operatorname{inlabel} v</tex> {{---}} простой путь из какой-то вершины вниз в <tex>T</tex>, что и требовалось доказать.}} {{Утверждение|statement=<tex>\operatorname{inlabel} v = 2^i \bigg\lfloor \dfrac{\operatorname{preOrder} v + \operatorname{size} v}{2^i}\bigg\rfloor</tex>, где <tex>i = \lfloor\log_2 ((\operatorname{preOrder} - 1) \oplus (\operatorname{preOrder} v + \operatorname{size} v - 1)) \rfloor</tex>|proof=Посмотрим на <tex>A = (\operatorname{preOrder} v - 1) \oplus (\operatorname{preOrder} v + \operatorname{size} v - 1)</tex>. Посмотрим на позицию самого значимого единичного бита <tex>l</tex> в <tex>A</tex>.  Так как в <tex>\operatorname{preOrder} v - 1</tex> там еще <tex>0</tex>, а в <tex>\operatorname{preOrder} v + \operatorname{size} v - 1</tex> {{---}} уже единица, то в отрезке <tex>[\operatorname{preOrder} v; \operatorname{preOrder} v + \operatorname{size} v]</tex> есть число, кратное <tex>2^l</tex>.  Докажем, что нет чисел, кратных <tex>2^{l+1}</tex>. Пусть такое число нашлось. Тогда <tex>l</tex>-й бит менялся хотя бы два раза, а значит, менялся <tex>l+1</tex>-й бит. А значит, самый значащий отличающийся бит в <tex>\operatorname{preOrder} v - 1</tex> и в <tex>\operatorname{preOrder} v + \operatorname{size} v - 1</tex> больше, чем <tex>l</tex>-й. Заметим, что функция <tex>\lfloor \log_2 a \rfloor + 1</tex> просто выделяет номер самого значашего единичного бита. Функция <tex>2^l\left\lfloor\dfrac{a}{2^l}\right\rfloor</tex> обнуляет все биты младше <tex>l</tex>-го.  Чтобы получить из отрезка число, кратное <tex>2^l</tex>, будучи уверенными, что оно там есть, достаточно обнулить <tex>l</tex> битов в правой границе отрезка.}} Каждое значение <tex>\operatorname{inlabel} v</tex> соответствует вершине в полном двоичном дереве <tex>B</tex> высоты <tex>h=\lceil\log_2 n\rceil</tex>. В дереве на одном наборе вершин будет построено два набора ребер: ''каркасные'' и ''основные''. Для каждой вершины <tex>v \in V(B)</tex> с уровня, кроме последнего, будут каркасные ребра <tex>v\to2v</tex> и <tex>v\to2v+1</tex>. Таким образом, вершины в <tex>B</tex> будут занумерованы в инфиксном порядке обхода по каркасным ребрам: сначала обрабатывается левое поддерево, потом {{---}} вершина, потом {{---}} правое поддерево. В <tex>B</tex> будет основное ребро между вершинами <tex>\operatorname{inlabel} v</tex> и <tex>\operatorname{inlabel} u</tex>, если в <tex>T</tex> есть ребро <tex>v\to u</tex>. Корень имеет номер <tex>1</tex>. Будем говорить, что вершина <tex>u \in B</tex> лежит в поддереве вершины <tex>u \in B</tex> (<tex>u \in S(v)</tex>), если от <tex>v</tex> есть путь до <tex>u</tex> по каркасным ребрам. {{Утверждение|statement=Если в <tex>T</tex>wесть ребро <tex>v\to u</tex>, то в <tex>B</tex>: <tex>\operatorname{inlabel} u \in S(\operatorname{inlabel} v)</tex>Другими словами, получим требуемоевсе основные ребра направлены вниз.|proof=
}}
 
Посчитаем для каждого <tex>\operatorname{inlabel} v</tex> множество всех его предков в <tex>B</tex> по основным ребрам. Заметим, что для хранения одного предка достаточно хранить только его высоту в дереве. Чтобы восстановить его значение, нужно просто подняться на <tex>\Delta h</tex> вверх от вершины <tex>v</tex>. Поэтому, все это множество можно уместить в целое число: <tex>i</tex>-й бит будет единицей, если есть предок на высоте <tex>i</tex>. Назовем это число, отвечающее множеству предков, <tex>\operatorname{ascendant} v</tex>.
 
В дальнейшем <tex>\operatorname{ascendant} v </tex> поможет в поиске <tex>LCA(\operatorname{inlabel} v, \operatorname{inlabel} u)</tex>. Также, нам понадобится еще следующая информация. <tex>\operatorname{head} v</tex> {{---}} самая не глубокая вершина <tex>u</tex> такая, что <tex>\operatorname{inlabel} v = \operatorname{inlabel} u</tex>. <tex>\operatorname{level} v</tex> {{---}} глубина вершины <tex>v</tex> в <tex>T</tex>.
==Обработка запроса==
Пусть <tex>x</tex>, <tex>y</tex> {{---}} вершины в исходном дереве <tex>LCA</tex> которых необходимо найти. Если <tex>\operatorname{inlabel} x = \operatorname{inlabel} y</tex>, то они принадлежат одному простому пути, а следовательно ответом на запрос является <tex>x</tex>, если <tex>\operatorname{inlabellevel} x \le leqslant \operatorname{inlabellevel} y</tex>, и <tex>y</tex>, в противном случае. Теперь рассмотрим случай, когда <tex>\operatorname{inlabel} x \ne \operatorname{inlabel} y</tex>, то есть <tex>x</tex> и <tex>y</tex> принадлежат разным простым путям. {{Утверждение|statement=Следующие вычисления позволяют найти <tex>\operatorname{inlabel} LCA(x,y)</tex>: #<tex>i = \lfloor\log_2 (\operatorname{inlabel} x \oplus \operatorname{inlabel} y)\rfloor</tex>#<tex>path = 2^i \lfloor\dfrac{(\operatorname{ascendant} x) \wedge (\operatorname{ascendant} y)}{2^i}\rfloor</tex>#<tex>\operatorname{inlabel} LCA(x, y) = \lfloor\dfrac12(path \oplus (path - 1))\rfloor + 1</tex>|proof=<tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex> {{---}} вершины в <tex>B</tex>. Биты в их записи задают задают их местоположение в дереве.Ноль {{---}} спуститься влево, единица {{---}} спуститься вправо или остаться здесь. Значит, наиболее значимый бит побитового исключающего или их номеров даст глубину, на которой пути до этих вершин начинают расходиться. Это и хранится в <tex>i</tex>. Значит, мы нашли <tex>LCA</tex> по каркасным ребрам. Однако, могло случиться так, что <tex>LCA</tex> по основным ребрам, поиском которого мы занимаемся, находится выше (он не может находиться ниже или в стороне, так как все основные ребра направлены вниз).  Взяв побитовое и <tex>\operatorname{ascendant} x</tex> и <tex>\operatorname{ascendant} y</tex>, в старших единичных битах мы получим путь от корня по основным ребрам до этих вершин. При этом, про те биты, которые отвечают за уровни ниже <tex>LCA</tex>, ничего не известно. Поэтому, нужно их обнулить. Умножение и деление на <tex>2^i</tex> обнулят ненужные биты. После этого, для нахождения <tex>LCA</tex> по основным ребрам, нужно найти в <tex>path</tex> наименее значимый единичный бит. Формула <tex>\dfrac12(x \oplus (x - 1)) + 1</tex> имеено это и делает.}} После этих действий нами был получен путь, в котором находится ответ. Осталось посмотреть на точки входа <tex>x</tex> и <tex>y</tex> на путь <tex>\operatorname{inlabel} LCA(x, y)</tex>. Это можно сделать с помощью посчитанной функции <tex>\operatorname{head}</tex>: найти <tex>\operatorname{head} v'</tex>, где <tex>v'</tex> {{---}} вершина предпоследнего пути в пути. Тогда, поднявшись от нее на один вверх по начальному дереву, получим искомую точку входа. Имея две точки входа, можно, как и в первом случае, сравнить их по высоте и выбрать более высокое из них. ==Оценка сложности=====Построение===Подсчет массивов <tex> \operatorname{inlabel} </tex> и <tex> \operatorname{preOrder}</tex> занимает <tex>O(n)</tex>: <tex> \operatorname{preOrder}</tex> можно посчитать, например, [[Обход в глубину, цвета вершин|обходом в глубину]], а <tex> \operatorname{inlabel} </tex> выражается через <tex> \operatorname{preOrder}</tex>, как описано выше. ===Запрос===<tex>\operatorname{inlabel} LCA(x, y)</tex> и <tex>\operatorname{head} v'</tex> вычисляются за <tex>O(1)</tex>, следовательно, нужно сделать <tex>O(1)</tex> действий для ответа на запрос. == См.также ==*[[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн ]]*[[Метод двоичного подъема]]== Источники информации ==* [http://ia600208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf Baruch Schieber, Uzi Vishkin, "On Finding Lowest Common Ancestors: Simplification and Parallelization"] [[Категория: Дискретная математика и алгоритмы]][[Категория: Задача о наименьшем общем предке]]
1632
правки

Навигация