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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 69 промежуточных версий 13 участников)
Строка 1: Строка 1:
'''Задача о уровне предка''' (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.
+
'''Задача о уровне предка''' (англ. "Level Ancestor problem") является задачей о превращении данного подвешенного дерева <tex>T</tex> в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от этого узла.
  
 
{{Задача
 
{{Задача
|definition = Дано корневое дерево <tex>T</tex> c <tex>n</tex> вершинами. Поступают запросы вида <tex>LA(v, k)</tex>, для каждого из которых необходимо
+
|definition = Дано подвешенное дерево <tex>T</tex> c <tex>n</tex> вершинами. Поступают запросы вида <tex>LA(v, k)</tex>, для каждого из которых необходимо
 
найти предка вершины <tex>v</tex>, который находится на расстоянии <tex>k</tex> от корня дерева <tex>T</tex>.
 
найти предка вершины <tex>v</tex>, который находится на расстоянии <tex>k</tex> от корня дерева <tex>T</tex>.
 
}}
 
}}
== Наивная реализация и двоичные подъемы ==
+
== Использование Heavy-light декомпозиции ==
 
[[Файл:LevelAncestor.png|200px|thumb|right]]
 
[[Файл:LevelAncestor.png|200px|thumb|right]]
Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>,
+
Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева]] (выберем heavy-light декомпозицию), из свойств этого разбиения следует,
что так же в худшем случае работает за <tex>O(n)</tex>.
+
что подняться на любую высоту из вершины <tex>v</tex> мы можем за время <tex>O(\log n)</tex>.
Получили алгоритм за < <tex>O(n), O(n)</tex> >, где время ответа на
+
Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за <tex>\langle O(n), O(\log n) \rangle</tex>.
запрос можно улучшить до <tex>O(\log n)</tex> c помощью [[Метод двоичного подъёма | предподсчета двоичных подъемов]]  ,
+
 
но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до < <tex>O(n \log n),
+
В данном примере поступает запрос LA(v, 2), на который алгоритм должен дать ответ h.
O(\log n)</tex> >. Альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам ассимптотику < <tex>O(n^2), O(1)</tex> >.
 
  
В данном примере поступает запрос <tex>LA(v, 2)</tex>, на который алгоритм должен дать ответ h.
 
== Использование Heavy-light декомпозиции ==
 
Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева]] (выберем heavy-light декомпозицию), из свойств этого разбиения следует,
 
что подняться на любую высоту из вершины <tex>v</tex> мы можем за <tex>O(\log n)</tex>.
 
Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за < <tex>O(n), O(\log n)</tex> >.
 
 
== Алгоритм лестниц ==
 
