Редактирование: Level Ancestor problem

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Задача о уровне предка''' (англ. "Level Ancestor problem") является задачей о превращении данного подвешенного дерева <tex>T</tex> в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от этого узла.
+
'''Задача о уровне предка''' (англ. "Level Ancestor problem") является задачей о превращении данного подвешенного дерева <tex>T</tex> в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.
  
 
{{Задача
 
{{Задача
Строка 11: Строка 11:
 
Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за <tex>\langle O(n), O(\log n) \rangle</tex>.
 
Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за <tex>\langle O(n), O(\log n) \rangle</tex>.
  
В данном примере поступает запрос LA(v, 2), на который алгоритм должен дать ответ h.
+
В данном примере поступает запрос LA(v,2), на который алгоритм должен дать ответ h.
  
 
== Алгоритм лестниц ==
 
== Алгоритм лестниц ==
=== 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>===
+
=== Longest path decomposition ===
Это декомпозиция дерева, которая разбивает его на множество вершинно-непересекающихся путей, идущих из каждой вершины в ее ребенка с самым глубоким поддеревом.
+
Разобьем все вершины на пути следующим образом. Обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
Сделаем ее следующим образом: обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
 
 
<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(n \log n)</tex>.
Строка 30: Строка 28:
 
=== Псевдокод ===
 
=== Псевдокод ===
  
Пусть после этого нам пришел запрос LA(v, k).
+
Пусть после этого нам пришел запрос <tex>LA(v, k)</tex>.
 
 
*<tex>p[i] [v]</tex> — <tex>i</tex>-тый двоичный подъем в предка вершины <tex>v</tex>
 
*<tex>way[v]</tex> — путь, проходящий через данную вершину
 
*<tex>num[v]</tex> — номер данной вершины на пути
 
*<tex>ladder[p][i]</tex> — возвращает <tex>i</tex>-тую вершину на пути <tex>p</tex>
 
 
 
 
   '''function''' LA('''int''' v,'''int''' k):
 
   '''function''' LA('''int''' v,'''int''' k):
       '''int''' n = h(v) ''<font color="green">// получаем глубину вершины <tex>v</tex></font>''
+
       '''int''' n = h(v); ''<font color="green">// получаем глубину вершины <tex>v</tex></font>''
 
       n = n - k;  ''<font color="green">// на столько необходимо подняться до ответа</font>''
 
       n = n - k;  ''<font color="green">// на столько необходимо подняться до ответа</font>''
       i = <tex>\lfloor \log_2 n \rfloor</tex>
+
       i = <tex>\log_2 n</tex>
       v = p[i][v]  ''<font color="green">// делаем максимально большой прыжок вверх</font>''
+
       v = p_i[v]  ''<font color="green">// делаем максимально большой прыжок вверх</font>''
       i = n - i  ''<font color="green">// на столько осталось еще подняться</font>''
+
       i = n - i; ''<font color="green">// на столько осталось еще подняться</font>''
       '''return''' ladder[way[v]][num[v] - i] ''<font color="green">// так как теперь <tex>v</tex> и ответ находятся на одном пути</font>''
+
       '''return''' way[num_on_way[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>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> с помощью оптимизации предподсчета.
 
Таким образом, наш алгоритм работает за <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 ==
 
==  The Macro-Micro-Tree Algorithm ==
 
В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до <tex>O(n)</tex>.
 
В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до <tex>O(n)</tex>.
Для начала рассмотрим алгоритм <tex>\langle O(L\log n + n), O(1)\rangle </tex>, где <tex>L</tex> это количество листьев.
+
Для начала рассмотрим алгоритм <tex>\langle O(L\log n + n), O(1)</tex> >, где <tex>L</tex> это количество листьев.
*С помощью обхода в глубину запомним по одному листу в поддереве для каждой вершины
+
*С помощью обхода в глубину запомним по одному листу в ее поддереве для каждой вершины
 
*Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.
 
*Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.
 
Рассмотрим как можно улучшить данный алгоритм:
 
Рассмотрим как можно улучшить данный алгоритм:
Строка 61: Строка 52:
  
 
В итоге полученный алгоритм действительно работает за <tex>\langle O(n), O(1)\rangle </tex> времени и за <tex>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>,
 
Используя DFS посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>,
 
что так же в худшем случае работает за <tex>O(n)</tex>.
 
что так же в худшем случае работает за <tex>O(n)</tex>.
Строка 71: Строка 61:
  
 
Сравнение различных асимптотик из данной статьи:
 
Сравнение различных асимптотик из данной статьи:
{| class="wikitable" style="clear:right;" cellpadding="10"
+
{| class="wikitable" style="clear:right; color:blue;" cellpadding="10"
 
|+
 
|+
 
|-align="center"
 
|-align="center"
 
!
 
!
| Предподсчет
+
| <tex>Предподсчет</tex>
| Ответ на запрос
+
| <tex>Ответ</tex>
| Память
+
| <tex>Память</tex>
 
|-align="center"
 
|-align="center"
 
!Обычный подъем до нужного уровня
 
!Обычный подъем до нужного уровня
Строка 97: Строка 87:
 
|<tex>O(n)</tex>||<tex>O(1)</tex>||<tex>O(n)</tex>
 
|<tex>O(n)</tex>||<tex>O(1)</tex>||<tex>O(n)</tex>
 
|}
 
|}
 +
 +
== Примечания ==
 +
[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]
 
== См. также ==  
 
== См. также ==  
 
*[[Метод двоичного подъёма]]
 
*[[Метод двоичного подъёма]]
 
*[[Heavy-light декомпозиция]]
 
*[[Heavy-light декомпозиция]]
== Примечания ==
 
<references/>
 
 
== Источники информации ==
 
== Источники информации ==
 
*[https://www.cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/5.pdf Level Ancestor problem simplified Cai Qi]
 
*[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]
 
*[https://en.wikipedia.org/wiki/Level_ancestor_problem Wikipedia: LA]
 +
*[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]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: