Level Ancestor problem — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 23: Строка 23:
 
Разобьем все вершины на пути следующим образом. Обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
 
Разобьем все вершины на пути следующим образом. Обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
 
<tex>v</tex>, обойдем всех ее детей, добавив <tex>v</tex> в путь, идущий в самое глубокое поддерево,
 
<tex>v</tex>, обойдем всех ее детей, добавив <tex>v</tex> в путь, идущий в самое глубокое поддерево,
т.е. в котором находится вершина с саомй большой глубиной.
+
т.е. в котором находится вершина с самой большой глубиной.
 
Для каждой вершины сохраним номер пути в который она входит.
 
Для каждой вершины сохраним номер пути в который она входит.
 
=== Ladder decomposition ===
 
=== Ladder decomposition ===
Увеличим каждый путь в два раза вверх, для каждого ового пути сохраним все входящие в него вершины,
+
Увеличим каждый путь в два раза вверх, для каждого нового пути сохраним все входящие в него вершины,
 
а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у
 
а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у
 
нас O(n) времени (обход в глубину), соответственно удлиннение каждого пути ухудшит ассимптотику до  <tex>O(n \log n)</tex>.
 
нас O(n) времени (обход в глубину), соответственно удлиннение каждого пути ухудшит ассимптотику до  <tex>O(n \log n)</tex>.
После этого посчитаем двоичные подьемы для каждой вершины за <tex>O(\log n)</tex>, что соответственно не ухудшит ассимптотику.
+
=== Двоичные подъемы ===
 +
После этого посчитаем двоичные подъемы для каждой вершины за <tex>O(\log n)</tex>, что соответственно не ухудшит ассимптотику.
  
 
Пусть после этого нам пришел запрос <tex>LA(v, k)</tex>.
 
Пусть после этого нам пришел запрос <tex>LA(v, k)</tex>.
 +
 +
*Сделаем один максимально большой прыжок вверх с помощью насчитанных двоичных подъемов.
 +
#<tex>i = \log k</tex>
 +
#<tex>v = p_i[v]</tex>
 +
* Рассмотрим путь, на котором лежит вершина <tex>v</tex> до удвоения. Он длины хотя бы <tex>2^i</tex>, так как мы точно знаем, что существует вершина потомок <tex>v</tex>, расстояние до которого ровно <tex>2^i</tex> (это вершина, из которой мы только что пришли). Значит, после удвоения этот путь стал длины хотя бы <tex>2^{i + 1}</tex>, причем хотя бы <tex>2^i</tex> вершин в нем - предки <tex>v</tex>. Это означает, что вершина, которую мы ищем, находится на этом пути (иначе бы мы могли до этого прыгнуть еще на <tex>2^i</tex> вверх). Так как мы знаем позицию <tex>v</tex> в этом пути, то нужную вершину мы можем найти за <tex>O(1)</tex>.
 +
 +
Таким образом, наш алгоритм работает за < <tex>O(n\log n), O(1)</tex> >. С помощью метода четырех русских данный метод можно улучшить до < <tex>O(n), O(1)</tex> > с помощью оптимизации предподсчета.

Версия 23:54, 11 мая 2019

Задача о уровне предка (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.


Задача:
Дано корневое дерево [math]T[/math] c [math]n[/math] вершинами. Поступают запросы вида [math]LA(v, k)[/math], для каждого из которых необходимо найти предка вершины [math]v[/math], который находится на расстоянии [math]k[/math] от корня дерева [math]T[/math].

Наивная реализация и двоичные подъемы

LevelAncestor.png

Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за [math]O(n)[/math]), после чего можем из вершины [math]v[/math] подняться до необходимой глубины вершины [math]k[/math], что так же в худшем случае работает за [math]O(n)[/math]. Получили алгоритм за < [math]O(n), O(n)[/math] >, где время ответа на запрос можно улучшить до [math]O(\log n)[/math] c помощью предподсчета двоичных подъемов , но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до < [math]O(n \log n), O(\log n)[/math] >. Альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам ассимптотику < [math]O(n^2), O(1)[/math] >.

В данном примере поступает запрос [math]LA(v, 2)[/math], на который алгоритм должен дать ответ h.

Использование Heavy-light декомпозиции

Этот алгоритм базируется на различных способах декомпозиции дерева (выберем heavy-light декомпозицию), из свойств этого разбиения следует, что подняться на любую высоту из вершины [math]v[/math] мы можем за [math]O(\log n)[/math]. Данное разбиение можно строить за [math]O(n)[/math], что дает нам алгоритм за < [math]O(n), O(\log n)[/math] >.

Алгоритм лестниц

Longest path decomposition

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

Ladder decomposition

Увеличим каждый путь в два раза вверх, для каждого нового пути сохраним все входящие в него вершины, а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у нас O(n) времени (обход в глубину), соответственно удлиннение каждого пути ухудшит ассимптотику до [math]O(n \log n)[/math].

Двоичные подъемы

После этого посчитаем двоичные подъемы для каждой вершины за [math]O(\log n)[/math], что соответственно не ухудшит ассимптотику.

Пусть после этого нам пришел запрос [math]LA(v, k)[/math].

  • Сделаем один максимально большой прыжок вверх с помощью насчитанных двоичных подъемов.
  1. [math]i = \log k[/math]
  2. [math]v = p_i[v][/math]
  • Рассмотрим путь, на котором лежит вершина [math]v[/math] до удвоения. Он длины хотя бы [math]2^i[/math], так как мы точно знаем, что существует вершина потомок [math]v[/math], расстояние до которого ровно [math]2^i[/math] (это вершина, из которой мы только что пришли). Значит, после удвоения этот путь стал длины хотя бы [math]2^{i + 1}[/math], причем хотя бы [math]2^i[/math] вершин в нем - предки [math]v[/math]. Это означает, что вершина, которую мы ищем, находится на этом пути (иначе бы мы могли до этого прыгнуть еще на [math]2^i[/math] вверх). Так как мы знаем позицию [math]v[/math] в этом пути, то нужную вершину мы можем найти за [math]O(1)[/math].

Таким образом, наш алгоритм работает за < [math]O(n\log n), O(1)[/math] >. С помощью метода четырех русских данный метод можно улучшить до < [math]O(n), O(1)[/math] > с помощью оптимизации предподсчета.