== Алгоритм лестниц ==
=== Longest path decomposition ===
+
=== Longest path decomposition <ref>[https://www.mi.fu-berlin.de/en/inf/groups/abi/teaching/lectures/lectures_past/WS0910/V____Discrete_Mathematics_for_Bioinformatics__P1/material/scripts/treedecomposition1.pdf Longest path decomposition]</ref>===
Разобьем все вершины на пути следующим образом. Обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
+
Это декомпозиция дерева, которая разбивает его на множество вершинно-непересекающихся путей, идущих из каждой вершины в ее ребенка с самым глубоким поддеревом.
 +
Сделаем ее следующим образом: обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
 
<tex>v</tex>, обойдем всех ее детей, добавив <tex>v</tex> в путь, идущий в самое глубокое поддерево,
 
<tex>v</tex>, обойдем всех ее детей, добавив <tex>v</tex> в путь, идущий в самое глубокое поддерево,
 
т.е. в котором находится вершина с самой большой глубиной.
 
т.е. в котором находится вершина с самой большой глубиной.
 
Для каждой вершины сохраним номер пути в который она входит.
 
Для каждой вершины сохраним номер пути в который она входит.
 +
 
=== Ladder decomposition ===
 
=== Ladder decomposition ===
Увеличим каждый путь в два раза вверх, для каждого нового пути сохраним все входящие в него вершины,
+
Это улучшение Longest-path декомпозиции, позволяющее, как мы потом докажем, подниматься на любую высоту за <tex>O(1)</tex>. Выполним его следующим образом: увеличим каждый путь в два раза вверх, для каждого нового пути сохраним все входящие в него вершины,
 
а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у
 
а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у
нас <tex>O(n)</tex> времени (обход в глубину), соответственно удлиннение каждого пути ухудшит ассимптотику до  <tex>O(n \log n)</tex>.
+
нас <tex>O(n)</tex> времени (обход в глубину), удлинение каждого пути не ухудшит асимптотику.
=== Двоичные подъемы ===
+
 
После этого посчитаем двоичные подъемы для каждой вершины за <tex>O(\log n)</tex>, что соответственно не ухудшит ассимптотику.
+
После этого посчитаем двоичные подъемы для каждой вершины за <tex>O(\log n)</tex>, получим итоговую оценку <tex>O(n \log n)</tex> на предподсчет.
 +
 
 +
=== Псевдокод ===
  
Пусть после этого нам пришел запрос <tex>LA(v, k)</tex>.
+
Пусть после этого нам пришел запрос LA(v, k).
  
*Сделаем один максимально большой прыжок вверх с помощью насчитанных двоичных подъемов.
+
*<tex>p[i] [v]</tex> — <tex>i</tex>-тый двоичный подъем в предка вершины <tex>v</tex>
#<tex>i = \log k</tex>
+
*<tex>way[v]</tex> — путь, проходящий через данную вершину
#<tex>v = p_i[v]</tex>
+
*<tex>num[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>ladder[p][i]</tex> — возвращает <tex>i</tex>-тую вершину на пути <tex>p</tex>
 +
 
 +
  '''function''' LA('''int''' v,'''int''' k):
 +
      '''int''' n = h(v) ''<font color="green">// получаем глубину вершины <tex>v</tex></font>''
 +
      n = n - k;  ''<font color="green">// на столько необходимо подняться до ответа</font>''
 +
      i = <tex>\lfloor \log_2 n \rfloor</tex>
 +
      v = p[i][v]  ''<font color="green">// делаем максимально большой прыжок вверх</font>''
 +
      i = n - <tex>2^i</tex> ''<font color="green">// на столько осталось еще подняться</font>''
 +
      '''return''' ladder[way[v]][num[v] - i] ''<font color="green">// так как теперь <tex>v</tex> и ответ находятся на одном пути</font>''
 +
 
 +
=== Доказательство корректности ===
 +
Рассмотрим путь, на котором лежит вершина <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>\langle O(n\log n), O(1)\rangle </tex> времени и за <tex>O(n\log n)</tex> памяти. Методом четырех русских данный метод можно улучшить до <tex>\langle O(n), O(1)\rangle </tex> с помощью оптимизации предподсчета.
 +
 
 +
==  The Macro-Micro-Tree Algorithm ==
 +
В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до <tex>O(n)</tex>.
 +
Для начала рассмотрим алгоритм <tex>\langle O(L\log n + n), O(1)\rangle </tex>, где <tex>L</tex> это количество листьев.
 +
*С помощью обхода в глубину запомним по одному листу в поддереве для каждой вершины
 +
*Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.
 +
Рассмотрим как можно улучшить данный алгоритм:
 +
*Зададим некую функцию <tex>S(n) = \dfrac{1}{4} \log_2 n</tex>
 +
*Посчитаем размер поддерева для каждой вершины с помощью обхода в глубину, после чего удалим все вершины размер поддерева которых меньше чем  <tex>S(n)</tex>.
 +
*Забудем на время про удаленные поддеревья, для оставшегося дерева наш алгоритм работает за  <tex>\langle O(\dfrac{n}{S(n)} \log n + n), O(1)\rangle </tex>. Получаем алгоритм <tex>\langle O(n), O(1) \rangle </tex>. Для удаленных поддеревьев же выполним полный предподсчет: таких деревьев не более чем <tex>2^{2S(n)}</tex>, что дает асимптотику предподсчета <tex>O(\sqrt{n} \log^2{n}) = o(n) = O(n)</tex>.
 +
 
 +
В итоге полученный алгоритм действительно работает за <tex>\langle O(n), O(1)\rangle </tex> времени и за <tex>O(n)</tex> памяти.
 +
 
 +
== Сравнение с другими реализациями ==
 +
Используя DFS посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>,
 +
что так же в худшем случае работает за <tex>O(n)</tex>.
 +
Получили алгоритм за <tex>\langle O(n), O(n) \rangle</tex> времени и <tex>O(n)</tex> памяти, где время ответа на
 +
запрос можно улучшить до <tex>O(\log n)</tex> c помощью [[Метод двоичного подъёма | предподсчета двоичных подъемов]]  ,
 +
но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до <tex>\langle O(n \log n),
 +
O(\log n)\rangle </tex> времени и <tex>O(n \log n)</tex> памяти. Также альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам асимптотику <tex>\langle O(n^2), O(1)\rangle </tex>времени и <tex>O(n^2)</tex> памяти.
  
Таким образом, наш алгоритм работает за < <tex>O(n\log n), O(1)</tex> >. Методом четырех русских данный метод можно улучшить до < <tex>O(n), O(1)</tex> > с помощью оптимизации предподсчета.
+
Сравнение различных асимптотик из данной статьи:
 +
{| class="wikitable" style="clear:right;" cellpadding="10"
 +
|+
 +
|-align="center"
 +
!
 +
| Предподсчет
 +
| Ответ на запрос
 +
| Память
 +
|-align="center"
 +
!Обычный подъем до нужного уровня
 +
|<tex>O(n)</tex>||<tex>O(n)</tex>||<tex>O(n)</tex>
 +
|-align="center"
 +
!Полный предподсчет
 +
|<tex>O(n^2)</tex>||<tex>O(1)</tex>||<tex>O(n^2)</tex>
 +
|-align="center"
 +
!Двоичные подъемы
 +
|<tex>O(n \log n)</tex>||<tex>O(\log n)</tex>||<tex>O(n \log n)</tex>
 +
|-align="center"
 +
!Декомпозиция
 +
|<tex>O(n)</tex>||<tex>O(\log n)</tex>||<tex>O(n)</tex>
 +
|-align="center"
 +
!Алгоритм лестниц
 +
|<tex>O(n \log n)</tex>||<tex>O(1)</tex>||<tex>O(n \log n)</tex>
 +
|-align="center"
 +
!Macro-Micro-Tree Algorithm
 +
|<tex>O(n)</tex>||<tex>O(1)</tex>||<tex>O(n)</tex>
 +
|}
 +
== См. также ==
 +
*[[Метод двоичного подъёма]]
 +
*[[Heavy-light декомпозиция]]
 +
== Примечания ==
 +
<references/>
 +
== Источники информации ==
 +
*[https://www.cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/5.pdf Level Ancestor problem simplified Cai Qi]
 +
*[https://en.wikipedia.org/wiki/Level_ancestor_problem Wikipedia: LA]
 +
[[Категория: Алгоритмы и структуры данных]]

Текущая версия на 19:15, 4 сентября 2022

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


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

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

LevelAncestor.png

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

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

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

Longest path decomposition [1]

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

Ladder decomposition

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

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

Псевдокод

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

  • [math]p[i] [v][/math][math]i[/math]-тый двоичный подъем в предка вершины [math]v[/math]
  • [math]way[v][/math] — путь, проходящий через данную вершину
  • [math]num[v][/math] — номер данной вершины на пути
  • [math]ladder[p][i][/math] — возвращает [math]i[/math]-тую вершину на пути [math]p[/math]
  function LA(int v,int k):
     int n = h(v) // получаем глубину вершины [math]v[/math]
     n = n - k;  // на столько необходимо подняться до ответа
     i = [math]\lfloor \log_2 n \rfloor[/math]
     v = p[i][v]  // делаем максимально большой прыжок вверх
     i = n - [math]2^i[/math]  // на столько осталось еще подняться
     return ladder[way[v]][num[v] - i] // так как теперь [math]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]\langle O(n\log n), O(1)\rangle [/math] времени и за [math]O(n\log n)[/math] памяти. Методом четырех русских данный метод можно улучшить до [math]\langle O(n), O(1)\rangle [/math] с помощью оптимизации предподсчета.

The Macro-Micro-Tree Algorithm

В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до [math]O(n)[/math]. Для начала рассмотрим алгоритм [math]\langle O(L\log n + n), O(1)\rangle [/math], где [math]L[/math] это количество листьев.

  • С помощью обхода в глубину запомним по одному листу в поддереве для каждой вершины
  • Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.

Рассмотрим как можно улучшить данный алгоритм:

  • Зададим некую функцию [math]S(n) = \dfrac{1}{4} \log_2 n[/math]
  • Посчитаем размер поддерева для каждой вершины с помощью обхода в глубину, после чего удалим все вершины размер поддерева которых меньше чем [math]S(n)[/math].
  • Забудем на время про удаленные поддеревья, для оставшегося дерева наш алгоритм работает за [math]\langle O(\dfrac{n}{S(n)} \log n + n), O(1)\rangle [/math]. Получаем алгоритм [math]\langle O(n), O(1) \rangle [/math]. Для удаленных поддеревьев же выполним полный предподсчет: таких деревьев не более чем [math]2^{2S(n)}[/math], что дает асимптотику предподсчета [math]O(\sqrt{n} \log^2{n}) = o(n) = O(n)[/math].

В итоге полученный алгоритм действительно работает за [math]\langle O(n), O(1)\rangle [/math] времени и за [math]O(n)[/math] памяти.

Сравнение с другими реализациями

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

Сравнение различных асимптотик из данной статьи:

Предподсчет Ответ на запрос Память
Обычный подъем до нужного уровня [math]O(n)[/math] [math]O(n)[/math] [math]O(n)[/math]
Полный предподсчет [math]O(n^2)[/math] [math]O(1)[/math] [math]O(n^2)[/math]
Двоичные подъемы [math]O(n \log n)[/math] [math]O(\log n)[/math] [math]O(n \log n)[/math]
Декомпозиция [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math]
Алгоритм лестниц [math]O(n \log n)[/math] [math]O(1)[/math] [math]O(n \log n)[/math]
Macro-Micro-Tree Algorithm [math]O(n)[/math] [math]O(1)[/math] [math]O(n)[/math]

См. также

Примечания

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