Изменения

{{Определение 1) K* применяет A* на графе <tex>G</tex> вместо обратного алгоритма Дейкстры, который используется алгоритмом Эппштейна. 2) Мы запускаем A* на <tex>G</tex> и Дейкстру на <tex>P(G)</tex> в поочередном порядке, который позволяет Дейкстре вычислить требуемые пути до заверешения полного поиска алгоритма A* на графе <tex>G</tex> . == 4.1 Поиск A* на G == K* применяет A* к входному графу <tex>G</tex> для того, чтобы построить дерево поиска <tex>T</tex>. Заметим, что A*, также как и алгоритм Дейкстры, строит дерево поиска в процессе нахождения кратчайшего пути <tex>s-t</tex> . Эти деревья формируются с помощью ссылок на родительские узлы, которые хранятся в том время, как A* производит итерации для того, чтобы восстановить путь <tex>s-t</tex>, когда вершина <tex>t</tex> ещё не найдена. Запасные ребра, открытые в процессе поиска A* на графе G, немедленно добавляются в граф P(G), структура которого будет объясняться в разделе 4.3.  В K* A* применяется к графу <tex>G</tex> в прямом направлении в отличие от алгоритма Эппштейна, из-за чего корнем дерева <tex>T</tex> является вершина начальная <tex>s</tex>. Это необходимо для того, чтобы была возможность работать c неявным описанием графа <tex>G</tex> через функцию successor (функция, возвращающая список исходящих ребер из данной вершины). На протяжение статьи будем считать граф <tex>G</tex> конечным, если не будет сказано иное. Заметим, что А* корректен на конечных графах. Будем следовать литературному соглашению, предполагая, что стоимость бесконечного пути неограниченна. == 4.2 Стоимость объезда ==[[Файл:kstar-figure-3.png|600px|idthumb|center|'''Рисунок 3.''' Исходный граф, в котором сплошные линии представляют построенное A* дерево поиска <tex>T</tex>. Пунктирные линии являются запасными ребрами.]]Для ребра <tex>(u, v)</tex> стоимость '''объезда''' (англ. ''detour'') <tex>\delta(u, v)</tex> представляет стоимость '''ущерба''' (англ. ''disadvantage'') из-за взятия ребра объезда <tex>(u,v)</tex> в сравнении с кратчайшим путем <tex>s-t</tex> через <tex>v</tex>. Ни длина кратчайшего пути <tex>s-t</tex> через <tex>v</tex>, ни длина пути <tex>s-t</tex>, включающего запасные ребра <tex>(u, v)</tex> не известны, когда A* обнаруживает <tex>(u, v)</tex>. Обе длины могут быть оценены с помощью функции оценки <tex>f</tex>, которая использует эвристическую функцию <tex>h</tex>. Пусть <tex>f(v)</tex> будет <tex>f</tex>-значением с соответствии с деревом поиска <tex>T</tex> и <tex>f_u(v)</tex> будет <tex>f</tex>-значением в соответствии с родителем u, т.е. <tex>f_u(v) = g(u) + c(u, v) + h(v)</tex>. Тогда <tex>\delta(u, v)</tex> может быть определена так: <tex>\delta(u, v) = f_u(v) - f(v) = g(u) + c(u, v) + h(v) - g(v) - h(v) =def_monotone_polygong(u) + c(u, v) - g(v)</tex> Заметим, что <tex>\delta(u, v)</tex> дает точную объездную метрику, поскольку оценочное <tex>h</tex>-значение не появляется в определении функции <tex>\delta(u, v)</tex>.|definition== 4.3 Структура графа путей ==Простой многоугольник Структура графа путей <tex>P(G)</tex> довольно сложная. В принципе, <tex>P(G)</tex> будет ориентированным графом, вершины которого соответствуют ребрам в исходном графе <tex>G</tex> называется . Он будет организован как коллекция взаимосвязанных '''монотоннымкуч''' относительно прямой (англ. ''heap''). 2 бинарные кучи минимума присвоены к каждой вершине <tex>v</tex>lв графе <tex>G</tex>, если любая которые называются '''входящей кучей''' (англ. ''incoming heap'')<tex>H_{in}(v)</tex>lи '''деревянной кучей''' (англ. ''tree heap'') <tex>H_{T}(v)</tex>. Эти кучи являются базисом <tex>P(G)</tex>. Как мы покажем далее, использование этих куч также играет главную роль в поддержании асимптотической сложности K*, также как в EA и LVEA. Входящая куча <tex>H_{in}(v)</tex> содержит узлы для каждого запасного ребра к вершине <tex>v</tex>, которые до сих пор были обнаружены A*. Узлы <tex>H_{in}(v)</tex> будут упорядочены в соответствии с <tex>\delta</tex>-значением соответствующих переходов. Узел владеющий ребром с минимальной стоимостью ущерба будет расположен на вершине кучи. Мы ограничим структуру кучи <tex>H_{in}(v)</tex>таким образом, такая что её корень в отличие от остальных узлов, будет иметь не более 1 ребенка. Обозначим его <tex>lroot_{in}(v)</tex>. ' ''Пример 4.''' Рисунок 4 иллюстрирует входящие кучи графа из рисунка 3. Цифры рядом с узлами кучи соответствуют <tex>\perp ldelta</tex>-значениям. [[Файл:kstar-figure-4.png|600px|thumb|center|'''Рисунок 4.''' Входящие кучи <tex>H_{in}(s_i)</tex>, пересекает стороны полученные из графа, показанного на рисунке 3.]] Деревянная куча <tex>H_{T}(v)</tex> для произвольной вершины <tex>v</tex>Pстроится следующим образом. Если <tex>v</tex> - стартовая вершина, т.е. <tex>v = s</tex>, то <tex>H_{T}(v)</tex> будет изначально пустой кучей. Затем в неё будет добавлен <tex>root_{in}(s)</tex>, если <tex>H_{in}(s)</tex> не пустая. Если <tex>v</tex> не стартовая вершина, то пусть вершина <tex>u</tex> будет родителем вершины <tex>v</tex> в дереве поиска <tex>T</tex>. Мы можем представить, что <tex>H_{T}(v)</tex> конструируется как копия <tex>H_{T}(u)</tex>, в которую добавлен <tex>root_{in}(v)</tex>. Если <tex>H_{in}(v)</tex> пустая, то <tex>H_{T}(v)</tex> идентична <tex>H_{T}(u)</tex>. Однако, для экономии памяти мы создаем только дешевую копию <tex>H_{T}(u)</tex>. Это осуществляется через создание копий только тех узлов кучи, которые лежат на обновленном пути в <tex>H_{T}(u)</tex>. Оставшаяся часть <tex>H_{T}(u)</tex> не более двух раз копируется. Другими словами, <tex>root_{in}(v)</tex> вставляется в <tex>H_{T}(u)</tex> неразрушающим путем так, что структура <tex>H_{T}(u)</tex> сохраняется. В куче <tex>H_{T}(v)</tex> к <tex>root_{in}(v)</tex> могут быть присоединены 1 или 2 ребенка. К тому же, <tex>root_{in}(v)</tex> хранит только 1 собственного ребенка из <tex>H_{in}(v)</tex>. Мы обозначим корень <tex>H_{T}(v)</tex> как <tex>R(v)</tex>. [[Файл:kstar-figure-5.png|600px|thumb|center|'''Рисунок 5.''' Деревянные кучи <tex>H_{T}(s_i)</tex>, полученные из графа, показанного на рисунке 3.]] Назовем ребра, которые берут начало из входящих или деревянных куч, '''кучными ребрами''' (англ. ''heap edges''). Сформулируем следующую лемму.{{Лемма|about=1|statement=Все узлы, достижимые из <tex>R(результатом пересечения v)</tex> по кучным ребрам, для каждой вершины <tex>v</tex> формируют тернарную кучу, упорядоченную в соответствии с <tex>\delta</tex>l-значением. Мы назовем такую кучу '''графовой кучей''' (англ. ''graph heap'') вершины <tex>v</tex> и обозначим её как <tex>H_{G}(v)</tex>.|proof=Те узлы, которые находятся в <tex>PH_{T}(v)</tex> может быть только один отрезок или точкаво входящей куче, на которую ссылается узел из <tex>H_{T}(v)</tex>, достижимы по кучным ребрам из <tex>R(v)</tex>. Деревянная куча <tex>H_{T}(v)</tex> формируется через добавление корней входящих куч всех вершин, лежащих на пути из стартовой вершины <tex>s</tex> до <tex>v</tex> в бинарной куче. Каждый из этих корней имеет максимум 3 детей: до 2 в <tex>H_{T}(v)</tex> и дополнительно единственного из входящей кучи. Любой другой узел, живущий во входящей куче имеет не больше 2 детей. Напомним, что каждая входящая куча - это бинарная куча с ограничением, что корень имеет единственного ребенка. Древовидная структура <tex>H_{G}(v)</tex> непосредственный результат древовидных структур <tex>H_{T}(v)</tex> и входящих куч. Более того, кучная характеристика деревянной кучи обеспечивает упорядочивание в соответствии с <tex>\delta</tex>-значением по ребрам из <tex>H_{T}(v)</tex>, а кучная характеристика входящих куч - по всем ребрам из <tex>H_{in}</tex>. Все это приводит к тому, что <tex>H_{G}(v)</tex> - тернарная куча, упорядоченная в соответствии с <tex>\delta</tex>-значением.

Финальная структура <tex>P(G)</tex> получется из входящих и деревянных куч следующим образом. К каждому узлу <tex>n</tex> из <tex>P(G)</tex>, несущему ребро <tex>(u,v)</tex>, мы присоединим указатель, ссылающийся на <tex>R(u)</tex>, который является корневым узлом <tex>H_{T}(u)</tex>. Мы назовем такие указатели '''кросс-ребрами''' (англ. ''cross edges''), в то время как указатели, возникающие из куч названы кучными ребрами, как упоминалось раньше. Более того, мы добавим специальный узел <tex>\mathrm{ОпределениеR}</tex> в <tex>P(G)</tex> с одним выходящим кросс-ребром к <tex>R(t)</tex>.|definition=МногоугольникБолее того, монотонный относительно мы определим весовую функцию <tex>y\Delta</tex>-оси называется на ребрах из <tex>P(G)</tex>. Пусть <tex>(n,n')</tex> обозначает ребро в <tex>P(G)</tex>, и пусть <tex>e</tex> и <tex>e'</tex> обозначают ребра из <tex>G</tex>, соответствующие узлам <tex>n</tex> и <tex>n'</tex>. Тогда определим <tex>y\Delta(n,n')</tex>следующим образом:  <tex> \Delta(n,n')=\begin{cases} \delta(e') -монотонным\delta(e),& \text{if}\ (n,n')\ \text{heap edge} \\ \delta(e'),& \text{if}\ (n,n')\ \text{cross edge}. \end{cases}} </tex>

Суть данного метода заключается в том, чтобы разбить многоугольник на монотонные части, а затем триангулировать каждую из них'''Пример 6.=== Разбиение многоугольника на монотонные части ====[[Файл:Split-merge.png|500px|thumb||Пять типов вершин]]'''

Рассмотрим самую верхнюю — максимальную по координате <tex>y</tex> вершину. Будем идти вниз по рёбрам до самой нижней — соотвественно минимальной по <tex>y</tex> вершине, то есть таким образомВ оставшейся части этого раздела мы проиллюстрируем особенности структуры графа путей, что которые актуальны для некоторой вершины <tex>j</tex>: <tex>y_j > y_{j+1}</tex>. '''Поворотной''' назовём вершину <tex>i</tex>, на которой направление обхода будет меняется: нахождения кратчайших путей <tex>y_{is-1} > y_i</tex> и <tex>y_i < y_{i+1}</tex>. Опишем более подробно этот тип вершин. Уточним понятния ''выше'' и ''ниже'': точка <tex>pt</tex> лежит ''ниже'' точки <tex>q</tex>, если <tex>p_y < q_y</tex> или если <tex>p_y = q_y</tex> и <tex>p_x > q_x</tex>, соответственно точка <tex>p</tex> лежит ''выше'' точки <tex>q</tex>, если <tex>p_y > q_y</tex> или если <tex>p_y = q_y</tex> и <tex>p_x < q_x</tex>. Это было сделано для того, чтобы избежать неопределённых ситуаций с вершинами, у которых <tex>y</tex>-координаты равны.

Обозначим за Первое наблюдение в том, что <tex>\phiP(G)</tex> внутренний угол при некоторой вершине и определим далее пять типов вершин, четыре из которых являются поворотными:* '''''start вершина''''' — два её соседа лежат ниже её самой и ориентированный взвешенный граф. Каждый узел в <tex> \phi < \pi P(G)</tex>* '''''split вершина''''' — два её соседа лежат ниже её самой и несет запасное ребро из G. Использование бинарных куч в конструкции <tex> \phi > \pi P(G)</tex>* '''''end вершина''''' — два её соседа лежат выше её самой и извлекает выгоду из следующих 2 свойств. Во-первых, произвольный узел в <tex> \phi < \pi P(G)</tex>* '''''merge вершина''''' — два её соседа лежат выше её самой и имеет не более 4 выходящих ребер. Одним из ребер будет точно кросс-ребро в то время, как оставшимися будут кучные ребра. Во-вторых, функция веса <tex> \phi > \pi Delta</tex>* '''''regular вершина''''' — не является поворотной, неотрицательна. Как станет ясно в отличие от остальныхразделе 5, другими словами один её сосед находится выше, а другой ниже её самойэти свойства необходимы для доказательства правильности и определения сложности K*.

{{Лемма|statement=Многоугольник <tex>P</tex> является <tex>y</tex>Второе наблюдение заключается в существовании соответствия один-монотонным, если в нём отсутствуют split и merge вершины.|proof=Предположим, что <tex>P</tex> не <tex>y</tex>к-монотонный. Тогда докажем, что <tex>P</tex> содержит split и merge вершины. Поскольку <tex>P</tex> не <tex>yодному между путей </tex>s-монотонный, существует горизонтальная прямая <tex>lt</tex>, которая пересекает его стороны более двух раз. Выберем <tex>l</tex> таким образом, чтобы самой левой компонентой пересечения в <tex>lG</tex> и <tex>P</tex> был бы отрезок <tex>pq</tex>. Далее будем двигаться наверх по сторонам <tex>P</tex>, начиная от точки <tex>q</tex>. В результате путей в некоторой точке <tex>r</tex>, где <tex>r \neq p</tex> Р(случай '''(a)''' на рисункеG), прямая <tex>l</tex> снова пересечёт одну из сторон <tex>P</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам которые начинаются в <tex>P\mathrm{R}</tex>, будет split вершиной.

[[Файл:Proof_lemma.jpg|450px]]..

Если же {{Лемма|about=2|statement=Пусть <tex>r = pn</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам будет узлом графовой кучи <tex>PH_{G}(w)</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка для какой-нибудь вершины <tex>r'w</tex>, которая будет результатом пересечения . Пусть <tex>l(u,v)</tex> и будет ребром связанным с <tex>Pn</tex>. При этом <tex>r' \neq p</tex>, Тогда существует путь в противном случае дереве поиска <tex>lT</tex> будет пересекать из <tex>Pv</tex> только два раза, что противоречит выбору в <tex>lw</tex>. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P|proof=.. Она будет merge вершиной.

=== Алгоритм =4.4 Алгоритмическая структура K* ==Чтобы сделать многоугольник монотоннымАлгоритмический принцип K* следующий. Будем запускать алгоритмы Дейкстры и A* на <tex>G</tex> с чередованием. Сначала, мы выполним A* на <tex>G</tex>, который будет работать до тех, пока вершина <tex>t</tex> не будет выбрана из очереди для раскрытия. Затем, вы запустим алгоритм Дейкстры на доступной части <tex>P(G)</tex>. Каждый узел раскрытый Дейкстрой представляет путь. Если точнее, то путь <tex>\sigma</tex> в <tex>P(G)</tex>, нужно избавиться от split по которому Дейкстра достигла этого узла является решением. Путь <tex>s-t</tex> может быть построен из <tex>\sigma</tex> за линейное время путем вычисления последовательности запасных ребер <tex>seq(\sigma)</tex> и merge вершин путём проведения непересекающихся дигоналей затем <tex>s-t</tex> пути из таких вершиннеё. Если Дейкстра находит <tex>k</tex> кратчайших путей, то K* завершается успешно. Иначе, A* возобновляется для исследования большей части <tex>G</tex>. Это приводит к росту <tex>P(G)</tex>, на котором алгоритм Дейкстры затем будет возобновлен. Мы будем повторять этот процесс до тех пор, пока алгоритм Дейкстры не найдет <tex>k</tex> кратчайших путей.

Рассмотрим горизонтальную заметающую прямую <tex>l</tex>, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до <tex>l</tex> минимально, при этом она должна лежать соответственно выше или ниже <tex>l</tex>.Data: A graph given by its start vertex s ∈ V and its successor function succ and a[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split'' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнееnatural number kResult:A list R containing k sidetrack edge sequences representing k solution paths

# '''''Split вершина'''''. Пусть 1 <tex>e_jopen_D</tex> и ← пустая приоритетная очередь 2 <tex>e_kclosed_D</tex> — ближайшее левое и правое ребро относительно split вершины ← пустая хеш-таблица 3 <tex>v_iR</tex>, которые ← пустой список 4 <tex>lP(G)</tex> пересекает в данный момент. Нам нужно найти вершину, лежащую между ← пустой граф путей 5 Выполняем A* на графе <tex>e_jG</tex> и пока <tex>e_kt</tex>, наиболее приближённую к не будет выбрана для раскрытия 6 Если вершина <tex>lt</tex>не была достигнута, либо если такой точки не существет выбрать минимальную из верхних вершин то выходим без ответа 7 Кладем <tex>e_j\mathrm{R}</tex> и в очередь <tex>e_kopen_D</tex>. Для этого будем хранить указатель на искомую вершину у левого ребра 8 '''while''' A queue or open D is not empty: 9 '''if''' A queue is not empty: 10 '''if''' очередь <tex>e_jopen_D</tex>, который можно заранее вычислить. Тип вершины, хранящийся в не пуста: 11 Let u be the head of the search queue of A ∗ and n the head of <tex>helperopen_D</tex> не имеет значения. Таким образом, чтобы построить диагональ для split вершины нужно обратиться к указателю 12 <tex>helperd = max\{ d(e_jn)</tex> её левого ребра+ \Delta(n, которое <tex>ln') | n' \in succ(n) \}</tex> пересекает в данный момент.# 13 '''if''Merge вершина'''''. В отличие от случая со split вершиной заранее вычислить указатель <tex>helperg(t) + d <= f</tex> нельзя(u) then переходим на строку 17. 14 Возобновляем A* для того, поскольку merge вершина чтобы исследовать более большую часть графа <tex>v_iG</tex> должна быть соединена с вершиной, лежащей ниже заметающей прямой 15 Обновляем <tex>lP(G)</tex>. Для этого в and bring Dijkstra’s search into a consistent status 16 Переходим на строку 8 17 '''if''' очередь <tex>helper(e_j)open_D</tex> - левого относительно пуста: переходим на строку 8. 18 Remove from <tex>v_iopen_D</tex> ребра запишем саму and place on <tex>v_iclosed_D</tex>the node n with the minimal d-value. Далее спускаем заметающую прямую вниз к следующей вершине 19 '''foreach''' <tex>v_mn'</tex>, обращаемся к referred by n in P(G): 20 <tex>helperd(n') = d(n) + \Delta(n, n')</tex>'у её левого ребра. Проверяем, если там хранится merge вершина, строим диагональ 21 Attach to <tex>v_{i}v_{m}n'</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''merge'' вершины a parent link referring to <tex>v_in</tex>. На рисунке слева 22 Insert n 0 into <tex>v_iopen_D</tex> записывается в качестве 23 Пусть <tex>helper\sigma</tex>'а своего левого ребра. На правом рисунке ближайшая вершина будет путем в <tex>v_mP(G)</tex> при обращении к своему левому ребру , через который узел n был достигнут. 24 Добавим <tex>helperseq(e_j\sigma)</tex> находит в конец списка <tex>v_iR</tex> и образует диагональ . 25 '''if''' <tex>v_{i}v_m|R| = k</tex>]]: переходим на строку 26. 26 Return R and exit.

=== Структуры данных ===В подходе, описанном вышеАлгоритм 1 содержит псевдокод K*. Код с 8 по 25 строчку образует главный цикл K*. Цикл завершается, требуется находить пересечения заметающей прямой когда очереди обоих алгоритмов А* и левых ребёр многоугольникаДейкстры пусты. До 8 строчки выполняет некоторые подготовительные вещи. Создадим двоичное дерево поиска После инициализации, А* запускает на 5 строчке пока вершина <tex>Tt</tex>не будет выбрана им для рассмотрения, в листьях которого будем хранить рёбра, пересекающие этом случае кратчайший путь <tex>ls-t</tex>, такие, что внутренняя область многоугольника будет лежать справа от них самихнайден. С каждым таким ребром будем хранить его Если <tex>helpert</tex>не достигнута, то алгоритм завершается без ответа. Порядок следования листьев в дереве соответствует порядку следования рёбер в многоугольнике: слева направоОтметим, что он не завершится на бесконечных графах. Дерево изменяется в зависимости от текущего состояния заметающей прямой. Создадим приоритетную очередь Иначе, алгоритм добавляет специальную вершину <tex>QR</tex> из вершин, в которой приоритетом будет которая назначена корнем <tex>yP(G)</tex>-координата вершины, в поисковую очередь алгоритма Дейкстры. Если две вершины имеют одинаковые <tex>y</tex>-координатыЗатем, больший приоритет у левой. Вершины будут добавляться на "остановках" заметающей прямойK* входит в главный цикл.

Многоугольник K* поддерживает механизм планирования для контролирования, когда A* или Дейкстра будет возобновлены. Если очередь из A* не пуста, что означает, что А* ещё не завершил исследования всего графа G, то Дейкстра возобновляется тогда и только тогда, когда <tex>g(t) + d <= f(u)</tex>. Значение <tex>d</tex> является максимальным <tex>d</tex>-значением среди всех successor-ов головы поисковой очереди <tex>n</tex> алгоритма Дейкстры. Вершина <tex>u</tex> является головой поисковой очереди A*. Напомним, что <tex>d</tex> - функция расстояния, используемая в алгоритме Дейкстры. Если очередь поиска Дейкстры пуста или <tex>g(t) + d > f(u)</tex>, то А* возобновляется для того, чтобы исследовать более большую часть графа <tex>G</tex> (строка 14). То, как долго мы ему позволим работать, является компромиссом. Если мы запустим его только на маленьком количестве шагов, то мы дадим Дейкстре шанс найти необходимое количество путей скорее, чем они будут доступны в <tex>P(G)</tex> . С другой стороны, мы вызываем накладные расходы путем переключения A* и добавленные Дейкстры и поэтому должны ограничить количество переключений. Эти накладные расходы вызваны тем фактом, что после возобновления A* (строка 14), структура графа <tex>P(G)</tex> может измениться. Следовательно нам необходимо обновить <tex>P(G)</tex> (строка 15), как мы будет широко обсуждать в процессе диагонали удобно хранить разделе 4.5. Это требует последующую проверку статуса Дейкстры. Мы должны быть уверены, что Дейкстра поддерживает согласованное состояние после изменений в виде списка <tex>DP(G)</tex> рёбер с двойными связями (. K* предусматривает условие, которые управляет решением, когда остановить A*, которое мы назовем ''DCEL — doubly-connected edge listусловие расширения''). Для того, чтобы поддерживать аналогичную асимптотическую сложность как у EA и LVEA, мы должны определить условие расширения так, чтобы A* выполнялся пока количество рассмотренных вершин и количество внутренних ребер удваивается или <tex>G</tex> полностью исследован. Мы обсудим эту проблему несколько подробнее позже. В качестве полезного свойства, K* позволяет другое определения этого условия, которое может быть более эффективным на практике. В наших экспериментах в разделе 6, мы определили условие расширения так как потом это обеспечит эффективный доступ к каждой из частей, которые нужно будет триангулироватьчто количество рассмотренных вершин или количество рассмотренных ребер ребер возрастает на 20% при каждом запуске A*. Этот механизм планирования включен до тех пор, пока A* не закончит исследовать весь граф <tex>G</tex>. Как только A* исследует весь граф <tex>G</tex> (строка 9), механизм планирования отключается и в дальнейшем работает только алгоритм Дейкстры.

=== Псевдокод === MakeMonotone(P) Construct(D); Construct(Q); // функция Construct создаёт объекты Строки 18-22 представляют обычный шаг рассмотрения узла алгоритмом Дейкстры. Отметим, что когда successor-узел <tex>Dn'</tex> и сгенерирован, K* не проверяет был ли <tex>Qn'</tex> уже посещен до этого. Другими словами, описанные вышекаждый раз, когда узел генерируется, он рассматривает как новый. bst T = new bst(); while Q Эта стратегия обоснована на наблюдении, что путь s-t может содержать одно и то же ребро несколько раз. Строка 24 добавляет следующий путь <tex> \neq \varnothing s-t</tex> Remove в результирующее множество R. Это делается путем конструирования последовательности запасных ребер <tex>v_{max}</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex> switch seq(Type_of_vertex(<tex>v_{max}</tex>\sigma)): // определение типа вершины case 'start': HandleStartVertex(<tex>v_{max}</tex>); case 'end': HandleEndVertex(из пути <tex>v_{max}\sigma</tex>); case 'split': HandleSplitVertex(, через которые Дейкстра достигла узла <tex>v_{max}n</tex>); case 'merge': HandleMergeVertex(, который был только что рассмотрен. Алгоритм завершается, когда в результирующее множество добавлено <tex>v_{max}k</tex>); case 'regular': HandleRegularVertexпоследовательностей запасных ребер (<tex>v_{max}</tex>строка 25);.

[[Файл:Split== 4.5 Взаимосвязь алгоритмов Дейкстры и A* ==Тот факт, что оба алгоритма A* и Дейкстры делят между собой граф путей <tex>P(G)</tex>, вызывает обеспокоенность в отношении правильности работы Дейкстры на <tex>P(G)</tex>. Возобновление A* приводит к изменениям в структуре <tex>P(G)</tex>. Таким образом, после возобновления A*, мы обновляем <tex>P(G)</tex> и проверяет статус поиска Дейкстры (строка 15). В основном, A* может добавить новые узлы, менять <tex>\delta</tex>-merge - resultзначения существующих узлов или даже удалять узлы. A* может также существенно изменять дерево поиска <tex>T</tex>, которое будет в худшем случае разрушать структуру все деревянных куч <tex>H_{T}</tex>. Эти изменения могут приводить к глобальной реструктуризации или даже перестроению <tex>P(G)</tex> с нуля. В худшем случае это может сделать предыдущие поиски Дейкстры на <tex>P(G)</tex> бесполезными таким образом, что нам придется перезапускать алгоритм Дейкстры с нуля.png|470px|thumb|right]]

HandleStartVertexВ случае монотонной эвристической оценки мы даже не нуждаемся в восстановлении или перестроении <tex>P(G)</tex>. Если <tex>h</tex> монотонная, то дерево поиска A* является деревом кратчайшего пути для всех раскрытых вершин. Следовательно, g-значения раскрытых вершин не меняются. Это означает, что <tex>\delta</tex>-значения для внутренних ребер никогда не изменятся. Ребра дерева раскрытых вершин не изменятся также. Следовательно, обновление <tex>v_{i}\delta</tex>-значений, heaping-up, heaping-down (операции в кучах) Insert или удаление узлов не влекут за собой каких-либо изменений в <tex>e_{i}P(G)</tex> in T . Только добавление новых узлов приводит к изменениям в <tex>helperP(e_{i}G) \leftarrow v_i</tex>. Следовательно, восстановление или глобальное перестроение не требуется в данном случае.

HandleSplitVertex(<tex>v_{i}</tex>) edge <tex>e_jВ оставшейся части этого раздела, мы сначала покажем, что корректность поиска Дейкстры на </tex> = <tex>l \cap P</tex> Search <tex>e_j</tex> in T Insert edge(<tex>v_{i}G)</tex>поддерживается в случае допустимой эвристической оценки. После этого мы покажем, что изменения в <tex>helperP(e_{j}G)</tex>) in D <tex>helper(e_{j}) \leftarrow v_i</tex> Insert <tex>e_{i}</tex> in T <tex>helper(e_{i}) \leftarrow v_i</tex>могут помешать завершенности поиска Дейкстры независимо от того, является ли эвристика допустимой или даже монотонной. Следовательно, мы предложим механизм для её поддержания.

В последующих трех функциях обработки вершины Мы фокусируемся дальше на корректности поиска Дейкстры на <tex>v_iP(G)</tex> происходит обращение к смежному ребру в случае допустимой эвристической оценки. Сначала, мы заявляем, что если <tex>e_{i-1}h</tex>. Это сделано для вершиндопустимая, относительно которых внутренняя область то узлы исследованной части <tex>P</tex> лежит справа от них самих (вершина <tex>v_6</tex>G), либо для двух подряд идущих merge вершин, таких как <tex>v_2</tex> и не поменяют свои <tex>v_8\delta</tex>-значения.

HandleEndVertex({{Лемма|about=6|statement=Пусть <tex>v_{i}n</tex>будет произвольным узлов в <tex>P(G) if (Type_of_vertex(</tex> и пусть <tex>helper(e_{i-1}u,v)</tex> = 'merge') Insert edge(будет ребром, связанным с <tex>n</tex>. Если <tex>v_{i}h</tex>допустимая функция, то значение <tex>helper\delta(e_{i-1}u, v)</tex>) in D Delete никогда не изменится после того, как <tex>e_{i-1}n</tex> from Tбудет рассмотрен алгоритмом Дейкстры.|proof=...}}

|about=следствие 3|statement=Функция ''MakeMonotone(P)'' корректно выполняет разбиение многоугольника Пусть <tex>n</tex> будет произвольным узлом в <tex>P(G)</tex>. Другими словами эта функция добавляет в Если <tex>Ph</tex> множество непересекающихся диагоналейдопустимая функция, которые разбивают то <tex>Pn</tex> на монотонные части.|proof=Тот факт, что никогда не будет удален из <tex>P(G)</tex> разбивается на монотонные части следует из предыдущей леммы.Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритмапосле того, попарно не пересекаются и не пересекают стороны как <tex>Pn</tex>был рассмотрен алгоритмом Дейкстры.|proof=.. .}}

Рассмотрим случай выполнения функции ''HandleSplitVertex''Более того, поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершинмы докажем, в отличие от остальных функций что структура исследованной части <tex>P(в них рассматриваемая в данный момент вершина может быть соединена только с merge вершинойG)</tex> не изменится.

Допустим, что диагональ <tex>v_{i}v_{m}</tex> была построена с помощью ''HandleSplitVertex'' по достижению split вершины Лемма|about=7|statement=Пусть <tex>v_in</tex>. Рассмотрим четырёхугольник <tex>H</tex>, заключённый между <tex>e_j</tex> и <tex>e_k</tex> - левым и правым ребром относительно <tex>v_i</tex> и горизонтальными прямыми, проведёнными через <tex>v_i</tex> и <tex>v_m</tex>. Внутри <tex>H</tex>, не может находиться ни одной из вершин будет произвольным узлов в <tex>P</tex>, в противном случае <tex>helper(e_jG)</tex> не равнялся бы <tex>v_m</tex>. Предположим теперь, что <tex>v_{i}v_{m}</tex> пересекает <tex>e_sЕсли </tex> одну из сторон <tex>Ph</tex>. Учитываядопустимая функция, что никаких вершин <tex>P</tex> не лежит внутри то <tex>H</tex> и стороны <tex>Pn</tex> никогда не пересекаютсяизменит свою позицию после того, то <tex>e_s</tex> должна пересечь либо отрезок, соединяющий <tex>e_j</tex> и <tex>v_m</tex>, либо <tex>e_j</tex> и <tex>v_i</tex>как он был рассмотрен алгоритмом Дейкстры.|proof=.[[Файл:Pic_of_correctness.jpg‎|400px|thumb|right|1) Вершин внутри <tex>H</tex> находиться не может; 2) <tex>v_{i}v_m</tex> может пересекать только рёбра, помеченные зелёным]] Такое возможно только в случае, когда точками пересечения будут являться <tex>v_i</tex> или <tex>v_m</tex>, что не противоречит условию. Отсюда <tex>v_{i}v_{m}</tex> не пересекает ни одну из сторон <tex>P</tex> в посторонних точках.

Теперь рассмотрим случай с пересечением добавленной ранее диагональю. Поскольку внутри Леммы 6 и 7 обеспечивают, что изменения в <tex>HP(G)</tex> никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше <tex>v_i</tex>которые индуцируются A*, диагональ <tex>v_{i}v_m</tex> не может пересекать никакую из ранее добавленных диагоналей.}}===== Оценка работы =====Построение описанной выше приоритетной очереди <tex>Q</tex> происходит за линейное время. Когда заметающая прямая останавливается в вершине: операции с очередью занимают константу по времени, операции с деревом <tex>T</tex> влияют на запросы и обновления требуют часть <tex>\mathcal{O}P(\mathcal \log nG)</tex>, которую алгоритм Дейкстры уже исследовал. Добавление диагонали в Это гарантирует корректность поиска Дейкстры на <tex>D</tex> требует <tex>\mathcal{O}P(1G)</tex>, если используемая эвристика допустимая. В итоге обработка каждой вершины требует <tex>\mathcal{O}(\log n)</tex>Таким образом, каждый путь, а весь который предоставляет алгоритм соответственно <tex>\mathcal{O}(n \log n)</tex>Дейкстры корректен и его длина действительна. Что касается памятиОднако, она очевидно составляет это не обеспечивает завершенность поиска Дейкстры на <tex>\mathcal{O}P(nG) </tex>. Очередь <tex>Q</tex> и дерево <tex>T</tex> занимают линейную память.

[[Файл:Triangulationg introВозможно, что узел <tex>n'</tex> присоединяется к другом узлу n как ребенок, после раскрытия узла <tex>n</tex>.jpg|170px|thumb|right|Зелёным помечена так называемая воронкаВ этом случае братья <tex>n'</tex> будут рассотрены до того, которая образуетсякак <tex>n'</tex> станет ребенком n. Поэтому мы должны рассмотреть то, когда мы достигнем красной вершины]]что было упущено во время поиска в связи с отсутствием <tex>n'</tex>. Мы добиваемся этого путем применения строк 20-22 к <tex>n'</tex> для каждого раскрытого направленного predecessor-а узла <tex>n'</tex>. Если <tex>n'</tex> ещё не выполняет условие планирования, A* будет неоднократно возобновляться пока механизм планирования не допустит алгоритму Дейкстры положить <tex>n'</tex> в поисковую очередь. Заметим, что таким образом не требуется каких-либо дополнительных усилий во время типичного поиска Дейкстры.

== Триангуляция монотонного многоугольника ==Будем проходить сверху вниз по вершинам многоугольника проводя диагонали где Мы может быть уверены, что нерассмотренные узлы не будут принудительно опущены после применения операции heaping-up к <tex>n'</tex>. Иначе, мы могли бы иметь узел <tex>n''</tex>, который являлся бы ребенком n и впоследствии был бы заменен узлом <tex>n'</tex>. Заметим, что <tex>n''</tex> должен быть рассмотрен, поскольку <tex>n'</tex> был раскрыт. Однако, это возможнопротиворечение к лемме 7, которая гарантирует, что этого не произойдет.

Отсортируем все вершины многоугольника Более того, следующее следствие гарантирует, что наилучшее <tex>Pd(n')</tex> в порядке убывания их не лучше, чем <tex>yd</tex>-координаты. Заведём стек вершин <tex>S</tex>. В стеке будем хранить значение любой рассмотренной вершины в отсортированном порядке, которые были обработаны, но не были отрезаны от многоугольника, то есть находятся в той части многоугольникачастности, которая ещё не была триангулированараскрытой вершины. В момент обработки некоторой вершиныЭто означает, будем пытаться провести из неё как можно больше диагоналей к вершинам, содержащимся в стеке. Эти диагонали отрезают треугольники от что мы не упустим возможность раскрыть <tex>Pn'</tex>. На вершине стека будет храниться вершина, которая будет обрабатываться последней.

Часть многоугольника {{Лемма|about=следствие 3|statement=Пусть <tex>n</tex> будет узлом в <tex>P(G)</tex>, лежащая выше последней обработанной вершины который был раскрыт Дейкстрой. Кроме того, пусть <tex>v_im</tex> и которая ещё не была триангулирована имеет форму перевёрнутой воронки будет узлом, который заново добавляется в <tex>P(см. рисункиG). Одна сторона воронки состоит из одной из сторон </tex> или его позиция изменена, после того как <tex>Pn</tex>, а другая состоит из цепи вершин, которые лежат выше был раскрыт. Если <tex>v_ih</tex> и внутренние углы которых не меньше допустимая, тогда выполяется следующее:<tex>\piC_{P(G)}(R,m) >= d(n)</tex>|proof=. Несложно догадаться, что самая нижняя вершина стека является единственной выпуклой. Несложно также заметить, что при обработке следующей вершины свойство перевёрнутой воронки сохранится, то есть оно является инвариантом алгоритма.}}

[[Файл:Triang_alg_case1.jpg|200px|thumb|left|Первый случай. Синим помечены стороны воронки, зелёным — диагонали, а жёлтым границы новой ещё не протриангулированной области]][[Файл:Triang alg case2.jpg|300px|thumb|right|Второй случай. Синим помечена цепь из вершин, которая содержится в стеке <tex>S</tex> на момент достижения вершины <tex>v_j</tex>, рыжей помечена первая вершина, до которой невозможно провести диагональ, жёлтой помечена новая нетриангулированная область <tex>P</tex> в форме воронки]]=== Алгоритм =4.6 Пример ==Рассмотрим процесс обработки вершины более подробноМы проиллюстрируем работу алгоритма K* следующим примером. Мы будем рассматривать ориентированный взвешанный граф G на рисунке 7. Возможны два случая:* Текущая вершина Стартовой вершиной будет называться <tex>v_js_0</tex> является нижним концом стороны и конечной вершиной - <tex>es_6</tex>, ограничивающего воронку. Вершины противоположной цепи уже были положены в стек. В этом случае можно просто построить диагонали, соединяющие Нас интересует поиск 9 лучших путей из <tex>v_js_0</tex> со всеми вершинами, находящимися в стеке, кроме последней. Последняя вершина в стеке уже соединена с <tex>v_js_6</tex> стороной . Для достижения этой цели мы применим алгоритм K* к <tex>eG</tex>. Часть многоугольника <tex>P</tex>Предположим, лежащая выше <tex>v_j</tex>, которая не была триангулирована, ограничена диагональю, которая соединяет <tex>v_j</tex> с вершиной <tex>v_{s1}</tex>, которая была первой что эвристическая оценка существует. Значения эвристики даны в стеке. Сторона многоугольника пометках c <tex>Ph(s_0)</tex>, выходящая из по <tex>v_{s1}h(s_6)</tex> направлена вниз. Снова образуется фигура c одним выпуклым углом, похожая на воронку — инвариант сохраняетсярисунке 7. Вершины <tex>v_j</tex> и <tex>v_{s1}</tex> кладутся в стек, поскольку они были были обработаныЛегко заметить, но по прежнему являются вершинами непротриангулированной части <tex>P</tex>что эвристическая функция допустима.

Первый раз A* Вершина делает итерации на графе <tex>v_jG</tex> принадлежит последовательной цепи вершиндо тех пор, добавленных в пока не будет найдена вершина <tex>Ss_6</tex>. Вынем из стека верхнюю вершину Часть графа <tex>v_{s1}G</tex> — она , которая уже соединена с была рассмотрена иллиюстрируется на рисунке 8. Ребра, изображенные сплошными линиями, обозначают ребра дерева, в то время, как все остальные - запасные ребра. Они будет храниться в кучах <tex>v_H_{jin}</tex> одной из сторон , показанных на рисунке 9. Номера, присвоенные узлах кучи, соответствуют <tex>P\delta</tex>-значениям. Затем будем пытаться выстраивать диагонали, соединяющие На этом этапе поиска A* приостановлен и <tex>v_{j}P(G)</tex> c вынимаемыми из стека вершинами пока это возможнопостроен. Проверку на возможность построения диагонали Первоначально, только назначенный корень <tex>v_{j}v_{k}R</tex>, где явно доступен в <tex>v_{k}P(G)</tex> — текущая верхняя вершина стека, можно осуществлять посредством изучения взаимного расположения предыдущей вершины. Инициализируется алгоритм Дейкстры. Это означает, вынутой из что узел <tex>SR</tex>добавляется в поискую очередь Дейкстры. Планировщику требуется доступ к successors К для того, относительно чтобы решить следует ли возобновлять Дейкстру или A*. На данном этапе должна быть построена деревянная куча <tex>v_{j}v_H_{kT}(s_6)</tex>. Когда мы достигнем вершины Куча <tex>v_H_{kT}(s_4)</tex>, до которой невозможно провести диагональ, положим предыдущую вершину требуется для построения <tex>v_H_{k-1T}(s_6)</tex> обратно в стек. Вершина Следовательно, строются деревянные кучи <tex>v_H_{k-1T}(s_6)</tex> является либо последней, до которой было возможно провести диагональ, либо, если ни одной диагонали из <tex>v_H_{jT}(s_4)</tex> провести не удалось, — соседом <tex>v_H_{jT}(s_2)</tex>. Далее положим и <tex>v_H_{jT}(s_0)</tex> в стек. Опять же инвариант непротриангулированной части <tex>P</tex> сохраняется: одна сторона воронки ограничена частью стороны многоугольникаРезультат показан на рисунке 10, где сплошные линии представляют кучные ребра и пунктирные линии показывают кросс-ребра. Во избежание путаницы на рисунке некоторые из ребер не полностью изображены. Мы указываем каждое из них, а другая цепью невыпуклых вершиниспользуя короткую стрелку с конретной целью.

=== Псевдокод ===Как ранее уже было отмеченоПосле построения, как показано 10, задаём планировщик проверяет только ребенка <tex>P(s_4, s_2)</tex> в виде рёберного списка c двойными связями узла <tex>DR</tex>. TriangulateMonotonePolygon(P) vertex [n] V = new vertex(P); // массив вершин <tex>Pна предмет того, что </tex>, отсортированный по y-координате в порядке убывания. stack S = new stackg(s_6); S.push+ d(V[1]s_4,s_2); S.push<= f(V[2]s_1); for j <tex>\leftarrow</tex> 3 to n - 1 if (V[j] = S.peek()) while (S Отметим, что <tex>\neq \varnothing s_1</tex>) if (Sявляется головой поисковой очереди A*.size() Значение <tex>\neqd(s_4,s_2)</tex> 1) Insert edge(V[j]равно 2, Sт.peek()) in D Sе.pop() S.push(V[j-1]) S.push(V[j]); else vertex last <tex>\leftarrow</tex> S.peekg(s_6); S.pop+ d(s_4,s_2); while (IsValidDiagonal(edge= 7 + 2 = 9 = f(V[j], S.peek()), last)s_1) //проверка возможности построения //диагонали — предикат "левый поворот" last <tex>\leftarrow</tex> S.peek(); S.pop(); Insert edge(V[j]Следовательно, last) in D S.push(last); S.push(V[j]); S.pop() while (S планировщик позволяет Дейкстре раскрыть <tex>\neq \varnothing R</tex>) if (S.size() <tex>\neqи вставить </tex> 1) Insert edge(V[j]s_4, S.peek(s_2)) in D S.pop()=== Корректность ===* Все построенные диагонали попарно не пересекаются. Это гарантируется тем, что при каждом просмотре определённой вершины рассматривается только та часть <tex>P'</tex> многоугольника в поисковую очередь. При раскрытии <tex>PR</tex>, которая не была протриангулирована, следовательно внутри этой области по определению не может лежать ни одной находится первый путь из уже построенных диагоналейответа. Несложно заметить, что в стеке Он строится из пути <tex>SP(G)</tex> на каждой итерации главного цикла хранятся вершины, которые принадлежат именно содержащего единственный узел <tex>P'R</tex> и лежат выше рассматриваемой вершины.* Количество построенных диагоналей всегда будет Этот путь приводит к пустой последовательности запасных ребер. Напомним, что пустая последовательность запасных ребер соответствует пути из <tex>n-3s_0</tex>, поэтому непротриангулированных частей в многоугольнике не останется.=== Оценка работы ===Построение массива вершин требует линейное время и занимает линейную память. Главный цикл ''for'' выполняется <tex>n-3s_6</tex> раза. Каждая его итерация может потребовать линейное время. Однако заметим, что на каждой итерации главного цикла в стек кладутся максимум две вершиныдереве поиска, следовательно общее число выполнения операции ''push'', включая первые две вершины, положенные в начале алгоритма, ограничено а именно <tex>2n-4s_0s_2s_4s_6</tex>длиной 7. Количество операций ''pop'' за время работы алгоритма не превысит количества операций ''push''. Отсюда общее время работы цикла ''for'' Затем поиск Дейкстры приостанавливается, потому что для successor-ов узла <tex>\mathcal{O}(ns_4,s_2)</tex>. В итоге общее время работы не выполняется условие <tex>\mathcal{O}g(ns_6)</tex>.=== Общая оценка ===Разбиение многоугольника на монотонные части занимает <tex>\mathcal{O}+d(n \log n)</tex> времени и <tex>\mathcal{O}=f(ns_1)</tex> памяти. Триангуляция каждой из частей занимает линейную память и время. Учитывая тоСледовательно, что суммарное количество вершин во всех частях <tex>\mathcal{O}(n)</tex>, триангуляция всех частей займёт <tex>\mathcal{O}(n)</tex> по времени и по памятивозобновляется A*.

В итоге общая оценка составляет Мы предполагаем, что условие раскрытия определено как раскрытие одной вершины для того, чтобы пример был простым и иллюстративным. Поэтому A* раскрывает <tex>s_1</tex> и останавливается. Исследованная часть <tex>G</tex> на текущем этапе показана на рисунке 11. Результат раскрытия приведет к обнаружению 2 новых запасных ребер <tex>(s_1,s_2)</tex> и <tex>\mathcal(s_1,s_6)</tex>, которые будут добавлены в <tex>H_{Oin}(n \log ns_2)</tex> по времени и <tex>\mathcalH_{Oin}(ns_6)</tex> по памятисоответственно. Обновленные кучи <tex>H_{in}(s_2)</tex> и <tex>H_{in}(s_6)</tex> представлены на рисунке 12. Другие кучи остаются неизменными, как на рисунке 9. Граф путей <tex>P(G)</tex> перестаивается, как показано на рисунке 13. Затем алгоритм Дейкстры возобновляется. Заметим, что поисковая очередь Дейкстры содержит только <tex>(s_4,s_2)</tex> с <tex>d = 2</tex> на этом моменте. Используя ручное выполнение мы можем легко увидеть, что Дейкстра будет выдавать в ответ пути, перечисленные в таблице 1.