Метод двоичного подъёма — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}} ==Описание алгоритма== Метод двоичного подъема - это один из самых простых м…»)
 
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 +
Метод двоичного подъема - это один из самых простых методов для решения задачи LCA в on-line и он не использует метод решение задачи RMQ. Он основан на методе динамического программирования.
 +
==Описание алгоритма==
 +
Как и все on-line алгоритмы, этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.
 +
===Препроцессинг===
 +
Препроцессинг заключается в том, чтобы посчитать функцию: <tex> dp[v][i] </tex> - это номер вершины, в которую мы придем если пройдем из вершины <tex> v </tex> вверх по подвешенному дереву <tex> 2 ^ i </tex> шагов, причем если мы пришли в корень, то мы там и останемся.
 +
Для этого сначала обойдем дерево в глубину и для каждой вершины запишем номер ее родителя <tex> p[v] </tex> и глубину вершины в подвешенном дереве <tex> depth[v] </tex>. Если <tex> v </tex> - корень, то <tex> p[v] = v </tex>. Тогда для функции <tex> dp </tex> есть рекуррентная формула:
 +
<tex>dp[v][i]= \begin{cases}
 +
p[v] & i = 0,\\
 +
dp[dp[v][i - 1]][i - 1] & i > 0.
 +
\end{cases}</tex>
  
==Описание алгоритма==
+
Для того чтобы отвечать на запросы нам нужны будут только те значения <tex> dp[v][i] </tex>, где <tex> i \le \log_2{n} </tex>, ведь при больших <tex> i </tex> значение <tex> dp[v][i] </tex> будет номером корня.
Метод двоичного подъема - это один из самых простых методов для решения задачи LCA в on-line и он не использует метод решение задачи RMQ. Он основан на методе динамического программирования.
+
 
 +
===Ответы на запросы===

Версия 06:44, 7 мая 2011

Эта статья находится в разработке!

Метод двоичного подъема - это один из самых простых методов для решения задачи LCA в on-line и он не использует метод решение задачи RMQ. Он основан на методе динамического программирования.

Описание алгоритма

Как и все on-line алгоритмы, этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.

Препроцессинг

Препроцессинг заключается в том, чтобы посчитать функцию: [math] dp[v][i] [/math] - это номер вершины, в которую мы придем если пройдем из вершины [math] v [/math] вверх по подвешенному дереву [math] 2 ^ i [/math] шагов, причем если мы пришли в корень, то мы там и останемся. Для этого сначала обойдем дерево в глубину и для каждой вершины запишем номер ее родителя [math] p[v] [/math] и глубину вершины в подвешенном дереве [math] depth[v] [/math]. Если [math] v [/math] - корень, то [math] p[v] = v [/math]. Тогда для функции [math] dp [/math] есть рекуррентная формула: [math]dp[v][i]= \begin{cases} p[v] & i = 0,\\ dp[dp[v][i - 1]][i - 1] & i \gt 0. \end{cases}[/math]

Для того чтобы отвечать на запросы нам нужны будут только те значения [math] dp[v][i] [/math], где [math] i \le \log_2{n} [/math], ведь при больших [math] i [/math] значение [math] dp[v][i] [/math] будет номером корня.

Ответы на запросы