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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 14: Строка 14:
  
 
== Алгоритм лестниц ==
 
== Алгоритм лестниц ==
=== 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 ===
 
Это декомпозиция дерева, которая разбивает его на множество вершинно-непересекающихся путей, идущих из каждой вершины в ее ребенка с самым глубоким поддеревом.
 
Это декомпозиция дерева, которая разбивает его на множество вершинно-непересекающихся путей, идущих из каждой вершины в ее ребенка с самым глубоким поддеревом.
 
Сделаем ее следующим образом: обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
 
Сделаем ее следующим образом: обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
Строка 38: Строка 38:
  
 
   '''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''' ladder[way[v]][num[v] - i]; ''<font color="green">// так как теперь <tex>v</tex> и ответ находятся на одном пути</font>''
  
 
=== Доказательство корректности ===
 
=== Доказательство корректности ===
Строка 62: Строка 62:
 
В итоге полученный алгоритм действительно работает за <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>.
Строка 97: Строка 97:
 
|<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]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]

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

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

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

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