http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=93.175.2.117&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-29T09:14:45ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%B0%D1%80%D0%B0%D0%BA%D0%B0-%D0%9A%D0%BE%D0%BB%D1%82%D0%BE%D0%BD%D0%B0_%D0%B8_%D0%91%D0%B5%D0%BD%D0%B4%D0%B5%D1%80%D0%B0&diff=72200Алгоритм Фарака-Колтона и Бендера2020-01-20T18:15:36Z<p>93.175.2.117: /* Псевдокод */ Fix codeblock display</p>
<hr />
<div>'''Алгоритм Фарака-Колтона, Бендера''' (англ. ''Farach-Colton, Bender'') — применяется для решения за <tex>\langle O(N),O(1) \rangle</tex> времени специального случая задачи <tex>\mathrm{RMQ}</tex> (поиск минимума на отрезке), в котором соседние элементы входной последовательности различаются на <tex>\pm 1</tex>. Может быть использован также для [[Сведение задачи LCA к задаче RMQ|решения задачи <tex>\mathrm{LCA}</tex>]].<br />
<br />
{{Задача<br />
|definition = Дан массив <tex>A[1 \ldots N]</tex> целых чисел, соседние элементы которого отличаются на <tex>\pm 1</tex>. Поступают онлайн запросы вида <tex>(l, r)</tex>, для каждого из которых требуется найти минимум среди элементов <tex>A[l], A[l + 1], \ldots, A[r] </tex>.<br />
}}<br />
<br />
== Алгоритм ==<br />
<br />
Данный алгоритм основывается на методе решения задачи <tex>\mathrm{RMQ}</tex> с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.<br />
<br />
Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>A_i</tex> на блоки длины <tex>K=\dfrac{1}{2}\log_2 N</tex>. Для каждого блока вычислим минимум на нём и определим <tex>B_i</tex> как позицию минимального элемента в <tex>i</tex>-ом блоке.<br />
<br />
<br />
<br />
На новой последовательности <tex>B_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. При этом размер разреженной таблицы и время её построения будут равны:<br />
<br />
<tex>\dfrac{N}{K}\log\dfrac{N}{K}=\bigg(\dfrac{2N}{\log N}\bigg)\log\bigg(\dfrac{2N}{\log N}\bigg)=\bigg(\dfrac{2N}{\log N}\bigg)\bigg(1+\log\bigg(\dfrac{N}{\log N}\bigg)\bigg)\leqslant \dfrac{2N}{\log N}</tex> <tex>+2N=O(N)</tex><br />
<br />
Теперь для ответа на запрос <tex>\mathrm{RMQ}</tex><tex>[l:r]</tex>, если <tex>l</tex> и <tex>r</tex> находятся в разных блоках, нам необходимо вычислить следующее: <br />
* минимум на отрезке от <tex>l</tex> до конца блока, содержащего <tex>l</tex>;<br />
* минимум по всем блокам, находящимся между блоками, содержащими <tex>l</tex> и <tex>r</tex>;<br />
* минимум от начала блока, содержащего <tex>r</tex>, до <tex>r</tex>.<br />
Ответом на запрос будет позиция меньшего из этих трёх элементов.<br />
<br />
[[Файл:F-C_B_algo.png|500px|center|Части, из которых состоит ответ на запрос RMQ]]<br />
<br />
Второй элемент мы уже умеем находить за <tex>O(1)</tex> с помощью <tex>B_i</tex> и разреженной таблицы. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков.<br />
<br />
=== Минимум внутри блока ===<br />
<br />
{{Утверждение<br />
|id=sameblocks<br />
|statement=Если две последовательности <tex>x_i</tex> и <tex>y_i</tex> таковы, что все их элементы на соответствующих позициях различаются на одну и ту же константу (т.е. <tex>\forall k: x_k = y_k + C</tex>), то любой запрос <tex>\mathrm{RMQ}</tex> даст один и тот же ответ для обеих последовательностей.<br />
}}<br />
<br />
Таким образом, мы можем ''нормализовать'' блок, вычтя из всех его элементов первый. Тем самым мы значительно уменьшим число возможных типов блоков.<br />
<br />
{{Утверждение<br />
|id=kindscount<br />
|statement=Существует <tex>O(\sqrt N)</tex> различных типов нормализованных блоков.<br />
|proof=Соседние элементы в блоках отличаются на <tex>\pm 1</tex>. Первый элемент в нормализованном блоке всегда равен нулю. Таким образом, каждый нормализованный блок может быть представлен <tex>\pm 1</tex>-вектором длины <tex> \bigg(\dfrac{1}{2} \log_2 N\bigg) - 1</tex>. Таких векторов <tex>2^{(\frac{1}{2} \log_2 N) - 1} = O(\sqrt N)</tex>.<br />
}}<br />
<br />
Осталось создать <tex>O(\sqrt N)</tex> таблиц {{---}} по одной для каждого типа блока. В такую таблицу необходимо занести предподсчитанные ответы на все возможные запросы минимума внутри блока соответствующего типа, которых <tex>\bigg(\dfrac{1}{2}\log_2 N\bigg)^2 = O(\log^2 N)</tex>. Для каждого блока в <tex>B_i</tex> необходимо заранее вычислить его тип. Для этого нужно подобрать некоторую функцию из множества блоков в множество натуральных чисел, не вызывающую коллизий. Например, вектор из нулей и единиц, соответствующий типу блока, можно записать в целочисленный тип. Таким образом мы получили возможность отвечать на запрос минимума по любой части блока за <tex>O(1)</tex>, затратив на предподсчёт <tex>O(N)</tex> времени.<br />
<br />
=== Псевдокод ===<br />
<br />
'''function''' precalc(A: '''int[N]'''): <br />
block_size = log(N) / 2 <font color=green> // размеры блоков </font><br />
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> <font color=green> // количество блоков </font> <br />
<font color=green>// предподсчитаем позиции минимумов в каждом блоке</font><br />
cur_block = -1<br />
'''for''' i = 0 '''to''' K - 1 <br />
B[i] = -1 <br />
'''for''' i = 0 '''to''' N - 1<br />
'''if''' i '''mod''' block_size == 0 <br />
cur_block++ <br />
'''if''' B[cur_block] = -1 '''or''' A[B[cur_block]] > A[i]<br />
B[cur_block] = i<br />
<font color=green>// построим Sparse table на массиве B</font><br />
'''for''' i = 0 '''to''' K - 1<br />
ST[i][0] = B[i]<br />
'''for''' j = 1 '''to''' log(N)<br />
'''for''' i = 0 '''to''' K - 1<br />
ind = (1 << (j - 1)) + i<br />
'''if''' ind &ge; K<br />
ST[i][j] = ST[i][j - 1]<br />
'''else if''' A[ST[i][j - 1]] > A[ST[ind][j - 1]]<br />
ST[i][j] = ST[ind][j - 1] <br />
'''else'''<br />
ST[i][j] = ST[i][j - 1]<br />
<font color=green>// Посчитаем тип для каждого блока</font><br />
'''for''' i = 0 '''to''' K - 1 <br />
type[i] = 0 <br />
cur_block = 0<br />
j = 0<br />
i = 0<br />
'''while''' i < N or j < K<br />
'''if''' j &ge; block_size <br />
j = 0<br />
cur_block++ <br />
'''if''' j > 0 '''and''' (i &ge; N '''or''' A[i - 1] < A[i])<br />
type[cur_block] += (1 << (j - 1)) <br />
i++<br />
j++<br />
<font color=green>// Осталось только для каждого блока предподсчитать позиции минимумов на всех подотрезках</font><br />
'''for''' i = 0 '''to''' K - 1<br />
'''for''' l = 0 '''to''' block_size - 1<br />
'''for''' r = 0 '''to''' block_size - 1<br />
block_min[i][l][r] = -1 <br />
'''for''' i = 0 '''to''' K - 1<br />
t = type[i]<br />
'''if''' block_min[t][0][0] = -1 <font color=green>// если там записано, что-то отличное от -1, то значит, мы уже посчитали ответ для такого типа отрезков</font><br />
'''for''' l = 0 '''to''' block_size - 1<br />
block_min[t][l][l] = l<br />
'''for''' r = l + 1 '''to''' block_size - 1<br />
block_min[t][l][r] = block_min[t][l][r - 1]<br />
'''if''' i * block_size + r &le; N '''and''' A[i * block_size + block_min[t][l][r]] > A[i * block_size + r]<br />
block_min[t][l][r] = r<br />
<br />
'''function''' block_RMQ(block_number: '''int''', l: '''int''', r: '''int'''): '''int'''<br />
'''return''' block_min[type[block_number]][l][r] + block_number * block_size<br />
<br />
'''function''' RMQ(l: '''int''', r: '''int'''): '''int'''<br />
bl = l / block_size<br />
br = r / block_size<br />
'''if''' bl = br <font color=green>// если оба индекса внутри одного блока</font><br />
'''return''' A[block_RMQ(bl, l % block_size, r % block_size)]<br />
'''if''' bl + 1 < br <font color=green>// найдем минимум на блоках между крайними, если таковые есть</font><br />
power = log(br - bl - 1)<br />
ansb = min(A[ST[bl + 1][power]], A[ST[br - (1 << power)][power]])<br />
ansl = A[block_RMQ(bl, l % block_size, block_size - 1)] <font color=green>// найдем минимум на отрезке от l до конца блока, содержащего l</font><br />
ansr = A[block_RMQ(bl, 0, r % block_size)] <font color=green>// найдем минимум от начала блока, содержащего r, до r </font> <br />
'''return''' min(ansb, min(ansl, ansr))<br />
<br />
=== Результат ===<br />
Итого, на предподсчёт требуется <tex>O(N)</tex> времени и памяти, а ответ на запрос вычисляется за <tex>O(1)</tex>.<br />
<br />
== См. также ==<br />
* [[Решение RMQ с помощью разреженной таблицы]]<br />
* [[Сведение задачи RMQ к задаче LCA]]<br />
* [[Сведение задачи LCA к задаче RMQ]]<br />
<br />
==Источники информации==<br />
* Bender, M.A., Farach-Colton, M. {{---}} The LCA Problem Revisited. LATIN (2000), с. 88-94<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Задача о наименьшем общем предке]]</div>93.175.2.117http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D0%B0%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0_%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D0%BE%D0%B3%D0%BE&diff=72199Диаграмма Вороного2020-01-20T12:03:20Z<p>93.175.2.117: /* Алгоритм Чана */</p>
<hr />
<div>== Определения ==<br />
=== Совсем неформальное определение ===<br />
[[Файл:voronoi-diagram.png|200px|thumb|right|Пример диаграммы Вороного]]<br />
Пусть есть карта города, на которой точками обозначены почтовые отделения. Человек хочет отправить письмо, и он пойдёт на ближайшую почту. Ему интересно знать, какое отделение ближе, для любой точки города — необходимость отправить письмо может наступить неожиданно. Для этого он может взять карту и расчертить её на ячейки так, чтобы внутри каждой ячейки находилось только одно отделение, а для всех остальных точек ячейки именно эта почта была ближайшей. Полученная картинка и будет диаграммой Вороного для точек-почт.<br />
<br />
=== Неформальное определение ===<br />
Есть множество точек <tex>P</tex> на плоскости. Кусочек плоскости из точек <tex>q</tex> такой, что для всех <tex>q</tex> ближайшей точкой из множества <tex>P</tex> является одна и та же точка <tex>p</tex>, называется ячейкой Вороного точки <tex>p</tex>. Разбиение плоскости на такие ячейки для всех точек <tex>p_i \in P</tex> называется диаграммой Вороного для множества <tex>P</tex>.<br />
<br />
=== Формальное определение ===<br />
<tex>P = \{ p_1, p_2, ..., p_n\}</tex> — множество точек на плоскости.<br />
<br />
{{Определение<br />
|definition=<tex>p_i \in P</tex> называется '''сайтом''' (''site'').<br />
}}<br />
<br />
{{Определение<br />
|definition='''Ячейка Вороного''' (''Voronoi cell'', <tex>\mathcal{V}(p_i)</tex>) — множество точек плоскости <tex>q</tex> таких, что для фиксированного сайта <tex>p_i</tex> и любых других сайтов <tex>p_j \in P, \ j \neq i</tex> верно неравенство <tex>\rho(q, p_i) < \rho(q, p_j)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition='''Диаграмма Вороного''' (''Voronoi diagram'', <tex>Vor(P)</tex>) для сайтов <tex>P = \{ p_1, p_2, ..., p_n\}</tex> на плоскости — это разбиение плоскости на ячейки Вороного для каждого сайта из <tex>P</tex>.<br />
}}<br />
<br />
В зависимости от контекста будем называть диаграммой Вороного как разбиение на ячейки, так и [[Основные определения теории графов|граф]] из вершин и рёбер, составляющих эти ячейки.<br />
<br />
== Свойства ==<br />
=== Связь с пересечением полуплоскостей ===<br />
Возьмём две точки плоскости: <tex>p</tex> и <tex>q</tex>. Проведём серединный перпендикуляр к отрезку <tex>pq</tex>; полученную полуплоскость, которая содержит в себе <tex>p</tex>, обозначим <tex>h(p, q)</tex>, другую — <tex>h(q, p)</tex>. Заметим, что для точки <tex>r</tex> выполняется <tex>r \in h(p, q)</tex> тогда и только тогда, когда <tex>\rho(r, p) < \rho(r, q)</tex>. Отсюда вытекает следующее:<br />
{{Утверждение<br />
|id=intersect<br />
|statement=<tex>\mathcal{V}(p_i) = \bigcap\limits_{1 \leqslant j \leqslant n, j \neq i} h(p_i, p_j)</tex><br />
}}<br />
Отсюда получаем, что ячейка Вороного — это пересечение <tex>n - 1</tex> полуплоскостей, и поэтому представляет собой (возможно, неограниченную) открытую выпуклую область с не более чем <tex>n - 1</tex> вершинами и <tex>n - 1</tex> рёбрами.<br />
<br />
=== Топология диаграммы Вороного ===<br />
{{Теорема<br />
|statement=Пусть <tex>P</tex> — множество из <tex>n</tex> сайтов. Если они все лежат на одной прямой, то <tex>Vor(P)</tex> представляет собой <tex>n - 1</tex> параллельную прямую. Иначе <tex>Vor(P)</tex> связная и все её рёбра — либо отрезки, либо лучи.<br />
|proof=[[Файл:voronoi-not-lines.png|200px|right]] В случае, если все сайты лежат на одной прямой, каждая пара соседних сайтов порождает серединный перпендикуляр к отрезку, содержащему их, и, соответственно, к прямой, которая содержит все сайты. Так получаются <tex>n - 1</tex> прямая, каждая из которых перпендикулярна прямой, содержащей сайты, а значит, эти прямые параллельны.<br />
<br />
Рассмотрим теперь случай, когда сайты не лежат на одной прямой. Покажем, что рёбра — это отрезки или лучи, от противного. Предположим, что есть ребро <tex>e</tex>, являющееся прямой. Пусть оно — граница ячеек <tex>\mathcal{V}(p_i)</tex> и <tex>\mathcal{V}(p_j)</tex>. Пусть точка <tex>p_k \in P</tex> не лежит на прямой <tex>p_i p_j</tex> (по условию такая точка существует). Тогда серединный перпендикуляр к <tex>p_j p_k</tex> не параллелен <tex>e</tex>, и, значит, он его пересекает. Но тогда та часть <tex>e</tex>, что лежит в <tex>h(p_k, p_j)</tex>, не может быть границей <tex>\mathcal{V}(p_j)</tex>, потому что она ближе к <tex>p_k</tex>, чем к <tex>p_j</tex>. Пришли к противоречию.<br />
<br />
Докажем теперь, что диаграмма связна. Предположим, что это не так. Тогда на её рёбрах найдутся две точки <tex>s</tex> и <tex>t</tex>, между которыми нет пути по рёбрам диаграммы. Рассмотрим отрезок <tex>st</tex>. Он пересекает некоторое количество ячеек диаграммы. Пусть он пересекает какую-то ячейку в точках <tex>a</tex> и <tex>b</tex>. От точки <tex>a</tex> до точки <tex>b</tex> можно добраться по рёбрам тогда и только тогда, когда ячейка связна. Раз пути из <tex>s</tex> в <tex>t</tex> нет, то какая-то из ячеек, пересекаемых отрезком <tex>st</tex>, несвязная. Это возможно, только если она представляет собой полосу, ограниченную двумя параллельными прямыми. Но в нашем случае в диаграмме не может быть прямых, пришли к противоречию.<br />
<br />
[[Файл:voronoi-connected.png|500px]]<br />
}}<br />
<br />
=== Размер структуры ===<br />
{{Теорема<br />
|statement=Для <tex>n \geqslant 3</tex> сайтов диаграмма Вороного содержит не больше <tex>2n - 5</tex> вершин и <tex> 3n - 6</tex> рёбер.<br />
|proof=[[Файл:voronoi-infinite-vertex.png|200px|right]]Для случая сайтов, лежащих на одной прямой, утверждение напрямую следует из вида диаграммы для этого случая, поэтому рассмотрим общий случай. По [[Формула Эйлера|формуле Эйлера]] <tex>v - e + f = 2</tex>, где <tex>v</tex> — число вершин, <tex>e</tex> — число рёбер и <tex>f</tex> — число граней связного планарного графа. Мы не можем сразу применить эту формулу к <tex>Vor(P)</tex>, потому что в этом графе есть полубесконечные рёбра. Поэтому добавим вершину <tex>v_\infty</tex>, и все полубесконечные рёбра мы превратим в рёбра, инцидентные ей. Таким образом мы увеличили число вершин на одну, а число рёбер не изменилось. Число граней равно <tex>n</tex> по определению диаграммы Вороного. Тогда по формуле Эйлера получаем <tex>(v + 1) - e + n = 2</tex>.<br />
Сумма степеней всех вершин полученного графа равна <tex>2e</tex>, так как у каждого ребра есть ровно два конца (нет петель). Также из каждой вершины исходят как минимум три ребра. Отсюда получаем <tex>2e \geqslant 3 (v + 1)</tex>.<br />
Домножим равенство на два и вычтем из него полученную нижнюю границу для <tex>2 \cdot e</tex>, в результате получим <tex> v \leqslant 2n - 5</tex>. Далее подставим этот результат в равенство и получим <tex>e \leqslant 3n - 6</tex>, что и требовалось доказать.<br />
}}<br />
<br />
=== Связь с триангуляцией Делоне ===<br />
{{Определение<br />
|definition='''Наибольшая пустая окружность''' точки <tex>q</tex> по отношению к <tex>P</tex> (''largest empty circle of ''<tex>q</tex>'' with respect to ''<tex>P</tex>, <tex>C_P(q)</tex>) — наибольшая окружность с центром в <tex>q</tex> такая, что во внутренности соответствующего ей круга не лежит ни одного сайта из <tex>P</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement=Точка <tex>q</tex> — вершина диаграммы Вороного в том и только в том случае, когда <tex>C_P(q)</tex> содержит три и более сайтов на своей границе.<br />
|proof=Предположим, что <tex>q</tex> существует, а <tex>p_i, \ p_j, \ p_k</tex> — соответствующие точки. Так как внутри <tex>C_P(q)</tex> нет других сайтов, а <tex>q</tex> равноудалена от точек <tex>p_i, \ p_j, \ p_k</tex>, <tex>q</tex> должна быть на границе <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex> одновременно, то есть вершиной диаграммы.<br />
Докажем в другую сторону: каждая вершина <tex>q</tex> диаграммы инцидентна минимум трём рёбрам, и, поэтому, как минимум трём ячейкам <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex>. Тогда <tex>q</tex> лежит на равном расстоянии от <tex>p_i, \ p_j, \ p_k</tex> и не может быть другого сайта ближе к <tex>q</tex>, так как иначе <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex> не сойдутся в <tex>q</tex>. Поэтому можно построить окружность с центром в <tex>q</tex> и <tex>p_i, \ p_j, \ p_k</tex> на границе так, что внутри не будет других сайтов.<br />
}}<br />
<br />
{{Лемма<br />
|statement=Серединный перпендикуляр к отрезку <tex>p_i p_j</tex> образует ребро диаграммы Вороного в том и только в том случае, если на нём есть точка <tex>q</tex> такая, что <tex>C_P(q)</tex> содержит на своей границе только сайты <tex>p_i, \ p_j</tex>.<br />
|proof=[[Файл:voronoi-circles.png|200px|right]]Предположим, что <tex>q</tex> существует. Тогда, так как <tex>C_P(q)</tex> не содержит в себе сайтов и содержит <tex>p_i, \ p_j</tex> на границе, <tex> \rho(q, p_i) = \rho(q, p_j) \leqslant \rho(q, p_k), \ 1 \leqslant k \leqslant n</tex>. Отсюда выходит, что <tex>q</tex> — вершина <tex>Vor(P)</tex> или лежит на ребре диаграммы. Но по предыдущей лемме выходит, что <tex>q</tex> не может быть вершиной диаграммы. Значит, она лежит на ребре, заданном серединным перпендикуляром к <tex>p_i p_j</tex>.<br />
<br />
Докажем в другую сторону: пусть серединный перпендикуляр к <tex>p_i p_j</tex> задаёт ребро диаграммы. Наибольшая пустая окружность любой точки <tex>q</tex> на этом ребре должна содержать на границе <tex>p_i</tex> и <tex>p_j</tex> (так как <tex>q</tex> равноудалена от <tex>p_i</tex> и <tex>p_j</tex>). Также эта окружность не должна содержать никаких других сайтов на границе, так как тогда она является вершиной.<br />
}}<br />
<br />
{{Теорема<br />
|statement=Если соединить все сайты, соответствующие смежным ячейкам диаграммы Вороного, получится [[триангуляция Делоне]] для этого множества точек.<br />
|proof=Если ячейки, соответствующие сайтам <tex>p_i, \ p_j</tex>, смежны, то серединный перпендикуляр к отрезку <tex>p_i p_j</tex> образует ребро диаграммы Вороного, то есть к нему применима предыдущая лемма и можно построить окружность с <tex>p_i</tex> и <tex>p_j</tex> на границе, внутри которой не будет других сайтов. Триангуляции Делоне принадлежат [[Триангуляция Делоне#Критерий Делоне для рёбер|те и только те]] рёбра (с поправкой на точки, лежащие на одной окружности), на которых можно построить такую окружность, что внутри неё не будет лежать никаких точек. Тогда ребро <tex>p_i p_j</tex> является ребром триангуляции Делоне. За счёт равносильности в обеих используемых леммах мы добавим все рёбра и не построим лишних.<br />
}}<br />
<br />
== Построение ==<br />
=== Наивный алгоритм ===<br />
Будем [[Пересечение полуплоскостей, связь с выпуклыми оболочками|пересекать полуплоскости]] по [[#intersect|свойству ячейки диаграммы]]. Необходимо для каждого сайта пересечь <tex>n - 1</tex> плоскость, что суммарно делается за <tex>O(n^2 \log n)</tex>.<br />
<br />
=== Инкрементальный алгоритм ===<br />
Храним диаграмму в [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]]. Пусть у нас уже есть диаграмма для точек <tex>p_1, p_2, ..., p_i</tex>. Добавим новый сайт <tex>p_{i+1}</tex>. Сначала найдём сайт <tex>p_j</tex>, в ячейку которого попадает <tex>p_{i+1}</tex>, перебором. После этого строим новую ячейку: сначала проведём серединный перпендикуляр для <tex>p_{i+1}p_j</tex>, он пересечёт границу ячейки <tex>\mathcal{V}(p_j)</tex> с ячейкой <tex>\mathcal{V}(p_k)</tex>; на следующем шаге будем строить серединный перпендикуляр для <tex>p_{i+1} p_k</tex> и так далее.<br />
<br />
В процессе построения перпендикуляров необходимо обновлять РСДС. Каждый раз, когда новое полуребро <tex>e</tex>, порождаемое <tex>p_{i+1}</tex> и <tex>p_j</tex>, пересекает существовавшее ранее полуребро <tex>e'</tex>, создаётся новая вершина <tex>v</tex> и начинается новое полуребро <tex>e+1</tex>.<br />
<br />
Обновление РСДС происходит следующим образом:<br />
<br />
* создаём вершину <tex>v</tex> с полуребром <tex>e</tex>;<br />
* для полуребра <tex>e</tex> в РСДС второй конец в вершине <tex>v</tex>, следующее полуребро — <tex>e'</tex>, инцидентные грани — слева <tex>\mathcal{V}(i+1)</tex>, справа — <tex>\mathcal{V}(j)</tex>;<br />
* добавляем в РСДС полуребро <tex>e + 1</tex> с началом в <tex>v</tex> и предыдущим полуребром <tex>e</tex>;<br />
* удаляем все полурёбра, лежащие между вершиной начала <tex>e</tex> и вершиной конца <tex>e</tex>, по часовой стрелке;<br />
* обновляем полуребро, соответствующее грани для <tex>\mathcal{V}(p_j)</tex> — им становится <tex>e</tex>.<br />
<br />
Каждый шаг выполняется за <tex>O(i)</tex>, значит, суммарно диаграмма из <tex>n</tex> сайтов с нуля создаётся за <tex>O(n^2)</tex>.<br />
<br />
{|<br />
|[[Файл:voronoi-incremental-zero-step.png|200px|thumb|Локализация]]<br />
|[[Файл:voronoi-incremental-first-step.png|200px|thumb|Добавление первого ребра]]<br />
|[[Файл:voronoi-incremental.png|200px|thumb|Добавление третьего ребра]]<br />
|[[Файл:voronoi-update-dcel.png|400px|thumb|Обновление структуры при добавлении ребра]]<br />
|}<br />
<br />
=== Алгоритм Форчуна ===<br />
Построение производится при помощи заметающей прямой и парабол позади неё (параболы в данном случае - это множества точек, равноудалённых от вершины и прямой). Сама диаграмма "рисуется" местами соприкасания соседних парабол. Несмотря на то, что в теории движение прямой происходит непрерывно, сам алгоритм обрабатывает только крайние случаи, когда происходят события. Рассматривается 2 типа событий - появление новой параболы, когда заметающая прямая касается вершины, и схлопывание параболы - когда две соседние параболы её полностью накрывают. Всего событий <tex>O(n)</tex> (<tex>n</tex> - число вершин). Для каждого события вычисляется его время (позиция заметающей прямой), события кладутся в очередь с приоритетом (отсюда <tex>O(\log n)</tex> по времени) и обрабатываются, пока очередь непуста. При обработке событий также записываются пары взаимодействующих вершин (у которых сайты имеют общую границу), это и является результатом работы алгоритма.<br />
<br />
Сложность работы алгоритма - <tex>O(n \log n)</tex> по времени и <tex>O(n)</tex> по памяти.<br />
<br />
Более подробно:<br />
* [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BE%D1%80%D1%87%D1%83%D0%BD%D0%B0 Описание алгоритма на Wikipedia]<br />
* [https://www2.cs.sfu.ca/~binay/813.2011/Fortune.pdf Презентация с описанием в деталях]<br />
<br />
=== Алгоритм Чана ===<br />
Вершины проецируются из двумерной плоскости на поверхность параболоида (<tex>x, y</tex> остаются те же, добавляется <tex>z = x^2 + y^2</tex>). Далее по ним строится нижняя [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|выпуклая оболочка]]. Поскольку параболоид выпуклый, никакие вершины не будут удалены. На выходе получаются рёбра между вершинами, которые соответствуют триангуляции Делоне. Сложность работы - <tex>O(n \log n)</tex>.<br />
<br />
== Диаграмма k-го порядка ==<br />
{{Определение<br />
|definition='''Ячейка Вороного''' <tex>k</tex>'''-го порядка''' (<tex>\mathcal{V}_k(p_1, p_2, ..., p_k)</tex>) — множество точек, имеющих в качестве ближайших <tex>k</tex> соседей множество сайтов <tex>p_1, p_2, ..., p_k</tex>.<br />
}}<br />
<br />
Чтобы построить диаграмму <tex>k</tex>-го порядка, возьмём диаграмму <tex>k - 1</tex>-го порядка. Каждая ячейка построена для некоторого набора <tex>k-1</tex> сайтов. Обозначим множество этих сайтов за <tex>S</tex>. [[Пересечение выпуклых многоугольников|Пересечём]] каждую из этих ячеек с ячейками диаграммы первого порядка, построенной на множестве сайтов <tex>P \setminus S</tex>. Когда мы пересекаем ячейку <tex>k-1</tex>-го порядка для точек <tex>S</tex> с ячейкой первого порядка для точки <tex>p_i</tex>, получаем ячейку для множества <tex>S \cup \{p_i\}</tex>. После пересечения ячеек необходимо объединить те, которые отвечают за одинаковый набор сайтов (это могут быть только соседние по ребру ячейки).<br />
<br />
Итого совершаем <tex>k</tex> шагов, на каждом строим <tex>O(n)</tex> диграмм Вороного за время <tex>O(n^3)</tex>, пересекаем <tex>O(n)</tex> ячеек с <tex>O(n)</tex> ячейками за <tex>O(n)</tex> времени, а потом объединяем ячейки за <tex>O(n)</tex> (линейное количество соседних рёбер ячейки, а объединение происходит за <tex>O(1)</tex> за счёт структуры РСДС). Итого <tex>O(k \cdot n^3)</tex>.<br />
<br />
{|<br />
|[[Файл:voronoi-first-order.png|200px|thumb|Диаграмма первого порядка]]<br />
|[[Файл:voronoi-second-order.png|200px|thumb|Диаграмма второго порядка]]<br />
|[[Файл:voronoi-third-order.png|200px|thumb|Диаграмма третьего порядка]]<br />
|[[Файл:voronoi-tenth-order.png|200px|thumb|Диаграмма <tex>n - 1</tex>-го порядка (она же farthest-point диаграмма) для данного набора сайтов]]<br />
|}<br />
<br />
== Farthest-point диаграмма ==<br />
{{Определение<br />
|definition=Диаграмма <tex>n - 1</tex>-го порядка является '''farthest-point диаграммой''', т.е. в каждой её ячейке все точки являются наиболее удалёнными от какого-то сайта.<br />
}}<br />
<br />
=== Свойства ===<br />
{{Лемма<br />
|statement=Для любой точки <tex>q</tex> плоскости самый удалённый от неё сайт из <tex>P</tex> должен лежать на [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|выпуклой оболочке]] <tex>P</tex>.<br />
|proof=[[Файл:voronoi-farthest-inside.png|200px|right]]Сайт, не находящийся на выпуклой оболочке, лежит внутри неё по свойствам выпуклой оболочки.<br />
<br />
Пусть самый удалённый от точки <tex>q</tex> сайт <tex>p_i</tex> не лежит на выпуклой оболочке (т.е. лежит внутри неё). Проведём луч <tex>q p_i</tex>. Он пересечёт ребро выпуклой оболочки <tex>p_j p_k</tex>. Получатся два смежных угла, рассмотрим тот, который оказался прямым или тупым. Тогда в полученном треугольнике <tex>\rho(q, p_j) > \rho(q, p_i)</tex>, так как напротив большего угла лежит большая сторона. Пришли к противоречию.<br />
}}<br />
<br />
{{Лемма<br />
|statement=Сайт, который лежит внутри выпуклой оболочки сайтов, не может иметь ячейку в farthest-point диаграмме.<br />
|proof=Пусть это не так и сайт <tex>p</tex> лежит внутри выпуклой оболочки и имеет ячейку в farthest-point диаграмме. Тогда внутри неё есть точка <tex>q</tex>. Но по предыдущей лемме самый удалённый для <tex>q</tex> сайт лежит на выпуклой оболочке, а значит, сайт <tex>p</tex> не может быть самым удалённым для <tex>q</tex>. Пришли к противоречию.<br />
}}<br />
<br />
{{Лемма<br />
|statement=Каждый сайт, который является вершиной выпуклой оболочки сайтов, имеет ячейку в farthest-point диаграмме.<br />
|proof=Докажем по индукции.<br />
<br />
База индукции: для двух сайтов они оба являются вершинами выпуклой оболочки и оба имеют ячейку в farthest-point диаграмме (дальняя от сайта полуплоскость).<br />
<br />
Переход: добавим сайт <tex>p</tex> так, что он станет новой вершиной выпуклой оболочки. Пусть он не имеет ячейку в farthest-point диаграмме, то есть уже имеющаяся перед его добавлением диаграмма не меняется. Для построения farthest-point диаграммы проводятся серединные перпендикуляры между всеми парами сайтов, и полученные полуплоскости пересекаются; раз новой ячейки не добавилось, то серединные перпендикуляры между <tex>p</tex> и остальными сайтами совпали с уже имеющимися перпендикулярами. Это возможно, только если <tex>p</tex> совпал с другим сайтом. Пришли к противоречию.<br />
}}<br />
<br />
{{Утверждение<br />
|statement=Сайт имеет ячейку в farthest-point диаграмме тогда и только тогда, когда он является вершиной выпуклой оболочки всех сайтов.<br />
|proof=Непосредственно следует из двух предыдущих лемм.<br />
}}<br />
<br />
{{Утверждение<br />
|statement=Все ячейки в farthest-point диаграмме неограничены.<br />
|proof=[[Файл:voronoi-farthest-unbounded.png|200px|right]]Пусть <tex>p_i</tex> — сайт на выпуклой оболочке сайтов, а <tex>q</tex> — точка, для которой он является наиболее удалённым. Тогда для всех точек на луче, лежащем на <tex>p_i q</tex>, начинающемся в <tex>q</tex> и не проходящим через <tex>p_i</tex>, сайт <tex>p_i</tex> будет наиболее удалённым среди остальных сайтов. Значит, ячейка сайта <tex>p_i</tex> в farthest-point диаграмме включает в себя этот луч, а значит, неограничена.<br />
}}<br />
<br />
=== Алгоритм ===<br />
Чтобы найти farthest-point диаграмму, сначала найдём выпуклую оболочку всех сайтов. Обозначим сайты, её образующие, через <tex>p_1, p_2, ..., p_m</tex>. Запомним порядки обхода для каждой вершины выпуклой оболочки по часовой стрелке (<tex>cw(p_i)</tex>) и против часовой (<tex>ccw(p_i)</tex>) и сделаем случайную перестановку точек. Далее удаляем из выпуклой оболочки все точки, кроме первых трёх (запоминая при этом их соседей в оболочке на момент удаления). После этого строим farthest-point диаграмму для первых трёх точек (пересекая полуплоскости) и последовательно добавляем остальные (удалённые) в порядке, обратном порядку удаления.<br />
<br />
{|<br />
|[[Файл:voronoi-farthest-construct.png|600px|thumb|Построение очередной ячейки farthest-point диаграммы]]<br />
|}<br />
<br />
Для точки <tex>p_i</tex> ячейка встанет «между» ячейками, соответствующими <tex>cw(p_i)</tex> и <tex>ccw(p_i)</tex>. Перед добавлением <tex>p_i</tex> <tex>cw(p_i)</tex> и <tex>ccw(p_i)</tex> — соседи, поэтому между ними построен серединный перпендикуляр. Серединный перпендикуляр к <tex>p_i ccw(p_i)</tex> даст новое ребро, которое лежит в farthest-point ячейке <tex>ccw(p_i)</tex> и является частью границы ячейки <tex> p_i</tex>. Обойдём ячейку <tex>ccw(p_i)</tex> по часовой стрелке, чтоб понять, какое ребро пересечёт перпендикуляр. С другой стороны этого ребра лежит ячейка какой-то точки <tex>p_j</tex>, и серединный перпендикуляр <tex>p_i p_j</tex> тоже даст ребро ячейке <tex>p_i</tex>. Аналогично совершим обход и так далее. Последний серединный перпендикуляр будет построен для <tex>p_i cw(p_i)</tex>. После этого удаляем рёбра, которые лежат внутри новой ячейки.<br />
<br />
== См. также ==<br />
* [[Трапецоидная карта]]<br />
* [[Триангуляция Делоне]]<br />
* [[Straight skeleton]]<br />
<br />
== Источники ==<br />
* de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 147-151, 164-166<br />
* [http://students.info.uaic.ro/~emilian.necula/vor2.pdf Algorithms for constructing Voronoi diagrams, Vera Sacrist´an {{---}} Incremental algorithm]<br />
* [http://en.wikipedia.org/wiki/Voronoi_diagram Wikipedia — Voronoi diagram]<br />
* [https://web.archive.org/web/20170329014016/http://www.cs.uu.nl/docs/vakken/ga/slides7b.pdf Computational Geometry {{---}} Lecture 13: More on Voronoi diagrams]<br />
<br />
[[Категория: Вычислительная геометрия]]<br />
[[Категория: Триангуляция Делоне и диаграмма Вороного]]</div>93.175.2.117http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D0%B0%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0_%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D0%BE%D0%B3%D0%BE&diff=72198Диаграмма Вороного2020-01-20T12:00:11Z<p>93.175.2.117: /* Построение */ А что про Форчуна и Чана ничего не написано? Добавил. Если у кого есть желание - дополните и приведите к нормальному виду.</p>
<hr />
<div>== Определения ==<br />
=== Совсем неформальное определение ===<br />
[[Файл:voronoi-diagram.png|200px|thumb|right|Пример диаграммы Вороного]]<br />
Пусть есть карта города, на которой точками обозначены почтовые отделения. Человек хочет отправить письмо, и он пойдёт на ближайшую почту. Ему интересно знать, какое отделение ближе, для любой точки города — необходимость отправить письмо может наступить неожиданно. Для этого он может взять карту и расчертить её на ячейки так, чтобы внутри каждой ячейки находилось только одно отделение, а для всех остальных точек ячейки именно эта почта была ближайшей. Полученная картинка и будет диаграммой Вороного для точек-почт.<br />
<br />
=== Неформальное определение ===<br />
Есть множество точек <tex>P</tex> на плоскости. Кусочек плоскости из точек <tex>q</tex> такой, что для всех <tex>q</tex> ближайшей точкой из множества <tex>P</tex> является одна и та же точка <tex>p</tex>, называется ячейкой Вороного точки <tex>p</tex>. Разбиение плоскости на такие ячейки для всех точек <tex>p_i \in P</tex> называется диаграммой Вороного для множества <tex>P</tex>.<br />
<br />
=== Формальное определение ===<br />
<tex>P = \{ p_1, p_2, ..., p_n\}</tex> — множество точек на плоскости.<br />
<br />
{{Определение<br />
|definition=<tex>p_i \in P</tex> называется '''сайтом''' (''site'').<br />
}}<br />
<br />
{{Определение<br />
|definition='''Ячейка Вороного''' (''Voronoi cell'', <tex>\mathcal{V}(p_i)</tex>) — множество точек плоскости <tex>q</tex> таких, что для фиксированного сайта <tex>p_i</tex> и любых других сайтов <tex>p_j \in P, \ j \neq i</tex> верно неравенство <tex>\rho(q, p_i) < \rho(q, p_j)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition='''Диаграмма Вороного''' (''Voronoi diagram'', <tex>Vor(P)</tex>) для сайтов <tex>P = \{ p_1, p_2, ..., p_n\}</tex> на плоскости — это разбиение плоскости на ячейки Вороного для каждого сайта из <tex>P</tex>.<br />
}}<br />
<br />
В зависимости от контекста будем называть диаграммой Вороного как разбиение на ячейки, так и [[Основные определения теории графов|граф]] из вершин и рёбер, составляющих эти ячейки.<br />
<br />
== Свойства ==<br />
=== Связь с пересечением полуплоскостей ===<br />
Возьмём две точки плоскости: <tex>p</tex> и <tex>q</tex>. Проведём серединный перпендикуляр к отрезку <tex>pq</tex>; полученную полуплоскость, которая содержит в себе <tex>p</tex>, обозначим <tex>h(p, q)</tex>, другую — <tex>h(q, p)</tex>. Заметим, что для точки <tex>r</tex> выполняется <tex>r \in h(p, q)</tex> тогда и только тогда, когда <tex>\rho(r, p) < \rho(r, q)</tex>. Отсюда вытекает следующее:<br />
{{Утверждение<br />
|id=intersect<br />
|statement=<tex>\mathcal{V}(p_i) = \bigcap\limits_{1 \leqslant j \leqslant n, j \neq i} h(p_i, p_j)</tex><br />
}}<br />
Отсюда получаем, что ячейка Вороного — это пересечение <tex>n - 1</tex> полуплоскостей, и поэтому представляет собой (возможно, неограниченную) открытую выпуклую область с не более чем <tex>n - 1</tex> вершинами и <tex>n - 1</tex> рёбрами.<br />
<br />
=== Топология диаграммы Вороного ===<br />
{{Теорема<br />
|statement=Пусть <tex>P</tex> — множество из <tex>n</tex> сайтов. Если они все лежат на одной прямой, то <tex>Vor(P)</tex> представляет собой <tex>n - 1</tex> параллельную прямую. Иначе <tex>Vor(P)</tex> связная и все её рёбра — либо отрезки, либо лучи.<br />
|proof=[[Файл:voronoi-not-lines.png|200px|right]] В случае, если все сайты лежат на одной прямой, каждая пара соседних сайтов порождает серединный перпендикуляр к отрезку, содержащему их, и, соответственно, к прямой, которая содержит все сайты. Так получаются <tex>n - 1</tex> прямая, каждая из которых перпендикулярна прямой, содержащей сайты, а значит, эти прямые параллельны.<br />
<br />
Рассмотрим теперь случай, когда сайты не лежат на одной прямой. Покажем, что рёбра — это отрезки или лучи, от противного. Предположим, что есть ребро <tex>e</tex>, являющееся прямой. Пусть оно — граница ячеек <tex>\mathcal{V}(p_i)</tex> и <tex>\mathcal{V}(p_j)</tex>. Пусть точка <tex>p_k \in P</tex> не лежит на прямой <tex>p_i p_j</tex> (по условию такая точка существует). Тогда серединный перпендикуляр к <tex>p_j p_k</tex> не параллелен <tex>e</tex>, и, значит, он его пересекает. Но тогда та часть <tex>e</tex>, что лежит в <tex>h(p_k, p_j)</tex>, не может быть границей <tex>\mathcal{V}(p_j)</tex>, потому что она ближе к <tex>p_k</tex>, чем к <tex>p_j</tex>. Пришли к противоречию.<br />
<br />
Докажем теперь, что диаграмма связна. Предположим, что это не так. Тогда на её рёбрах найдутся две точки <tex>s</tex> и <tex>t</tex>, между которыми нет пути по рёбрам диаграммы. Рассмотрим отрезок <tex>st</tex>. Он пересекает некоторое количество ячеек диаграммы. Пусть он пересекает какую-то ячейку в точках <tex>a</tex> и <tex>b</tex>. От точки <tex>a</tex> до точки <tex>b</tex> можно добраться по рёбрам тогда и только тогда, когда ячейка связна. Раз пути из <tex>s</tex> в <tex>t</tex> нет, то какая-то из ячеек, пересекаемых отрезком <tex>st</tex>, несвязная. Это возможно, только если она представляет собой полосу, ограниченную двумя параллельными прямыми. Но в нашем случае в диаграмме не может быть прямых, пришли к противоречию.<br />
<br />
[[Файл:voronoi-connected.png|500px]]<br />
}}<br />
<br />
=== Размер структуры ===<br />
{{Теорема<br />
|statement=Для <tex>n \geqslant 3</tex> сайтов диаграмма Вороного содержит не больше <tex>2n - 5</tex> вершин и <tex> 3n - 6</tex> рёбер.<br />
|proof=[[Файл:voronoi-infinite-vertex.png|200px|right]]Для случая сайтов, лежащих на одной прямой, утверждение напрямую следует из вида диаграммы для этого случая, поэтому рассмотрим общий случай. По [[Формула Эйлера|формуле Эйлера]] <tex>v - e + f = 2</tex>, где <tex>v</tex> — число вершин, <tex>e</tex> — число рёбер и <tex>f</tex> — число граней связного планарного графа. Мы не можем сразу применить эту формулу к <tex>Vor(P)</tex>, потому что в этом графе есть полубесконечные рёбра. Поэтому добавим вершину <tex>v_\infty</tex>, и все полубесконечные рёбра мы превратим в рёбра, инцидентные ей. Таким образом мы увеличили число вершин на одну, а число рёбер не изменилось. Число граней равно <tex>n</tex> по определению диаграммы Вороного. Тогда по формуле Эйлера получаем <tex>(v + 1) - e + n = 2</tex>.<br />
Сумма степеней всех вершин полученного графа равна <tex>2e</tex>, так как у каждого ребра есть ровно два конца (нет петель). Также из каждой вершины исходят как минимум три ребра. Отсюда получаем <tex>2e \geqslant 3 (v + 1)</tex>.<br />
Домножим равенство на два и вычтем из него полученную нижнюю границу для <tex>2 \cdot e</tex>, в результате получим <tex> v \leqslant 2n - 5</tex>. Далее подставим этот результат в равенство и получим <tex>e \leqslant 3n - 6</tex>, что и требовалось доказать.<br />
}}<br />
<br />
=== Связь с триангуляцией Делоне ===<br />
{{Определение<br />
|definition='''Наибольшая пустая окружность''' точки <tex>q</tex> по отношению к <tex>P</tex> (''largest empty circle of ''<tex>q</tex>'' with respect to ''<tex>P</tex>, <tex>C_P(q)</tex>) — наибольшая окружность с центром в <tex>q</tex> такая, что во внутренности соответствующего ей круга не лежит ни одного сайта из <tex>P</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement=Точка <tex>q</tex> — вершина диаграммы Вороного в том и только в том случае, когда <tex>C_P(q)</tex> содержит три и более сайтов на своей границе.<br />
|proof=Предположим, что <tex>q</tex> существует, а <tex>p_i, \ p_j, \ p_k</tex> — соответствующие точки. Так как внутри <tex>C_P(q)</tex> нет других сайтов, а <tex>q</tex> равноудалена от точек <tex>p_i, \ p_j, \ p_k</tex>, <tex>q</tex> должна быть на границе <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex> одновременно, то есть вершиной диаграммы.<br />
Докажем в другую сторону: каждая вершина <tex>q</tex> диаграммы инцидентна минимум трём рёбрам, и, поэтому, как минимум трём ячейкам <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex>. Тогда <tex>q</tex> лежит на равном расстоянии от <tex>p_i, \ p_j, \ p_k</tex> и не может быть другого сайта ближе к <tex>q</tex>, так как иначе <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex> не сойдутся в <tex>q</tex>. Поэтому можно построить окружность с центром в <tex>q</tex> и <tex>p_i, \ p_j, \ p_k</tex> на границе так, что внутри не будет других сайтов.<br />
}}<br />
<br />
{{Лемма<br />
|statement=Серединный перпендикуляр к отрезку <tex>p_i p_j</tex> образует ребро диаграммы Вороного в том и только в том случае, если на нём есть точка <tex>q</tex> такая, что <tex>C_P(q)</tex> содержит на своей границе только сайты <tex>p_i, \ p_j</tex>.<br />
|proof=[[Файл:voronoi-circles.png|200px|right]]Предположим, что <tex>q</tex> существует. Тогда, так как <tex>C_P(q)</tex> не содержит в себе сайтов и содержит <tex>p_i, \ p_j</tex> на границе, <tex> \rho(q, p_i) = \rho(q, p_j) \leqslant \rho(q, p_k), \ 1 \leqslant k \leqslant n</tex>. Отсюда выходит, что <tex>q</tex> — вершина <tex>Vor(P)</tex> или лежит на ребре диаграммы. Но по предыдущей лемме выходит, что <tex>q</tex> не может быть вершиной диаграммы. Значит, она лежит на ребре, заданном серединным перпендикуляром к <tex>p_i p_j</tex>.<br />
<br />
Докажем в другую сторону: пусть серединный перпендикуляр к <tex>p_i p_j</tex> задаёт ребро диаграммы. Наибольшая пустая окружность любой точки <tex>q</tex> на этом ребре должна содержать на границе <tex>p_i</tex> и <tex>p_j</tex> (так как <tex>q</tex> равноудалена от <tex>p_i</tex> и <tex>p_j</tex>). Также эта окружность не должна содержать никаких других сайтов на границе, так как тогда она является вершиной.<br />
}}<br />
<br />
{{Теорема<br />
|statement=Если соединить все сайты, соответствующие смежным ячейкам диаграммы Вороного, получится [[триангуляция Делоне]] для этого множества точек.<br />
|proof=Если ячейки, соответствующие сайтам <tex>p_i, \ p_j</tex>, смежны, то серединный перпендикуляр к отрезку <tex>p_i p_j</tex> образует ребро диаграммы Вороного, то есть к нему применима предыдущая лемма и можно построить окружность с <tex>p_i</tex> и <tex>p_j</tex> на границе, внутри которой не будет других сайтов. Триангуляции Делоне принадлежат [[Триангуляция Делоне#Критерий Делоне для рёбер|те и только те]] рёбра (с поправкой на точки, лежащие на одной окружности), на которых можно построить такую окружность, что внутри неё не будет лежать никаких точек. Тогда ребро <tex>p_i p_j</tex> является ребром триангуляции Делоне. За счёт равносильности в обеих используемых леммах мы добавим все рёбра и не построим лишних.<br />
}}<br />
<br />
== Построение ==<br />
=== Наивный алгоритм ===<br />
Будем [[Пересечение полуплоскостей, связь с выпуклыми оболочками|пересекать полуплоскости]] по [[#intersect|свойству ячейки диаграммы]]. Необходимо для каждого сайта пересечь <tex>n - 1</tex> плоскость, что суммарно делается за <tex>O(n^2 \log n)</tex>.<br />
<br />
=== Инкрементальный алгоритм ===<br />
Храним диаграмму в [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]]. Пусть у нас уже есть диаграмма для точек <tex>p_1, p_2, ..., p_i</tex>. Добавим новый сайт <tex>p_{i+1}</tex>. Сначала найдём сайт <tex>p_j</tex>, в ячейку которого попадает <tex>p_{i+1}</tex>, перебором. После этого строим новую ячейку: сначала проведём серединный перпендикуляр для <tex>p_{i+1}p_j</tex>, он пересечёт границу ячейки <tex>\mathcal{V}(p_j)</tex> с ячейкой <tex>\mathcal{V}(p_k)</tex>; на следующем шаге будем строить серединный перпендикуляр для <tex>p_{i+1} p_k</tex> и так далее.<br />
<br />
В процессе построения перпендикуляров необходимо обновлять РСДС. Каждый раз, когда новое полуребро <tex>e</tex>, порождаемое <tex>p_{i+1}</tex> и <tex>p_j</tex>, пересекает существовавшее ранее полуребро <tex>e'</tex>, создаётся новая вершина <tex>v</tex> и начинается новое полуребро <tex>e+1</tex>.<br />
<br />
Обновление РСДС происходит следующим образом:<br />
<br />
* создаём вершину <tex>v</tex> с полуребром <tex>e</tex>;<br />
* для полуребра <tex>e</tex> в РСДС второй конец в вершине <tex>v</tex>, следующее полуребро — <tex>e'</tex>, инцидентные грани — слева <tex>\mathcal{V}(i+1)</tex>, справа — <tex>\mathcal{V}(j)</tex>;<br />
* добавляем в РСДС полуребро <tex>e + 1</tex> с началом в <tex>v</tex> и предыдущим полуребром <tex>e</tex>;<br />
* удаляем все полурёбра, лежащие между вершиной начала <tex>e</tex> и вершиной конца <tex>e</tex>, по часовой стрелке;<br />
* обновляем полуребро, соответствующее грани для <tex>\mathcal{V}(p_j)</tex> — им становится <tex>e</tex>.<br />
<br />
Каждый шаг выполняется за <tex>O(i)</tex>, значит, суммарно диаграмма из <tex>n</tex> сайтов с нуля создаётся за <tex>O(n^2)</tex>.<br />
<br />
{|<br />
|[[Файл:voronoi-incremental-zero-step.png|200px|thumb|Локализация]]<br />
|[[Файл:voronoi-incremental-first-step.png|200px|thumb|Добавление первого ребра]]<br />
|[[Файл:voronoi-incremental.png|200px|thumb|Добавление третьего ребра]]<br />
|[[Файл:voronoi-update-dcel.png|400px|thumb|Обновление структуры при добавлении ребра]]<br />
|}<br />
<br />
=== Алгоритм Форчуна ===<br />
Построение производится при помощи заметающей прямой и парабол позади неё (параболы в данном случае - это множества точек, равноудалённых от вершины и прямой). Сама диаграмма "рисуется" местами соприкасания соседних парабол. Несмотря на то, что в теории движение прямой происходит непрерывно, сам алгоритм обрабатывает только крайние случаи, когда происходят события. Рассматривается 2 типа событий - появление новой параболы, когда заметающая прямая касается вершины, и схлопывание параболы - когда две соседние параболы её полностью накрывают. Всего событий <tex>O(n)</tex> (<tex>n</tex> - число вершин). Для каждого события вычисляется его время (позиция заметающей прямой), события кладутся в очередь с приоритетом (отсюда <tex>O(\log n)</tex> по времени) и обрабатываются, пока очередь непуста. При обработке событий также записываются пары взаимодействующих вершин (у которых сайты имеют общую границу), это и является результатом работы алгоритма.<br />
<br />
Сложность работы алгоритма - <tex>O(n \log n)</tex> по времени и <tex>O(n)</tex> по памяти.<br />
<br />
Более подробно:<br />
* [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BE%D1%80%D1%87%D1%83%D0%BD%D0%B0 Описание алгоритма на Wikipedia]<br />
* [https://www2.cs.sfu.ca/~binay/813.2011/Fortune.pdf Презентация с описанием в деталях]<br />
<br />
=== Алгоритм Чана ===<br />
Вершины проецируются из двумерной плоскости на поверхность параболоида (<tex>x, y</tex> остаются те же, добавляется <tex>z = x^2 + y^2</tex>). Далее по ним строится [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|выпуклая нижняя оболочка]], на выходе получаются рёбра между вершинами, которые соответствуют триангуляции Делоне.<br />
<br />
== Диаграмма k-го порядка ==<br />
{{Определение<br />
|definition='''Ячейка Вороного''' <tex>k</tex>'''-го порядка''' (<tex>\mathcal{V}_k(p_1, p_2, ..., p_k)</tex>) — множество точек, имеющих в качестве ближайших <tex>k</tex> соседей множество сайтов <tex>p_1, p_2, ..., p_k</tex>.<br />
}}<br />
<br />
Чтобы построить диаграмму <tex>k</tex>-го порядка, возьмём диаграмму <tex>k - 1</tex>-го порядка. Каждая ячейка построена для некоторого набора <tex>k-1</tex> сайтов. Обозначим множество этих сайтов за <tex>S</tex>. [[Пересечение выпуклых многоугольников|Пересечём]] каждую из этих ячеек с ячейками диаграммы первого порядка, построенной на множестве сайтов <tex>P \setminus S</tex>. Когда мы пересекаем ячейку <tex>k-1</tex>-го порядка для точек <tex>S</tex> с ячейкой первого порядка для точки <tex>p_i</tex>, получаем ячейку для множества <tex>S \cup \{p_i\}</tex>. После пересечения ячеек необходимо объединить те, которые отвечают за одинаковый набор сайтов (это могут быть только соседние по ребру ячейки).<br />
<br />
Итого совершаем <tex>k</tex> шагов, на каждом строим <tex>O(n)</tex> диграмм Вороного за время <tex>O(n^3)</tex>, пересекаем <tex>O(n)</tex> ячеек с <tex>O(n)</tex> ячейками за <tex>O(n)</tex> времени, а потом объединяем ячейки за <tex>O(n)</tex> (линейное количество соседних рёбер ячейки, а объединение происходит за <tex>O(1)</tex> за счёт структуры РСДС). Итого <tex>O(k \cdot n^3)</tex>.<br />
<br />
{|<br />
|[[Файл:voronoi-first-order.png|200px|thumb|Диаграмма первого порядка]]<br />
|[[Файл:voronoi-second-order.png|200px|thumb|Диаграмма второго порядка]]<br />
|[[Файл:voronoi-third-order.png|200px|thumb|Диаграмма третьего порядка]]<br />
|[[Файл:voronoi-tenth-order.png|200px|thumb|Диаграмма <tex>n - 1</tex>-го порядка (она же farthest-point диаграмма) для данного набора сайтов]]<br />
|}<br />
<br />
== Farthest-point диаграмма ==<br />
{{Определение<br />
|definition=Диаграмма <tex>n - 1</tex>-го порядка является '''farthest-point диаграммой''', т.е. в каждой её ячейке все точки являются наиболее удалёнными от какого-то сайта.<br />
}}<br />
<br />
=== Свойства ===<br />
{{Лемма<br />
|statement=Для любой точки <tex>q</tex> плоскости самый удалённый от неё сайт из <tex>P</tex> должен лежать на [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|выпуклой оболочке]] <tex>P</tex>.<br />
|proof=[[Файл:voronoi-farthest-inside.png|200px|right]]Сайт, не находящийся на выпуклой оболочке, лежит внутри неё по свойствам выпуклой оболочки.<br />
<br />
Пусть самый удалённый от точки <tex>q</tex> сайт <tex>p_i</tex> не лежит на выпуклой оболочке (т.е. лежит внутри неё). Проведём луч <tex>q p_i</tex>. Он пересечёт ребро выпуклой оболочки <tex>p_j p_k</tex>. Получатся два смежных угла, рассмотрим тот, который оказался прямым или тупым. Тогда в полученном треугольнике <tex>\rho(q, p_j) > \rho(q, p_i)</tex>, так как напротив большего угла лежит большая сторона. Пришли к противоречию.<br />
}}<br />
<br />
{{Лемма<br />
|statement=Сайт, который лежит внутри выпуклой оболочки сайтов, не может иметь ячейку в farthest-point диаграмме.<br />
|proof=Пусть это не так и сайт <tex>p</tex> лежит внутри выпуклой оболочки и имеет ячейку в farthest-point диаграмме. Тогда внутри неё есть точка <tex>q</tex>. Но по предыдущей лемме самый удалённый для <tex>q</tex> сайт лежит на выпуклой оболочке, а значит, сайт <tex>p</tex> не может быть самым удалённым для <tex>q</tex>. Пришли к противоречию.<br />
}}<br />
<br />
{{Лемма<br />
|statement=Каждый сайт, который является вершиной выпуклой оболочки сайтов, имеет ячейку в farthest-point диаграмме.<br />
|proof=Докажем по индукции.<br />
<br />
База индукции: для двух сайтов они оба являются вершинами выпуклой оболочки и оба имеют ячейку в farthest-point диаграмме (дальняя от сайта полуплоскость).<br />
<br />
Переход: добавим сайт <tex>p</tex> так, что он станет новой вершиной выпуклой оболочки. Пусть он не имеет ячейку в farthest-point диаграмме, то есть уже имеющаяся перед его добавлением диаграмма не меняется. Для построения farthest-point диаграммы проводятся серединные перпендикуляры между всеми парами сайтов, и полученные полуплоскости пересекаются; раз новой ячейки не добавилось, то серединные перпендикуляры между <tex>p</tex> и остальными сайтами совпали с уже имеющимися перпендикулярами. Это возможно, только если <tex>p</tex> совпал с другим сайтом. Пришли к противоречию.<br />
}}<br />
<br />
{{Утверждение<br />
|statement=Сайт имеет ячейку в farthest-point диаграмме тогда и только тогда, когда он является вершиной выпуклой оболочки всех сайтов.<br />
|proof=Непосредственно следует из двух предыдущих лемм.<br />
}}<br />
<br />
{{Утверждение<br />
|statement=Все ячейки в farthest-point диаграмме неограничены.<br />
|proof=[[Файл:voronoi-farthest-unbounded.png|200px|right]]Пусть <tex>p_i</tex> — сайт на выпуклой оболочке сайтов, а <tex>q</tex> — точка, для которой он является наиболее удалённым. Тогда для всех точек на луче, лежащем на <tex>p_i q</tex>, начинающемся в <tex>q</tex> и не проходящим через <tex>p_i</tex>, сайт <tex>p_i</tex> будет наиболее удалённым среди остальных сайтов. Значит, ячейка сайта <tex>p_i</tex> в farthest-point диаграмме включает в себя этот луч, а значит, неограничена.<br />
}}<br />
<br />
=== Алгоритм ===<br />
Чтобы найти farthest-point диаграмму, сначала найдём выпуклую оболочку всех сайтов. Обозначим сайты, её образующие, через <tex>p_1, p_2, ..., p_m</tex>. Запомним порядки обхода для каждой вершины выпуклой оболочки по часовой стрелке (<tex>cw(p_i)</tex>) и против часовой (<tex>ccw(p_i)</tex>) и сделаем случайную перестановку точек. Далее удаляем из выпуклой оболочки все точки, кроме первых трёх (запоминая при этом их соседей в оболочке на момент удаления). После этого строим farthest-point диаграмму для первых трёх точек (пересекая полуплоскости) и последовательно добавляем остальные (удалённые) в порядке, обратном порядку удаления.<br />
<br />
{|<br />
|[[Файл:voronoi-farthest-construct.png|600px|thumb|Построение очередной ячейки farthest-point диаграммы]]<br />
|}<br />
<br />
Для точки <tex>p_i</tex> ячейка встанет «между» ячейками, соответствующими <tex>cw(p_i)</tex> и <tex>ccw(p_i)</tex>. Перед добавлением <tex>p_i</tex> <tex>cw(p_i)</tex> и <tex>ccw(p_i)</tex> — соседи, поэтому между ними построен серединный перпендикуляр. Серединный перпендикуляр к <tex>p_i ccw(p_i)</tex> даст новое ребро, которое лежит в farthest-point ячейке <tex>ccw(p_i)</tex> и является частью границы ячейки <tex> p_i</tex>. Обойдём ячейку <tex>ccw(p_i)</tex> по часовой стрелке, чтоб понять, какое ребро пересечёт перпендикуляр. С другой стороны этого ребра лежит ячейка какой-то точки <tex>p_j</tex>, и серединный перпендикуляр <tex>p_i p_j</tex> тоже даст ребро ячейке <tex>p_i</tex>. Аналогично совершим обход и так далее. Последний серединный перпендикуляр будет построен для <tex>p_i cw(p_i)</tex>. После этого удаляем рёбра, которые лежат внутри новой ячейки.<br />
<br />
== См. также ==<br />
* [[Трапецоидная карта]]<br />
* [[Триангуляция Делоне]]<br />
* [[Straight skeleton]]<br />
<br />
== Источники ==<br />
* de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 147-151, 164-166<br />
* [http://students.info.uaic.ro/~emilian.necula/vor2.pdf Algorithms for constructing Voronoi diagrams, Vera Sacrist´an {{---}} Incremental algorithm]<br />
* [http://en.wikipedia.org/wiki/Voronoi_diagram Wikipedia — Voronoi diagram]<br />
* [https://web.archive.org/web/20170329014016/http://www.cs.uu.nl/docs/vakken/ga/slides7b.pdf Computational Geometry {{---}} Lecture 13: More on Voronoi diagrams]<br />
<br />
[[Категория: Вычислительная геометрия]]<br />
[[Категория: Триангуляция Делоне и диаграмма Вороного]]</div>93.175.2.117http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE-%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA&diff=72157Алгоритм Ахо-Корасик2020-01-19T16:42:24Z<p>93.175.2.117: /* Пример автомата Ахо-Корасик */ Replace back to tex, to the same style as in the beginning of the article</p>
<hr />
<div>{{Задача<br />
|definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст.<br />
}}<br />
<br />
==Алгоритм==<br />
=== Шаг 1. Построение бора ===<br />
Строим [[Бор|бор]] из строк.<br /><br />
Построение выполняется за время <tex>O(m)</tex>, где <tex>m</tex> {{---}} суммарная длина строк.<br />
<br />
====Пример построенного бора====<br />
Бор для набора строк <tex> \{ \textbf{he},\ \textbf{she},\ \textbf{his},\ \textbf{hers}\} </tex>:<br /><br />
[[Файл:Бор.jpg]]<br />
<br />
=== Шаг 2. Преобразование бора ===<br />
Обозначим за <tex>[u]</tex> слово, приводящее в вершину <tex>u</tex> в боре.<br /><br />
Узлы бора можно понимать как состояния [[Детерминированные_конечные_автоматы | автомата]], а корень как начальное состояние.<br /><br />
Узлы бора, в которых заканчиваются строки, становятся терминальными.<br /><br />
Для переходов по автомату заведём в узлах несколько функций:<br /><br />
*<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br /><br />
*<tex>\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)</tex> {{---}} '''суффиксная ссылка''', и существует переход из <tex>\mathrm{parent}(u)</tex> в <tex>u</tex> по символу <tex>c</tex>;<br /><br />
*<tex>\delta(u, c) = <br />
\begin{cases}<br />
v, &\text{if $v$ is son by symbol $c$ in trie;}\\<br />
root, &\text{if $u$ is root and $u$ has no child by symbol $c$ in trie}\\<br />
\delta(\pi(u), c), &\text{else.}<br />
\end{cases}</tex> {{---}} функция перехода.<br />
Мы можем понимать рёбра бора как переходы в автомате по соответствующей букве. Однако одними только рёбрами бора нельзя ограничиваться. Если мы пытаемся выполнить переход по какой-либо букве, а соответствующего ребра в боре нет, то мы тем не менее должны перейти в какое-то состояние. Для этого нам и нужны суффиксные ссылки.<br />
<br> Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>.<br />
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].<br />
<br />
Из определений выше можно заметить два следующих факта:<br />
* функция перехода определена через суффиксную ссылку, а суффиксная ссылка {{---}} через функию переходов;<br />
* для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.<br />
Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии.<br />
<br />
==== Пример автомата Ахо-Корасик ====<br />
[[Файл:axo.jpg]]<br /><br />
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.<br />
<br />
Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины <tex>5</tex> с соответствующей ей строкой <tex>\textbf{she}</tex> максимальным подходящим суффиксом является строка <tex>\textbf{he}</tex>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</tex>.<br />
<br />
===Шаг 3. Построение сжатых суффиксных ссылок ===<br />
При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.<br />
<br />
<tex>up(u) = <br />
\begin{cases}<br />
\pi(u), &\text{if $\pi(u)$ is terminal;}\\<br />
\varnothing,&\text{if $\pi(u)$ is root;}\\<br />
up(\pi(u)), &\text{else.}<br />
\end{cases}</tex> <br />
<br />
где <tex>up</tex> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии.<br />
<br />
== Использование автомата ==<br />
Теперь нужно сказать немного слов о том, как мы будем использовать наш автомат. По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам строки, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему строки тоже отмечаем.<br /><br />
<br />
== Пример реализации ==<br />
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br /><br />
<tex>k</tex> {{---}} размер алфавита.<br />
<br />
'''Структура вершины:'''<br />
'''struct''' Node:<br />
'''Node''' son[k] <font color=green>// массив сыновей</font><br />
'''Node''' go[k] <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии), используемый для вычисления суффиксных ссылок</font><br />
'''Node''' parent <font color=green>// вершина родитель</font><br />
'''Node''' suffLink <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font><br />
'''Node''' up <font color=green>// сжатая суффиксная ссылка</font><br />
'''char''' charToParent <font color=green>// символ, ведущий к родителю</font><br />
'''bool''' isLeaf <font color=green>// флаг, является ли вершина терминалом</font><br />
'''vector<int>''' leafPatternNumber <font color=green>// номера строк, за которые отвечает терминал</font><br />
<br />
'''Функция для вычисления суффиксной ссылки:'''<br />
'''Node''' getSuffLink('''Node''' v):<br />
'''if''' v.suffLink == ''null'' <font color=green>// если суффиксная ссылка ещё не вычислена</font><br />
'''if''' v == root '''or''' v.parent == root<br />
v.suffLink = root<br />
'''else'''<br />
v.suffLink = getLink(getSuffLink(v.parent), v.charToParent)<br />
'''return''' v.suffLink<br />
<br />
'''Функция для вычисления перехода:'''<br />
'''Node''' getLink('''Node''' v, '''char''' c): <br />
'''if''' v.go[c] == ''null'' <font color=green>// если переход по символу c ещё не вычислен</font><br />
'''if''' v.son[c]<br />
v.go[c] = v.son[c]<br />
'''else''' '''if''' v == root <br />
v.go[c] = root <br />
'''else''' <br />
v.go[c] = getLink(getSuffLink(v), c)<br />
'''return''' v.go[c]<br />
<br />
'''Функция для вычисления сжатой суффиксной ссылки:'''<br />
'''Node''' getUp('''Node''' v):<br />
'''if''' v.up == ''null'' <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font><br />
'''if''' getSuffLink(v).isLeaf<br />
v.up = getSuffLink(v)<br />
'''else''' '''if''' getSuffLink(v) == root<br />
v.up = root<br />
'''else''' <br />
v.up = getUp(getSuffLink(v))<br />
'''return''' v.up<br />
<br />
'''Функция для добавления строки в бор:'''<br />
'''fun''' addString('''string''' s, '''int''' patternNumber):<br />
'''Node''' cur = root<br />
'''for''' i = 0 '''to''' s.length - 1<br />
'''char''' c = s[i]<br />
'''if''' cur.son[c] == 0<br />
cur.son[c] = Node<br />
<font color=green>/* здесь также нужно обнулить указатели на переходы и сыновей */</font><br />
cur.son[c].suffLink = 0<br />
cur.son[c].up = 0<br />
cur.son[c].parent = cur<br />
cur.son[c].charToParent = c<br />
cur.son[c].isLeaf = ''false''<br />
cur = cur.son[c]<br />
cur.isLeaf = ''true''<br />
cur.leafPatternNumber.pushBack(patternNumber)<br />
'''Функция для процессинга текста (поиск, встречается строка или нет):'''<br />
'''fun''' processText('''string''' t): <br />
'''Node''' cur = root<br />
'''for''' i = 0 '''to''' t.length - 1 <br />
'''char''' c = t[i] - 'a'<br />
cur = getLink(cur, c)<br />
<font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины,<br />
обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки<br />
и так до корня. */</font><br />
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.<br />
<br />
== Оптимизации ==<br />
Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:<br />
<br />
# '''Сброс сжатых суффиксных ссылок для посещённых вершин.''' <br />
#: Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.<br />
# '''Сброс пометки терминальной вершины.''' <br />
#: В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.<br />
<br />
== Поиск шаблонов с масками ==<br />
<br />
{{Задача<br />
|definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR><br />
}}<br />
Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>7</tex> строки <tex>xabvccababcax</tex>. <br />
<br />
=== Алгоритм поиска ===<br />
<br />
Для того чтобы найти все вхождения в текст заданного шаблона с масками <tex>Q</tex>, необходимо обнаружить вхождения в текст всех его безмасочных кусков.<BR><br />
Пусть <tex>\{Q_1, \dots, Q_k \}</tex> {{---}} набор подстрок<br />
<tex>Q</tex>, разделенных масками, и пусть <tex>\{ l_1, \dots, l_k \}</tex> {{---}} их стартовые позиции в <tex>Q</tex>. Например, шаблон <tex>ab\varphi\varphi c\varphi</tex> содержит две подстроки без масок <tex>ab</tex> и <tex>c</tex> и их стартовые позиции соответственно <tex>1</tex> и <tex>5</tex>. Для алгоритма понадобится массив <tex>C</tex>. <tex>C[i]</tex> {{---}} количество встретившихся в тексте безмасочных подстрок шаблона, который начинается в тексте на позиции <tex>i</tex>. Тогда появление подстроки <tex>Q_i</tex> в тексте на позиции <tex>j</tex> будет означать возможное появление шаблона на позиции <tex>j - l_i + 1</tex>.<BR><br />
# Используя алгоритм Ахо-Корасик, находим безмасочные подстроки шаблона <tex>Q</tex>: когда находим <tex>Q_i</tex> в тексте <tex>T</tex> на позиции <tex>j</tex>, увеличиваем на единицу <tex>C[j - l_i + 1]</tex>.<BR><br />
# Каждое <tex>i</tex>, для которого <tex>C[i] = k</tex>, является стартовой позицией появления шаблона <tex>Q</tex> в тексте.<BR><br />
Рассмотрим подстроку текста <tex>T[i \dots i+n-1]</tex>. Равенство <tex>C[i] = k</tex> будет означать, что подстроки текста <tex> T[i + l_1 \dots i + l_1 + |Q_1| - 1], T[i + l_2 \dots i + l_2 + |Q_2| - 1]</tex> и так далее будут равны соответственно безмасочным подстрокам шаблона <tex>\{Q_1, \dots , Q_k \}</tex>. Остальная часть шаблона является масками, поэтому шаблон входит в текст на позиции <tex>i</tex>.<BR><br />
Поиск подстрок заданного шаблона с помощью алгоритма Ахо-Корасик выполняется за время <tex>O(m+n+a)</tex>, где <tex>n</tex> {{---}} суммарная длина подстрок, то есть длина шаблона, <tex>m</tex> {{---}} длина текста, <tex>a</tex> {{---}} количество появлений подстрок шаблона. Далее просто надо пробежаться по массиву <tex>C</tex> и просмотреть значения ячеек за время <tex>O (m)</tex>.<br />
<br />
==См. также==<br />
* [[Алгоритм Бойера-Мура]]<br />
* [[Алгоритм Кнута-Морриса-Пратта]]<br />
<br />
== Источники информации ==<br />
*[http://e-maxx.ru/algo/aho_corasick MAXimal :: algo :: Алгоритм Ахо-Корасик]<br />
*[http://aho-corasick.narod.ru Сопоставление множеств и алгоритм Ахо-Корасик]<br />
*[http://codeforces.com/blog/entry/14854?locale=ru Codeforces :: Алгоритм Ахо-Корасик]<br />
*[https://habrahabr.ru/post/198682/ Habr :: Алгоритм Ахо-Корасик]<br />
*[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE_%E2%80%94_%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA Wiki :: Алгоритм Ахо-Корасик]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]] <br />
[[Категория: Поиск подстроки в строке]]<br />
[[Категория: Точный поиск]]</div>93.175.2.117http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE-%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA&diff=72155Алгоритм Ахо-Корасик2020-01-19T16:39:35Z<p>93.175.2.117: /* Пример автомата Ахо-Корасик */ Replace tex with <code> because it is more suitable for strings and quotes were separated with extra spaces</p>
<hr />
<div>{{Задача<br />
|definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст.<br />
}}<br />
<br />
==Алгоритм==<br />
=== Шаг 1. Построение бора ===<br />
Строим [[Бор|бор]] из строк.<br /><br />
Построение выполняется за время <tex>O(m)</tex>, где <tex>m</tex> {{---}} суммарная длина строк.<br />
<br />
====Пример построенного бора====<br />
Бор для набора строк <tex> \{ \textbf{he},\ \textbf{she},\ \textbf{his},\ \textbf{hers}\} </tex>:<br /><br />
[[Файл:Бор.jpg]]<br />
<br />
=== Шаг 2. Преобразование бора ===<br />
Обозначим за <tex>[u]</tex> слово, приводящее в вершину <tex>u</tex> в боре.<br /><br />
Узлы бора можно понимать как состояния [[Детерминированные_конечные_автоматы | автомата]], а корень как начальное состояние.<br /><br />
Узлы бора, в которых заканчиваются строки, становятся терминальными.<br /><br />
Для переходов по автомату заведём в узлах несколько функций:<br /><br />
*<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br /><br />
*<tex>\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)</tex> {{---}} '''суффиксная ссылка''', и существует переход из <tex>\mathrm{parent}(u)</tex> в <tex>u</tex> по символу <tex>c</tex>;<br /><br />
*<tex>\delta(u, c) = <br />
\begin{cases}<br />
v, &\text{if $v$ is son by symbol $c$ in trie;}\\<br />
root, &\text{if $u$ is root and $u$ has no child by symbol $c$ in trie}\\<br />
\delta(\pi(u), c), &\text{else.}<br />
\end{cases}</tex> {{---}} функция перехода.<br />
Мы можем понимать рёбра бора как переходы в автомате по соответствующей букве. Однако одними только рёбрами бора нельзя ограничиваться. Если мы пытаемся выполнить переход по какой-либо букве, а соответствующего ребра в боре нет, то мы тем не менее должны перейти в какое-то состояние. Для этого нам и нужны суффиксные ссылки.<br />
<br> Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>.<br />
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].<br />
<br />
Из определений выше можно заметить два следующих факта:<br />
* функция перехода определена через суффиксную ссылку, а суффиксная ссылка {{---}} через функию переходов;<br />
* для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.<br />
Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии.<br />
<br />
==== Пример автомата Ахо-Корасик ====<br />
[[Файл:axo.jpg]]<br /><br />
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.<br />
<br />
Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины <tex>5</tex> с соответствующей ей строкой <code>she</code> максимальным подходящим суффиксом является строка <code>he</code>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</tex> .<br />
<br />
===Шаг 3. Построение сжатых суффиксных ссылок ===<br />
При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.<br />
<br />
<tex>up(u) = <br />
\begin{cases}<br />
\pi(u), &\text{if $\pi(u)$ is terminal;}\\<br />
\varnothing,&\text{if $\pi(u)$ is root;}\\<br />
up(\pi(u)), &\text{else.}<br />
\end{cases}</tex> <br />
<br />
где <tex>up</tex> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии.<br />
<br />
== Использование автомата ==<br />
Теперь нужно сказать немного слов о том, как мы будем использовать наш автомат. По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам строки, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему строки тоже отмечаем.<br /><br />
<br />
== Пример реализации ==<br />
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br /><br />
<tex>k</tex> {{---}} размер алфавита.<br />
<br />
'''Структура вершины:'''<br />
'''struct''' Node:<br />
'''Node''' son[k] <font color=green>// массив сыновей</font><br />
'''Node''' go[k] <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии), используемый для вычисления суффиксных ссылок</font><br />
'''Node''' parent <font color=green>// вершина родитель</font><br />
'''Node''' suffLink <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font><br />
'''Node''' up <font color=green>// сжатая суффиксная ссылка</font><br />
'''char''' charToParent <font color=green>// символ, ведущий к родителю</font><br />
'''bool''' isLeaf <font color=green>// флаг, является ли вершина терминалом</font><br />
'''vector<int>''' leafPatternNumber <font color=green>// номера строк, за которые отвечает терминал</font><br />
<br />
'''Функция для вычисления суффиксной ссылки:'''<br />
'''Node''' getSuffLink('''Node''' v):<br />
'''if''' v.suffLink == ''null'' <font color=green>// если суффиксная ссылка ещё не вычислена</font><br />
'''if''' v == root '''or''' v.parent == root<br />
v.suffLink = root<br />
'''else'''<br />
v.suffLink = getLink(getSuffLink(v.parent), v.charToParent)<br />
'''return''' v.suffLink<br />
<br />
'''Функция для вычисления перехода:'''<br />
'''Node''' getLink('''Node''' v, '''char''' c): <br />
'''if''' v.go[c] == ''null'' <font color=green>// если переход по символу c ещё не вычислен</font><br />
'''if''' v.son[c]<br />
v.go[c] = v.son[c]<br />
'''else''' '''if''' v == root <br />
v.go[c] = root <br />
'''else''' <br />
v.go[c] = getLink(getSuffLink(v), c)<br />
'''return''' v.go[c]<br />
<br />
'''Функция для вычисления сжатой суффиксной ссылки:'''<br />
'''Node''' getUp('''Node''' v):<br />
'''if''' v.up == ''null'' <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font><br />
'''if''' getSuffLink(v).isLeaf<br />
v.up = getSuffLink(v)<br />
'''else''' '''if''' getSuffLink(v) == root<br />
v.up = root<br />
'''else''' <br />
v.up = getUp(getSuffLink(v))<br />
'''return''' v.up<br />
<br />
'''Функция для добавления строки в бор:'''<br />
'''fun''' addString('''string''' s, '''int''' patternNumber):<br />
'''Node''' cur = root<br />
'''for''' i = 0 '''to''' s.length - 1<br />
'''char''' c = s[i]<br />
'''if''' cur.son[c] == 0<br />
cur.son[c] = Node<br />
<font color=green>/* здесь также нужно обнулить указатели на переходы и сыновей */</font><br />
cur.son[c].suffLink = 0<br />
cur.son[c].up = 0<br />
cur.son[c].parent = cur<br />
cur.son[c].charToParent = c<br />
cur.son[c].isLeaf = ''false''<br />
cur = cur.son[c]<br />
cur.isLeaf = ''true''<br />
cur.leafPatternNumber.pushBack(patternNumber)<br />
'''Функция для процессинга текста (поиск, встречается строка или нет):'''<br />
'''fun''' processText('''string''' t): <br />
'''Node''' cur = root<br />
'''for''' i = 0 '''to''' t.length - 1 <br />
'''char''' c = t[i] - 'a'<br />
cur = getLink(cur, c)<br />
<font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины,<br />
обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки<br />
и так до корня. */</font><br />
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.<br />
<br />
== Оптимизации ==<br />
Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:<br />
<br />
# '''Сброс сжатых суффиксных ссылок для посещённых вершин.''' <br />
#: Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.<br />
# '''Сброс пометки терминальной вершины.''' <br />
#: В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.<br />
<br />
== Поиск шаблонов с масками ==<br />
<br />
{{Задача<br />
|definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR><br />
}}<br />
Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>7</tex> строки <tex>xabvccababcax</tex>. <br />
<br />
=== Алгоритм поиска ===<br />
<br />
Для того чтобы найти все вхождения в текст заданного шаблона с масками <tex>Q</tex>, необходимо обнаружить вхождения в текст всех его безмасочных кусков.<BR><br />
Пусть <tex>\{Q_1, \dots, Q_k \}</tex> {{---}} набор подстрок<br />
<tex>Q</tex>, разделенных масками, и пусть <tex>\{ l_1, \dots, l_k \}</tex> {{---}} их стартовые позиции в <tex>Q</tex>. Например, шаблон <tex>ab\varphi\varphi c\varphi</tex> содержит две подстроки без масок <tex>ab</tex> и <tex>c</tex> и их стартовые позиции соответственно <tex>1</tex> и <tex>5</tex>. Для алгоритма понадобится массив <tex>C</tex>. <tex>C[i]</tex> {{---}} количество встретившихся в тексте безмасочных подстрок шаблона, который начинается в тексте на позиции <tex>i</tex>. Тогда появление подстроки <tex>Q_i</tex> в тексте на позиции <tex>j</tex> будет означать возможное появление шаблона на позиции <tex>j - l_i + 1</tex>.<BR><br />
# Используя алгоритм Ахо-Корасик, находим безмасочные подстроки шаблона <tex>Q</tex>: когда находим <tex>Q_i</tex> в тексте <tex>T</tex> на позиции <tex>j</tex>, увеличиваем на единицу <tex>C[j - l_i + 1]</tex>.<BR><br />
# Каждое <tex>i</tex>, для которого <tex>C[i] = k</tex>, является стартовой позицией появления шаблона <tex>Q</tex> в тексте.<BR><br />
Рассмотрим подстроку текста <tex>T[i \dots i+n-1]</tex>. Равенство <tex>C[i] = k</tex> будет означать, что подстроки текста <tex> T[i + l_1 \dots i + l_1 + |Q_1| - 1], T[i + l_2 \dots i + l_2 + |Q_2| - 1]</tex> и так далее будут равны соответственно безмасочным подстрокам шаблона <tex>\{Q_1, \dots , Q_k \}</tex>. Остальная часть шаблона является масками, поэтому шаблон входит в текст на позиции <tex>i</tex>.<BR><br />
Поиск подстрок заданного шаблона с помощью алгоритма Ахо-Корасик выполняется за время <tex>O(m+n+a)</tex>, где <tex>n</tex> {{---}} суммарная длина подстрок, то есть длина шаблона, <tex>m</tex> {{---}} длина текста, <tex>a</tex> {{---}} количество появлений подстрок шаблона. Далее просто надо пробежаться по массиву <tex>C</tex> и просмотреть значения ячеек за время <tex>O (m)</tex>.<br />
<br />
==См. также==<br />
* [[Алгоритм Бойера-Мура]]<br />
* [[Алгоритм Кнута-Морриса-Пратта]]<br />
<br />
== Источники информации ==<br />
*[http://e-maxx.ru/algo/aho_corasick MAXimal :: algo :: Алгоритм Ахо-Корасик]<br />
*[http://aho-corasick.narod.ru Сопоставление множеств и алгоритм Ахо-Корасик]<br />
*[http://codeforces.com/blog/entry/14854?locale=ru Codeforces :: Алгоритм Ахо-Корасик]<br />
*[https://habrahabr.ru/post/198682/ Habr :: Алгоритм Ахо-Корасик]<br />
*[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE_%E2%80%94_%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA Wiki :: Алгоритм Ахо-Корасик]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]] <br />
[[Категория: Поиск подстроки в строке]]<br />
[[Категория: Точный поиск]]</div>93.175.2.117http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%B4%D1%8A%D1%91%D0%BC%D0%B0&diff=72105Метод двоичного подъёма2020-01-17T13:53:24Z<p>93.175.2.117: /* Псевдокод */ Remove ambiguous tex in pseudocode</p>
<hr />
<div>'''Метод двоичного подъёма''' {{---}} один из самых простых методов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]] в online. Он не использует метод решения задачи '''RMQ''' и основан на методе [[Динамическое программирование | динамического программирования]].<br />
==Описание алгоритма==<br />
Как и большинство '''on-line''' алгоритмов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]], этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.<br />
===Препроцессинг===<br />
Препроцессинг заключается в том, чтобы посчитать функцию: <tex> dp[v][i] </tex> {{---}} номер вершины, в которую мы придём если пройдём из вершины <tex> v </tex> вверх по подвешенному дереву <tex> 2 ^ i </tex> шагов, причём если мы пришли в корень, то мы там и останемся.<br />
Для этого сначала обойдем дерево в глубину, и для каждой вершины запишем номер её родителя <tex> p[v] </tex> и глубину вершины в подвешенном дереве <tex> d[v] </tex>. Если <tex> v </tex> {{---}} корень, то <tex> p[v] = v </tex>. Тогда для функции <tex> dp </tex> есть рекуррентная формула:<br />
<br />
<tex>dp[v][i]= \begin{cases}<br />
p[v] & i = 0,\\<br />
dp[dp[v][i - 1]][i - 1] & i \: > \: 0.<br />
\end{cases}</tex><br />
<br />
Для того чтобы отвечать на запросы нам нужны будут только те значения <tex> dp[v][i] </tex>, где <tex> i \leqslant \log_2{n} </tex>, ведь при больших <tex> i </tex> значение <tex> dp[v][i] </tex> будет номером корня. <br />
<br />
Всего состояний динамики <tex> O(n \log{n})</tex>, где <tex> n </tex> {{---}} это количество вершин в дереве. Каждое состояние считается за <tex> O(1) </tex>. Поэтому суммарная сложность времени и памяти препроцессинга {{---}} <tex> O(n \log{n}) </tex>.<br />
<br />
===Ответы на запросы===<br />
Ответы на запросы будут происходить за время <tex> O(\log{n})</tex>.<br />
Для ответа на запрос заметим сначала, что если <tex> c = LCA(v, u) </tex>, для некоторых <tex> v </tex> и <tex> u </tex>, то <tex> d[c] \leqslant \min(d[v], d[u])</tex>. Поэтому если <tex> d[v] < d[u] </tex>, то пройдём от вершины <tex> u </tex> на <tex> (d[u] - d[v]) </tex> шагов вверх, это и будет новое значение <tex> u </tex> и это можно сделать за <tex> O(\log{n}) </tex>. Можно записать число <tex> (d[u] - d[v]) </tex> в двоичной системе, это представление этого число в виде суммы степеней двоек, <tex> 2 ^ {i_1} + 2 ^ {i_2} + \ldots + 2 ^ {i_l} </tex> и для всех <tex> i_j</tex> пройти вверх последовательно из вершины <tex> u </tex> в <tex> dp[u][i_j] </tex>.<br />
<br />
Дальше считаем, что <tex> d[v] = d[u] </tex>. <br />
<br />
Если <tex> v = u </tex>, то ответ на запрос <tex> v </tex>. <br />
<br />
А если <tex> v \neq u </tex>, то найдём такие вершины <tex> x </tex> и <tex> y </tex>, такие что <tex> x \neq y </tex>, <tex> x </tex> {{---}} предок <tex> v </tex>, <tex> y </tex> {{---}} предок <tex> u </tex> и <tex> p[x] = p[y] </tex>. Тогда ответом на запрос будет <tex> p[x] </tex>. <br />
<br />
Научимся находить эти вершины <tex> x </tex> и <tex> y </tex>. Для этого сначала инициализируем <tex> x = v </tex> и <tex> y = u </tex>. Дальше на каждом шаге находим такое максимальное <tex> k </tex>, что <tex> dp[x][k] \neq dp[y][k] </tex>. И проходим из вершин <tex> x </tex> и <tex> y </tex> на <tex> 2 ^ k </tex> шагов вверх. Если такого <tex> k </tex> найти нельзя, то значения <tex> x </tex> и <tex> y </tex>, это те самые вершины, которые нам требуется найти, ведь <tex> p[x] = dp[x][0] = dp[y][0] = p[y] </tex>.<br />
<br />
Оценим время работы. Заметим, что найденные <tex> k </tex> строго убывают. Во-первых, потому что мы находим на каждом шаге максимальное значение <tex> k </tex>, а во-вторых, два раза подряд мы одно и то же <tex> k </tex> получить не можем, так как тогда получилось бы, что можно пройти <tex> 2 ^ k + 2 ^ k = 2 ^ {k + 1}</tex> шагов, а значит вместо первого <tex> k </tex>, мы бы нашли <tex> k + 1 </tex>. А, значит, всего <tex> O(\log{n}) </tex> значений <tex> k </tex>, их можно перебирать в порядке убывания. Сложность ответа на запрос <tex> O(\log{n}) </tex>.<br />
<br />
==Псевдокод==<br />
'''function''' preprocess():<br />
'''int[]''' p = dfs(0)<br />
'''for''' i = 1 '''to''' n<br />
dp[i][0] = p[i]<br />
'''for''' j = 1 '''to''' log(n)<br />
'''for''' i = 1 '''to''' n<br />
dp[i][j] = dp[dp[i][j - 1]][j - 1]<br />
<br />
'''int''' lca('''int''' v, '''int''' u):<br />
'''if''' d[v] > d[u]<br />
swap(v, u)<br />
'''for''' i = log(n) '''downto''' 0<br />
'''if''' d[dp[u][i]] - d[v] >= 0<br />
u = dp[u][i]<br />
'''if''' v == u<br />
'''return''' v<br />
'''for''' i = log(n) '''downto''' 0<br />
'''if''' dp[v][i] != dp[u][i]<br />
v = dp[v][i]<br />
u = dp[u][i]<br />
'''return''' p[v]<br />
<br />
==См. также==<br />
* [[Сведение задачи LCA к задаче RMQ]]<br />
<br />
==Источники информации==<br />
* [http://en.wikipedia.org/wiki/Lowest_common_ancestor Wikipedia: LCA]<br />
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor TopCoder tutorial: RMQ and LCA]<br />
* [http://e-maxx.ru/algo/lca_simpler MAXimal :: algo :: Метод двоичного подъёма ]<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Задача о наименьшем общем предке]]</div>93.175.2.117http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%B4%D1%8A%D1%91%D0%BC%D0%B0&diff=72104Метод двоичного подъёма2020-01-17T13:43:51Z<p>93.175.2.117: /* Псевдокод */ Fix code block display</p>
<hr />
<div>'''Метод двоичного подъёма''' {{---}} один из самых простых методов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]] в online. Он не использует метод решения задачи '''RMQ''' и основан на методе [[Динамическое программирование | динамического программирования]].<br />
==Описание алгоритма==<br />
Как и большинство '''on-line''' алгоритмов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]], этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.<br />
===Препроцессинг===<br />
Препроцессинг заключается в том, чтобы посчитать функцию: <tex> dp[v][i] </tex> {{---}} номер вершины, в которую мы придём если пройдём из вершины <tex> v </tex> вверх по подвешенному дереву <tex> 2 ^ i </tex> шагов, причём если мы пришли в корень, то мы там и останемся.<br />
Для этого сначала обойдем дерево в глубину, и для каждой вершины запишем номер её родителя <tex> p[v] </tex> и глубину вершины в подвешенном дереве <tex> d[v] </tex>. Если <tex> v </tex> {{---}} корень, то <tex> p[v] = v </tex>. Тогда для функции <tex> dp </tex> есть рекуррентная формула:<br />
<br />
<tex>dp[v][i]= \begin{cases}<br />
p[v] & i = 0,\\<br />
dp[dp[v][i - 1]][i - 1] & i \: > \: 0.<br />
\end{cases}</tex><br />
<br />
Для того чтобы отвечать на запросы нам нужны будут только те значения <tex> dp[v][i] </tex>, где <tex> i \leqslant \log_2{n} </tex>, ведь при больших <tex> i </tex> значение <tex> dp[v][i] </tex> будет номером корня. <br />
<br />
Всего состояний динамики <tex> O(n \log{n})</tex>, где <tex> n </tex> {{---}} это количество вершин в дереве. Каждое состояние считается за <tex> O(1) </tex>. Поэтому суммарная сложность времени и памяти препроцессинга {{---}} <tex> O(n \log{n}) </tex>.<br />
<br />
===Ответы на запросы===<br />
Ответы на запросы будут происходить за время <tex> O(\log{n})</tex>.<br />
Для ответа на запрос заметим сначала, что если <tex> c = LCA(v, u) </tex>, для некоторых <tex> v </tex> и <tex> u </tex>, то <tex> d[c] \leqslant \min(d[v], d[u])</tex>. Поэтому если <tex> d[v] < d[u] </tex>, то пройдём от вершины <tex> u </tex> на <tex> (d[u] - d[v]) </tex> шагов вверх, это и будет новое значение <tex> u </tex> и это можно сделать за <tex> O(\log{n}) </tex>. Можно записать число <tex> (d[u] - d[v]) </tex> в двоичной системе, это представление этого число в виде суммы степеней двоек, <tex> 2 ^ {i_1} + 2 ^ {i_2} + \ldots + 2 ^ {i_l} </tex> и для всех <tex> i_j</tex> пройти вверх последовательно из вершины <tex> u </tex> в <tex> dp[u][i_j] </tex>.<br />
<br />
Дальше считаем, что <tex> d[v] = d[u] </tex>. <br />
<br />
Если <tex> v = u </tex>, то ответ на запрос <tex> v </tex>. <br />
<br />
А если <tex> v \neq u </tex>, то найдём такие вершины <tex> x </tex> и <tex> y </tex>, такие что <tex> x \neq y </tex>, <tex> x </tex> {{---}} предок <tex> v </tex>, <tex> y </tex> {{---}} предок <tex> u </tex> и <tex> p[x] = p[y] </tex>. Тогда ответом на запрос будет <tex> p[x] </tex>. <br />
<br />
Научимся находить эти вершины <tex> x </tex> и <tex> y </tex>. Для этого сначала инициализируем <tex> x = v </tex> и <tex> y = u </tex>. Дальше на каждом шаге находим такое максимальное <tex> k </tex>, что <tex> dp[x][k] \neq dp[y][k] </tex>. И проходим из вершин <tex> x </tex> и <tex> y </tex> на <tex> 2 ^ k </tex> шагов вверх. Если такого <tex> k </tex> найти нельзя, то значения <tex> x </tex> и <tex> y </tex>, это те самые вершины, которые нам требуется найти, ведь <tex> p[x] = dp[x][0] = dp[y][0] = p[y] </tex>.<br />
<br />
Оценим время работы. Заметим, что найденные <tex> k </tex> строго убывают. Во-первых, потому что мы находим на каждом шаге максимальное значение <tex> k </tex>, а во-вторых, два раза подряд мы одно и то же <tex> k </tex> получить не можем, так как тогда получилось бы, что можно пройти <tex> 2 ^ k + 2 ^ k = 2 ^ {k + 1}</tex> шагов, а значит вместо первого <tex> k </tex>, мы бы нашли <tex> k + 1 </tex>. А, значит, всего <tex> O(\log{n}) </tex> значений <tex> k </tex>, их можно перебирать в порядке убывания. Сложность ответа на запрос <tex> O(\log{n}) </tex>.<br />
<br />
==Псевдокод==<br />
'''function''' preprocess():<br />
'''int[]''' p = dfs(0)<br />
'''for''' i = 1 '''to''' n<br />
dp[i][0] = p[i]<br />
'''for''' j = 1 '''to''' log(n)<br />
'''for''' i = 1 '''to''' n<br />
dp[i][j] = dp[dp[i][j - 1]][j - 1]<br />
<br />
'''int''' lca('''int''' v, '''int''' u):<br />
'''if''' d[v] > d[u]<br />
swap(v, u)<br />
'''for''' i = log(n) '''downto''' 0<br />
'''if''' d[dp[u][i]] - d[v] >= 0 <tex>\geqslant 2 ^ i </tex><br />
u = dp[u][i]<br />
'''if''' v == u<br />
'''return''' v<br />
'''for''' i = log(n) '''downto''' 0<br />
'''if''' dp[v][i] != dp[u][i]<br />
v = dp[v][i]<br />
u = dp[u][i]<br />
'''return''' p[v]<br />
<br />
==См. также==<br />
* [[Сведение задачи LCA к задаче RMQ]]<br />
<br />
==Источники информации==<br />
* [http://en.wikipedia.org/wiki/Lowest_common_ancestor Wikipedia: LCA]<br />
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor TopCoder tutorial: RMQ and LCA]<br />
* [http://e-maxx.ru/algo/lca_simpler MAXimal :: algo :: Метод двоичного подъёма ]<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Задача о наименьшем общем предке]]</div>93.175.2.117