Участник:Kabanov — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (4.5 Взаимосвязь алгоритмов Дейкстры и A*)
 
(не показано 17 промежуточных версий 2 участников)
Строка 1: Строка 1:
=== Монотонный метод ===
+
Также как и алгоритм Эппштейна, K* выполняет поиск пути на графе <tex>G</tex> и использует граф путей <tex>P(G)</tex>. Граф путей ищется с помощью алгоритма Дейкстры для того, чтобы вычислить пути <tex>s-t</tex> в виде последовательности запасных путей. Общий принцип работы алгоритма K* следующий:
  
{{Определение
+
1) K* применяет A* на графе <tex>G</tex> вместо обратного алгоритма Дейкстры, который используется алгоритмом Эппштейна.
|id=def_monotone_polygon
+
2) Мы запускаем A* на <tex>G</tex> и Дейкстру на <tex>P(G)</tex> в поочередном порядке, который позволяет Дейкстре вычислить требуемые пути до заверешения полного поиска алгоритма A* на графе <tex>G</tex> .
|definition=
+
 
Простой многоугольник <tex>P</tex> называется '''монотонным''' относительно прямой <tex>l</tex>, если любая <tex>l'</tex>, такая что <tex>l' \perp l</tex>, пересекает стороны <tex>P</tex> не более двух раз (результатом пересечения <tex>l'</tex> и <tex>P</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|thumb|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) = g(u) + c(u, v) - g(v)</tex>
 +
 
 +
Заметим, что <tex>\delta(u, v)</tex> дает точную объездную метрику, поскольку оценочное <tex>h</tex>-значение не появляется в определении функции <tex>\delta(u, v)</tex>.
 +
 
 +
== 4.3 Структура графа путей ==
 +
Структура графа путей <tex>P(G)</tex> довольно сложная. В принципе, <tex>P(G)</tex> будет ориентированным графом, вершины которого соответствуют ребрам в исходном графе <tex>G</tex>. Он будет организован как коллекция взаимосвязанных '''куч''' (англ. ''heap''). 2 бинарные кучи минимума присвоены к каждой вершине <tex>v</tex> в графе <tex>G</tex>, которые называются '''входящей кучей''' (англ. ''incoming heap'')<tex>H_{in}(v)</tex> и '''деревянной кучей''' (англ. ''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>root_{in}(v)</tex>.
 +
 
 +
'''Пример 4.''' Рисунок 4 иллюстрирует входящие кучи графа из рисунка 3. Цифры рядом с узлами кучи соответствуют <tex>\delta</tex>-значениям.
 +
 
 +
[[Файл:kstar-figure-4.png|600px|thumb|center|'''Рисунок 4.''' Входящие кучи <tex>H_{in}(s_i)</tex>, полученные из графа, показанного на рисунке 3.]]
 +
 
 +
Деревянная куча <tex>H_{T}(v)</tex> для произвольной вершины <tex>v</tex> строится следующим образом. Если <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>-значением. Мы назовем такую кучу '''графовой кучей''' (англ. ''graph heap'') вершины <tex>v</tex> и обозначим её как <tex>H_{G}(v)</tex>.
 +
|proof=Те узлы, которые находятся в <tex>H_{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</tex>-оси называется '''<tex>y</tex>-монотонным'''.
+
Более того, мы определим весовую функцию <tex>\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>\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>
  
 +
Лемма 1 подразумевает, что куча упорядоченная в соответствии с <tex>\delta</tex>-значанием поддерживается для любого кучного ребра из <tex>P(G)</tex>. Эта упорядочивание кучи подразумевает, что <tex>\Delta(n,n')</tex> неотрицательна для любого кучного ребра <tex>(n,n')</tex>. Следовательно, <tex>\Delta</tex> также неотрицательна, т.е. <tex>\Delta(n,n') >= 0</tex> для любого ребра <tex>(n,n')</tex> в <tex>P(G)</tex>. Стоимость пути <tex>\sigma</tex>, т.е. <tex>C_{P(G)}(\sigma)</tex> равна <tex>\sum_{e \in \sigma}\Delta(e)</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_{i-1} > y_i</tex> и <tex>y_i < y_{i+1}</tex>. Опишем более подробно этот тип вершин.
+
В оставшейся части этого раздела мы проиллюстрируем особенности структуры графа путей, которые актуальны для нахождения кратчайших путей <tex>s-t</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>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>\phi</tex> внутренний угол при некоторой вершине и определим далее пять типов вершин, четыре из которых являются поворотными:
+
Первое наблюдение в том, что <tex>P(G)</tex> ориентированный взвешенный граф. Каждый узел в <tex>P(G)</tex> несет запасное ребро из G. Использование бинарных куч в конструкции <tex>P(G)</tex> извлекает выгоду из следующих 2 свойств. Во-первых, произвольный узел в <tex>P(G)</tex> имеет не более 4 выходящих ребер. Одним из ребер будет точно кросс-ребро в то время, как оставшимися будут кучные ребра. Во-вторых, функция веса <tex>\Delta</tex> неотрицательна. Как станет ясно в разделе 5, эти свойства необходимы для доказательства правильности и определения сложности K*.
* '''''start вершина''''' — два её соседа лежат ниже её самой и <tex> \phi < \pi </tex>
 
* '''''split вершина''''' — два её соседа лежат ниже её самой и <tex> \phi > \pi </tex>
 
* '''''end вершина''''' — два её соседа лежат выше её самой и <tex> \phi < \pi </tex>
 
* '''''merge вершина''''' — два её соседа лежат выше её самой и <tex> \phi > \pi </tex>
 
* '''''regular вершина''''' — не является поворотной, в отличие от остальных, другими словами один её сосед находится выше, а другой ниже её самой.
 
  
{{Лемма
+
Второе наблюдение заключается в существовании соответствия один-к-одному между путей <tex>s-t</tex> в <tex>G</tex> и путей в <tex>Р(G)</tex>, которые начинаются в <tex>\mathrm{R}</tex>.
|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>-монотонный, существует горизонтальная прямая <tex>l</tex>, которая пересекает его стороны более двух раз. Выберем <tex>l</tex> таким образом, чтобы самой левой компонентой пересечения <tex>l</tex> и <tex>P</tex> был бы отрезок <tex>pq</tex>. Далее будем двигаться наверх по сторонам <tex>P</tex>, начиная от точки <tex>q</tex>. В результате в некоторой точке <tex>r</tex>, где <tex>r \neq p</tex> (случай '''(a)''' на рисунке), прямая <tex>l</tex> снова пересечёт одну из сторон <tex>P</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам <tex>P</tex>, будет split вершиной.
 
  
[[Файл:Proof_lemma.jpg|450px]]
+
...
  
Если же <tex>r = p</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам <tex>P</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка <tex>r'</tex>, которая будет результатом пересечения <tex>l</tex> и <tex>P</tex>. При этом <tex>r' \neq p</tex>, в противном случае <tex>l</tex> будет пересекать <tex>P</tex> только два раза, что противоречит выбору <tex>l</tex>. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.
+
{{Лемма
 +
|about=2
 +
|statement=Пусть <tex>n</tex> будет узлом графовой кучи <tex>H_{G}(w)</tex> для какой-нибудь вершины <tex>w</tex>. Пусть <tex>(u,v)</tex> будет ребром связанным с <tex>n</tex>. Тогда существует путь в дереве поиска <tex>T</tex> из <tex>v</tex> в <tex>w</tex>.
 +
|proof=...
 
}}
 
}}
  
=== Алгоритм ===
+
== 4.4 Алгоритмическая структура K* ==
Чтобы сделать многоугольник монотонным, нужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершин.
+
Алгоритмический принцип K* следующий. Будем запускать алгоритмы Дейкстры и A* на <tex>G</tex> с чередованием. Сначала, мы выполним A* на <tex>G</tex>, который будет работать до тех, пока вершина <tex>t</tex> не будет выбрана из очереди для раскрытия. Затем, вы запустим алгоритм Дейкстры на доступной части <tex>P(G)</tex>. Каждый узел раскрытый Дейкстрой представляет путь. Если точнее, то путь <tex>\sigma</tex> в <tex>P(G)</tex>, по которому Дейкстра достигла этого узла является решением. Путь <tex>s-t</tex> может быть построен из <tex>\sigma</tex> за линейное время путем вычисления последовательности запасных ребер <tex>seq(\sigma)</tex> и затем <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 k
 +
Result: A list R containing k sidetrack edge sequences representing k solution paths
  
# '''''Split вершина'''''. Пусть <tex>e_j</tex> и <tex>e_k</tex> — ближайшее левое и правое ребро относительно split вершины <tex>v_i</tex>, которые <tex>l</tex> пересекает в данный момент. Нам нужно найти вершину, лежащую между <tex>e_j</tex> и <tex>e_k</tex>, наиболее приближённую к <tex>l</tex>, либо если такой точки не существет выбрать минимальную из верхних вершин <tex>e_j</tex> и <tex>e_k</tex>. Для этого будем хранить указатель на искомую вершину у левого ребра <tex>e_j</tex>, который можно заранее вычислить. Тип вершины, хранящийся в <tex>helper</tex> не имеет значения. Таким образом, чтобы построить диагональ для split вершины нужно обратиться к указателю <tex>helper(e_j)</tex> её левого ребра, которое <tex>l</tex> пересекает в данный момент.
+
  1  <tex>open_D</tex> ← пустая приоритетная очередь
# '''''Merge вершина'''''. В отличие от случая со split вершиной заранее вычислить указатель <tex>helper</tex> нельзя, поскольку merge вершина <tex>v_i</tex> должна быть соединена с вершиной, лежащей ниже заметающей прямой <tex>l</tex>. Для этого в <tex>helper(e_j)</tex> - левого относительно <tex>v_i</tex> ребра запишем саму <tex>v_i</tex>. Далее спускаем заметающую прямую вниз к следующей вершине <tex>v_m</tex>, обращаемся к <tex>helper</tex>'у её левого ребра. Проверяем, если там хранится merge вершина, строим диагональ <tex>v_{i}v_{m}</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.
+
  2  <tex>closed_D</tex> ← пустая хеш-таблица
[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''merge'' вершины <tex>v_i</tex>. На рисунке слева <tex>v_i</tex> записывается в качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}v_m</tex>]]
+
  3  <tex>R</tex> ← пустой список
 +
  4  <tex>P(G)</tex> ← пустой граф путей
 +
  5  Выполняем A* на графе <tex>G</tex> пока <tex>t</tex> не будет выбрана для раскрытия
 +
  6  Если вершина <tex>t</tex> не была достигнута, то выходим без ответа
 +
  7  Кладем <tex>\mathrm{R}</tex> в очередь <tex>open_D</tex>
 +
  8  '''while''' A queue or open D is not empty:
 +
  9    '''if''' A queue is not empty:
 +
  10      '''if''' очередь <tex>open_D</tex> не пуста:
 +
  11          Let u be the head of the search queue of A ∗ and n the head of <tex>open_D</tex>
 +
  12          <tex>d = max\{ d(n) + \Delta(n, n') | n' \in succ(n) \}</tex>
 +
  13          '''if''' <tex>g(t) + d <= f</tex> (u) then переходим на строку 17.
 +
  14      Возобновляем A* для того, чтобы исследовать более большую часть графа <tex>G</tex>
 +
  15      Обновляем <tex>P(G)</tex> and bring Dijkstra’s search into a consistent status
 +
  16      Переходим на строку 8
 +
  17    '''if''' очередь <tex>open_D</tex> пуста: переходим на строку 8.
 +
  18    Remove from <tex>open_D</tex> and place on <tex>closed_D</tex> the node n with the minimal d-value.
 +
  19    '''foreach''' <tex>n'</tex> referred by n in P(G):
 +
  20      <tex>d(n') = d(n) + \Delta(n, n')</tex>
 +
  21      Attach to <tex>n'</tex> a parent link referring to <tex>n</tex>.
 +
  22      Insert n 0 into <tex>open_D</tex>
 +
  23    Пусть <tex>\sigma</tex> будет путем в <tex>P(G)</tex>, через который узел n был достигнут.
 +
  24    Добавим <tex>seq(\sigma)</tex> в конец списка <tex>R</tex>.
 +
  25    '''if''' <tex>|R| = k</tex>: переходим на строку 26.
 +
  26 Return R and exit.
  
=== Структуры данных ===
+
Алгоритм 1 содержит псевдокод K*. Код с 8 по 25 строчку образует главный цикл K*. Цикл завершается, когда очереди обоих алгоритмов А* и Дейкстры пусты. До 8 строчки выполняет некоторые подготовительные вещи. После инициализации, А* запускает на 5 строчке пока вершина <tex>t</tex> не будет выбрана им для рассмотрения, в этом случае кратчайший путь <tex>s-t</tex> будет найден. Если <tex>t</tex> не достигнута, то алгоритм завершается без ответа. Отметим, что он не завершится на бесконечных графах. Иначе, алгоритм добавляет специальную вершину <tex>R</tex>, которая назначена корнем <tex>P(G)</tex>, в поисковую очередь алгоритма Дейкстры. Затем, K* входит в главный цикл.
В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <tex>T</tex>, в листьях которого будем хранить рёбра, пересекающие <tex>l</tex>, такие, что внутренняя область многоугольника будет лежать справа от них самих. С каждым таким ребром будем хранить его <tex>helper</tex>. Порядок следования листьев в дереве  соответствует порядку следования рёбер в многоугольнике: слева направо. Дерево изменяется в зависимости от текущего состояния заметающей прямой. Создадим приоритетную очередь <tex>Q</tex> из вершин, в которой приоритетом будет <tex>y</tex>-координата вершины. Если две вершины имеют одинаковые <tex>y</tex>-координаты, больший приоритет у левой. Вершины будут добавляться на "остановках" заметающей прямой.
 
  
Многоугольник <tex>P</tex> и добавленные в процессе диагонали удобно хранить в виде списка <tex>D</tex> рёбер с двойными связями (''DCEL — doubly-connected edge list''), так как потом это обеспечит эффективный доступ к каждой из частей, которые нужно будет триангулировать.
+
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>P(G)</tex>. K* предусматривает условие, которые управляет решением, когда остановить A*, которое мы назовем ''условие расширения''. Для того, чтобы поддерживать аналогичную асимптотическую сложность как у EA и LVEA, мы должны определить условие расширения так, чтобы A* выполнялся пока количество рассмотренных вершин и количество внутренних ребер удваивается или <tex>G</tex> полностью исследован. Мы обсудим эту проблему несколько подробнее позже. В качестве полезного свойства, K* позволяет другое определения этого условия, которое может быть более эффективным на практике. В наших экспериментах в разделе 6, мы определили условие расширения так, что количество рассмотренных вершин или количество рассмотренных ребер ребер возрастает на 20% при каждом запуске A*. Этот механизм планирования включен до тех пор, пока A* не закончит исследовать весь граф <tex>G</tex>. Как только A* исследует весь граф <tex>G</tex> (строка 9), механизм планирования отключается и в дальнейшем работает только алгоритм Дейкстры.
  
=== Псевдокод ===
+
Строки 18-22 представляют обычный шаг рассмотрения узла алгоритмом Дейкстры. Отметим, что когда successor-узел <tex>n'</tex> сгенерирован, K* не проверяет был ли <tex>n'</tex> уже посещен до этого. Другими словами, каждый раз, когда узел генерируется, он рассматривает как новый. Эта стратегия обоснована на наблюдении, что путь s-t может содержать одно и то же ребро несколько раз. Строка 24 добавляет следующий путь <tex>s-t</tex> в результирующее множество R. Это делается путем конструирования последовательности запасных ребер <tex>seq(\sigma)</tex> из пути <tex>\sigma</tex>, через которые Дейкстра достигла узла <tex>n</tex>, который был только что рассмотрен. Алгоритм завершается, когда в результирующее множество добавлено <tex>k</tex> последовательностей запасных ребер (строка 25).
MakeMonotone(P)
 
    Construct(D);
 
    Construct(Q); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше.
 
    bst T = new bst();
 
    while Q <tex> \neq  \varnothing </tex>
 
      Remove <tex>v_{max}</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex>   
 
      switch (Type_of_vertex(<tex>v_{max}</tex>)): // определение типа вершины
 
          case 'start':
 
            HandleStartVertex(<tex>v_{max}</tex>);
 
          case 'end':
 
            HandleEndVertex(<tex>v_{max}</tex>);
 
          case 'split':
 
            HandleSplitVertex(<tex>v_{max}</tex>);
 
          case 'merge':
 
            HandleMergeVertex(<tex>v_{max}</tex>);
 
          case 'regular':
 
            HandleRegularVertex(<tex>v_{max}</tex>);
 
  
[[Файл:Split-merge - result.png|470px|thumb|right]]
+
== 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>-значения существующих узлов или даже удалять узлы. A* может также существенно изменять дерево поиска <tex>T</tex>, которое будет в худшем случае разрушать структуру все деревянных куч <tex>H_{T}</tex>. Эти изменения могут приводить к глобальной реструктуризации или даже перестроению <tex>P(G)</tex> с нуля. В худшем случае это может сделать предыдущие поиски Дейкстры на <tex>P(G)</tex> бесполезными таким образом, что нам придется перезапускать алгоритм Дейкстры с нуля.
  
Опишем теперь каждый метод из последнего switch:
+
Если использованная эвристическая оценка допустимая, то наше положение лучше. Нам по-прежнему может понадобится перестроение <tex>P(G)</tex>, но мы покажем, что это перестроение не мешает корректности поиска Дейкстры на <tex>P(G)</tex>. Другими словами, мы не теряем результаты, до сих пор полученные поиском Дейкстры.
  
HandleStartVertex(<tex>v_{i}</tex>)
+
В случае монотонной эвристической оценки мы даже не нуждаемся в восстановлении или перестроении <tex>P(G)</tex>. Если <tex>h</tex> монотонная, то дерево поиска A* является деревом кратчайшего пути для всех раскрытых вершин. Следовательно, g-значения раскрытых вершин не меняются. Это означает, что <tex>\delta</tex>-значения для внутренних ребер никогда не изменятся. Ребра дерева раскрытых вершин не изменятся также. Следовательно, обновление <tex>\delta</tex>-значений, heaping-up, heaping-down (операции в кучах) или удаление узлов не влекут за собой каких-либо изменений в <tex>P(G)</tex>. Только добавление новых узлов приводит к изменениям в <tex>P(G)</tex>. Следовательно, восстановление или глобальное перестроение не требуется в данном случае.
    Insert <tex>e_{i}</tex> in T
 
    <tex>helper(e_{i}) \leftarrow  v_i</tex>
 
  
HandleSplitVertex(<tex>v_{i}</tex>)
+
В оставшейся части этого раздела, мы сначала покажем, что корректность поиска Дейкстры на <tex>P(G)</tex> поддерживается в случае допустимой эвристической оценки. После этого мы покажем, что изменения в <tex>P(G)</tex> могут помешать завершенности поиска Дейкстры независимо от того, является ли эвристика допустимой или даже монотонной. Следовательно, мы предложим механизм для её поддержания.
    edge <tex>e_j</tex> = <tex>l \cap P</tex>
 
    Search <tex>e_j</tex> in T
 
    Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</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_i</tex> происходит обращение к смежному ребру <tex>e_{i-1}</tex>. Это сделано для вершин, относительно которых внутренняя область <tex>P</tex> лежит справа от них самих (вершина <tex>v_6</tex>), либо для двух подряд идущих merge вершин, таких как <tex>v_2</tex> и <tex>v_8</tex>.
+
Мы фокусируемся дальше на корректности поиска Дейкстры на <tex>P(G)</tex> в случае допустимой эвристической оценки. Сначала, мы заявляем, что если <tex>h</tex> допустимая, то узлы исследованной части <tex>P(G)</tex> не поменяют свои <tex>\delta</tex>-значения.
  
HandleEndVertex(<tex>v_{i}</tex>)
+
{{Лемма
    if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge')
+
|about=6
      Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in D
+
|statement=Пусть <tex>n</tex> будет произвольным узлов в <tex>P(G)</tex> и пусть <tex>(u,v)</tex> будет ребром, связанным с <tex>n</tex>. Если <tex>h</tex> допустимая функция, то значение <tex>\delta(u, v)</tex> никогда не изменится после того, как <tex>n</tex> будет рассмотрен алгоритмом Дейкстры.
    Delete <tex>e_{i-1}</tex> from T
+
|proof=...
 +
}}
  
HandleMergeVertex(<tex>v_{i}</tex>)
+
Из леммы 6 мы может вывести следующее следствие.
    if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge')
 
      Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in D
 
    Delete <tex>e_{i-1}</tex> from T
 
    edge <tex>e_j</tex> = <tex>l \cap P</tex>
 
    Search <tex>e_j</tex> in T
 
    if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
 
      Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
 
    <tex>helper(e_{j}) \leftarrow  v_i</tex>
 
  
HandleRegularVertex(<tex>v_{i}</tex>)
 
    if (interior of <tex>P</tex> lies to the right of <tex>v_{i}</tex>)
 
      then
 
          if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge')
 
            Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in D
 
          Delete <tex>e_{i-1}</tex> from T
 
          Insert <tex>e_{i}</tex> in T
 
          <tex>helper(e_{i}) \leftarrow  v_i</tex>
 
      else
 
          edge <tex>e_j</tex> = <tex>l \cap P</tex>
 
          Search <tex>e_j</tex> in T
 
          if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
 
            Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
 
          <tex>helper(e_{j}) \leftarrow  v_i</tex>
 
===== Корректность =====
 
 
{{Лемма
 
{{Лемма
|statement=
+
|about=следствие 3
Функция ''MakeMonotone(P)'' корректно выполняет разбиение многоугольника <tex>P</tex>. Другими словами эта функция добавляет в <tex>P</tex> множество непересекающихся диагоналей, которые разбивают <tex>P</tex> на монотонные части.
+
|statement=Пусть <tex>n</tex> будет произвольным узлом в <tex>P(G)</tex>. Если <tex>h</tex> допустимая функция, то <tex>n</tex> никогда не будет удален из <tex>P(G)</tex> после того, как <tex>n</tex> был рассмотрен алгоритмом Дейкстры.
|proof=Тот факт, что <tex>P</tex> разбивается на монотонные части следует из предыдущей леммы.
+
|proof=...
Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, попарно не пересекаются и не пересекают стороны <tex>P</tex>.  
+
}}
  
Рассмотрим случай выполнения функции ''HandleSplitVertex'', поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций (в них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной).  
+
Более того, мы докажем, что структура исследованной части <tex>P(G)</tex> не изменится.
  
Допустим, что диагональ <tex>v_{i}v_{m}</tex> была построена с помощью ''HandleSplitVertex'' по достижению split вершины <tex>v_i</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_j)</tex> не равнялся бы <tex>v_m</tex>. Предположим теперь, что <tex>v_{i}v_{m}</tex> пересекает <tex>e_s</tex> одну из сторон <tex>P</tex>. Учитывая, что никаких вершин <tex>P</tex> не лежит внутри <tex>H</tex> и стороны <tex>P</tex> не пересекаются, то <tex>e_s</tex> должна пересечь либо отрезок, соединяющий <tex>e_j</tex> и <tex>v_m</tex>, либо <tex>e_j</tex> и <tex>v_i</tex>.[[Файл: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> в посторонних точках.
+
{{Лемма
 +
|about=7
 +
|statement=Пусть <tex>n</tex> будет произвольным узлов в <tex>P(G)</tex>. Если <tex>h</tex> допустимая функция, то <tex>n</tex> никогда не изменит свою позицию после того, как он был рассмотрен алгоритмом Дейкстры.
 +
|proof=...
 +
}}
  
  
Теперь рассмотрим случай с пересечением добавленной ранее диагональю. Поскольку внутри <tex>H</tex> никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше <tex>v_i</tex>, диагональ <tex>v_{i}v_m</tex> не может пересекать никакую из ранее добавленных диагоналей.
+
Леммы 6 и 7 обеспечивают, что изменения в <tex>P(G)</tex>, которые индуцируются A*, не влияют на часть <tex>P(G)</tex>, которую алгоритм Дейкстры уже исследовал. Это гарантирует корректность поиска Дейкстры на <tex>P(G)</tex>, если используемая эвристика допустимая. Таким образом, каждый путь, который предоставляет алгоритм Дейкстры корректен и его длина действительна. Однако, это не обеспечивает завершенность поиска Дейкстры на <tex>P(G)</tex>.
}}
 
===== Оценка работы =====
 
Построение описанной выше приоритетной очереди <tex>Q</tex> происходит за линейное время. Когда заметающая прямая останавливается в вершине: операции с очередью занимают константу по времени, операции с деревом <tex>T</tex> на запросы и обновления требуют <tex>\mathcal{O}(\mathcal \log n)</tex>. Добавление диагонали в <tex>D</tex> требует <tex>\mathcal{O}(1)</tex>. В итоге обработка каждой вершины требует <tex>\mathcal{O}(\log n)</tex>, а весь алгоритм соответственно <tex>\mathcal{O}(n \log n)</tex>. Что касается памяти, она очевидно составляет <tex>\mathcal{O}(n) </tex>. Очередь <tex>Q</tex> и дерево <tex>T</tex> занимают линейную память.
 
  
[[Файл:Triangulationg intro.jpg|170px|thumb|right|Зелёным помечена так называемая воронка, которая образуется, когда мы достигнем красной вершины]]
+
Возможно, что узел <tex>n'</tex> присоединяется к другом узлу n как ребенок, после раскрытия узла <tex>n</tex>. В этом случае братья <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>P</tex> в порядке убывания их <tex>y</tex>-координаты. Заведём стек вершин <tex>S</tex>. В стеке будем хранить вершины в отсортированном порядке, которые были обработаны, но не были отрезаны от многоугольника, то есть находятся в той части многоугольника, которая ещё не была триангулирована. В момент обработки некоторой вершины, будем пытаться провести из неё как можно больше диагоналей к вершинам, содержащимся в стеке. Эти диагонали отрезают треугольники от <tex>P</tex>. На вершине стека будет храниться вершина, которая будет обрабатываться последней.
+
Более того, следующее следствие гарантирует, что наилучшее <tex>d(n')</tex> не лучше, чем <tex>d</tex>-значение любой рассмотренной вершины, в частности, раскрытой вершины. Это означает, что мы не упустим возможность раскрыть <tex>n'</tex>.
  
Часть многоугольника <tex>P</tex>, лежащая выше последней обработанной вершины <tex>v_i</tex> и которая ещё не была триангулирована имеет форму перевёрнутой воронки (см. рисунки). Одна сторона воронки состоит из одной из сторон <tex>P</tex>, а другая состоит из цепи вершин, которые лежат выше <tex>v_i</tex> и внутренние углы которых не меньше <tex>\pi</tex>. Несложно догадаться, что самая нижняя вершина стека является единственной выпуклой. Несложно также заметить, что при обработке следующей вершины свойство перевёрнутой воронки сохранится, то есть оно является инвариантом алгоритма.
+
{{Лемма
 +
|about=следствие 3
 +
|statement=Пусть <tex>n</tex> будет узлом в <tex>P(G)</tex>, который был раскрыт Дейкстрой. Кроме того, пусть <tex>m</tex> будет узлом, который заново добавляется в <tex>P(G)</tex> или его позиция изменена, после того как <tex>n</tex> был раскрыт. Если <tex>h</tex> допустимая, тогда выполяется следующее:
 +
<tex>C_{P(G)}(R,m) >= d(n)</tex>
 +
|proof=...
 +
}}
  
[[Файл:Triang_alg_case1.jpg|200px|thumb|left|Первый случай. Синим помечены стороны воронки, зелёным — диагонали, а жёлтым границы новой ещё не протриангулированной области]]
+
== 4.6 Пример ==
[[Файл:Triang alg case2.jpg|300px|thumb|right|Второй случай. Синим помечена цепь из вершин, которая содержится в стеке <tex>S</tex> на момент достижения вершины <tex>v_j</tex>, рыжей помечена первая вершина, до которой невозможно провести диагональ, жёлтой помечена новая нетриангулированная область <tex>P</tex> в форме воронки]]
+
Мы проиллюстрируем работу алгоритма K* следующим примером. Мы будем рассматривать ориентированный взвешанный граф G на рисунке 7. Стартовой вершиной будет называться <tex>s_0</tex> и конечной вершиной - <tex>s_6</tex>. Нас интересует поиск 9 лучших путей из <tex>s_0</tex> в <tex>s_6</tex>. Для достижения этой цели мы применим алгоритм K* к <tex>G</tex>. Предположим, что эвристическая оценка существует. Значения эвристики даны в пометках c <tex>h(s_0)</tex> по <tex>h(s_6)</tex> на рисунке 7. Легко заметить, что эвристическая функция допустима.
=== Алгоритм ===
 
Рассмотрим процесс обработки вершины более подробно. Возможны два случая:
 
* Текущая вершина <tex>v_j</tex> является нижним концом стороны <tex>e</tex>, ограничивающего воронку. Вершины противоположной цепи уже были положены в стек. В этом случае можно просто построить диагонали, соединяющие <tex>v_j</tex> со всеми вершинами, находящимися в стеке, кроме последней. Последняя вершина в стеке уже соединена с <tex>v_j</tex> стороной <tex>e</tex>. Часть многоугольника <tex>P</tex>, лежащая выше <tex>v_j</tex>, которая не была триангулирована, ограничена диагональю, которая соединяет <tex>v_j</tex> с вершиной <tex>v_{s1}</tex>, которая была первой в стеке. Сторона многоугольника <tex>P</tex>, выходящая из <tex>v_{s1}</tex> направлена вниз. Снова образуется фигура c одним выпуклым углом, похожая на воронку — инвариант сохраняется. Вершины <tex>v_j</tex> и <tex>v_{s1}</tex>  кладутся в стек, поскольку они были были обработаны, но по прежнему являются вершинами непротриангулированной части <tex>P</tex>.
 
  
* Вершина <tex>v_j</tex> принадлежит последовательной цепи вершин, добавленных в <tex>S</tex>. Вынем из стека верхнюю вершину <tex>v_{s1}</tex> — она уже соединена с <tex>v_{j}</tex> одной из сторон <tex>P</tex>. Затем будем пытаться выстраивать диагонали, соединяющие <tex>v_{j}</tex> c вынимаемыми из стека вершинами пока это возможно. Проверку на возможность построения диагонали <tex>v_{j}v_{k}</tex>, где <tex>v_{k}</tex> — текущая верхняя вершина стека, можно осуществлять посредством изучения взаимного расположения предыдущей вершины, вынутой из <tex>S</tex>, относительно <tex>v_{j}v_{k}</tex>. Когда мы достигнем вершины  <tex>v_{k}</tex>, до которой невозможно провести диагональ, положим предыдущую вершину  <tex>v_{k-1}</tex> обратно в стек. Вершина <tex>v_{k-1}</tex> является либо последней, до которой было возможно провести диагональ, либо, если ни одной диагонали из  <tex>v_{j}</tex> провести не удалось, — соседом <tex>v_{j}</tex>. Далее положим <tex>v_{j}</tex> в стек. Опять же инвариант непротриангулированной части <tex>P</tex> сохраняется: одна сторона воронки ограничена частью стороны многоугольника, а другая цепью невыпуклых вершин.
+
Первый раз A* делает итерации на графе <tex>G</tex> до тех пор, пока не будет найдена вершина <tex>s_6</tex>. Часть графа <tex>G</tex>, которая уже была рассмотрена иллиюстрируется на рисунке 8. Ребра, изображенные сплошными линиями, обозначают ребра дерева, в то время, как все остальные - запасные ребра. Они будет храниться в кучах <tex>H_{in}</tex>, показанных на рисунке 9. Номера, присвоенные узлах кучи, соответствуют <tex>\delta</tex>-значениям. На этом этапе поиска A* приостановлен и <tex>P(G)</tex> построен. Первоначально, только назначенный корень <tex>R</tex> явно доступен в <tex>P(G)</tex>. Инициализируется алгоритм Дейкстры. Это означает, что узел <tex>R</tex> добавляется в поискую очередь Дейкстры. Планировщику требуется доступ к successors К для того, чтобы решить следует ли возобновлять Дейкстру или A*. На данном этапе должна быть построена деревянная куча <tex>H_{T}(s_6)</tex>. Куча <tex>H_{T}(s_4)</tex> требуется для построения <tex>H_{T}(s_6)</tex>. Следовательно, строются деревянные кучи <tex>H_{T}(s_6)</tex>, <tex>H_{T}(s_4)</tex>, <tex>H_{T}(s_2)</tex> и <tex>H_{T}(s_0)</tex>. Результат показан на рисунке 10, где сплошные линии представляют кучные ребра и пунктирные линии показывают кросс-ребра. Во избежание путаницы на рисунке некоторые из ребер не полностью изображены. Мы указываем каждое из них, используя короткую стрелку с конретной целью.
  
=== Псевдокод ===
+
После построения, как показано 10, планировщик проверяет только ребенка <tex>(s_4, s_2)</tex> узла <tex>R</tex> на предмет того, что <tex>g(s_6) + d(s_4,s_2) <= f(s_1)</tex>. Отметим, что <tex>s_1</tex> является головой поисковой очереди A*. Значение <tex>d(s_4,s_2)</tex> равно 2, т.е. <tex>g(s_6) + d(s_4,s_2) = 7 + 2 = 9 = f(s_1)</tex>. Следовательно, планировщик позволяет Дейкстре раскрыть <tex>R</tex> и вставить <tex>(s_4,s_2)</tex> в поисковую очередь. При раскрытии <tex>R</tex> находится первый путь из ответа. Он строится из пути <tex>P(G)</tex>, содержащего единственный узел <tex>R</tex>. Этот путь приводит к пустой последовательности запасных ребер. Напомним, что пустая последовательность запасных ребер соответствует пути из <tex>s_0</tex> в <tex>s_6</tex> в дереве поиска, а именно <tex>s_0s_2s_4s_6</tex> длиной 7. Затем поиск Дейкстры приостанавливается, потому что для successor-ов узла <tex>(s_4,s_2)</tex> не выполняется условие <tex>g(s_6)+d(n)<=f(s_1)</tex>. Следовательно, возобновляется A*.
Как ранее уже было отмечено, задаём <tex>P</tex> в виде рёберного списка c двойными связями <tex>D</tex>.
 
TriangulateMonotonePolygon(P)
 
    vertex [n] V = new vertex(P); // массив вершин <tex>P</tex>, отсортированный по y-координате в порядке убывания.
 
    stack S = new stack();
 
    S.push(V[1]);
 
    S.push(V[2]);
 
    for j <tex>\leftarrow</tex> 3 to n - 1
 
      if (V[j] = S.peek())
 
          while (S <tex>\neq  \varnothing </tex>)
 
            if (S.size() <tex>\neq</tex> 1)
 
                Insert edge(V[j], S.peek()) in D
 
            S.pop()
 
          S.push(V[j-1])
 
          S.push(V[j]);
 
      else
 
          vertex last <tex>\leftarrow</tex> S.peek();
 
          S.pop();
 
          while (IsValidDiagonal(edge(V[j], S.peek()), last)) //проверка возможности построения
 
                                                              //диагонали — предикат "левый поворот"
 
            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 </tex>)
 
      if (S.size() <tex>\neq</tex> 1)
 
          Insert edge(V[j], S.peek()) in D
 
      S.pop()
 
=== Корректность ===
 
* Все построенные диагонали попарно не пересекаются. Это гарантируется тем, что при каждом просмотре определённой вершины рассматривается только та часть <tex>P'</tex> многоугольника <tex>P</tex>, которая не была протриангулирована, следовательно внутри этой области по определению не может лежать ни одной из уже построенных диагоналей. Несложно заметить, что в стеке <tex>S</tex> на каждой итерации главного цикла хранятся вершины, которые принадлежат именно <tex>P'</tex> и лежат выше рассматриваемой вершины.
 
* Количество построенных диагоналей всегда будет <tex>n-3</tex>, поэтому непротриангулированных частей в многоугольнике не останется.
 
=== Оценка работы ===
 
Построение массива вершин требует линейное время и занимает линейную память. Главный цикл ''for'' выполняется <tex>n-3</tex> раза. Каждая его итерация может потребовать линейное время. Однако заметим, что на каждой итерации главного цикла в стек кладутся максимум две вершины, следовательно общее число выполнения операции ''push'', включая первые две вершины, положенные в начале алгоритма, ограничено <tex>2n-4</tex>. Количество операций ''pop'' за время работы алгоритма не превысит количества операций ''push''. Отсюда общее время работы цикла ''for'' <tex>\mathcal{O}(n)</tex>. В итоге общее время работы <tex>\mathcal{O}(n)</tex>.
 
=== Общая оценка ===
 
Разбиение многоугольника на монотонные части занимает <tex>\mathcal{O}(n \log n)</tex> времени и <tex>\mathcal{O}(n)</tex> памяти. Триангуляция каждой из частей занимает линейную память и время. Учитывая то, что суммарное количество вершин во всех частях <tex>\mathcal{O}(n)</tex>, триангуляция всех частей займёт <tex>\mathcal{O}(n)</tex> по времени и по памяти.
 
  
В итоге общая оценка составляет <tex>\mathcal{O}(n \log n)</tex> по времени и <tex>\mathcal{O}(n)</tex> по памяти.
+
Мы предполагаем, что условие раскрытия определено как раскрытие одной вершины для того, чтобы пример был простым и иллюстративным. Поэтому A* раскрывает <tex>s_1</tex> и останавливается. Исследованная часть <tex>G</tex> на текущем этапе показана на рисунке 11. Результат раскрытия приведет к обнаружению 2 новых запасных ребер <tex>(s_1,s_2)</tex> и <tex>(s_1,s_6)</tex>, которые будут добавлены в <tex>H_{in}(s_2)</tex> и <tex>H_{in}(s_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.

Текущая версия на 13:39, 19 августа 2015

Также как и алгоритм Эппштейна, K* выполняет поиск пути на графе [math]G[/math] и использует граф путей [math]P(G)[/math]. Граф путей ищется с помощью алгоритма Дейкстры для того, чтобы вычислить пути [math]s-t[/math] в виде последовательности запасных путей. Общий принцип работы алгоритма K* следующий:

1) K* применяет A* на графе [math]G[/math] вместо обратного алгоритма Дейкстры, который используется алгоритмом Эппштейна.
2) Мы запускаем A* на [math]G[/math] и Дейкстру на [math]P(G)[/math] в поочередном порядке, который позволяет Дейкстре вычислить требуемые пути до заверешения полного поиска алгоритма A* на графе [math]G[/math] .

4.1 Поиск A* на G

K* применяет A* к входному графу [math]G[/math] для того, чтобы построить дерево поиска [math]T[/math]. Заметим, что A*, также как и алгоритм Дейкстры, строит дерево поиска в процессе нахождения кратчайшего пути [math]s-t[/math] . Эти деревья формируются с помощью ссылок на родительские узлы, которые хранятся в том время, как A* производит итерации для того, чтобы восстановить путь [math]s-t[/math], когда вершина [math]t[/math] ещё не найдена. Запасные ребра, открытые в процессе поиска A* на графе G, немедленно добавляются в граф P(G), структура которого будет объясняться в разделе 4.3.

В K* A* применяется к графу [math]G[/math] в прямом направлении в отличие от алгоритма Эппштейна, из-за чего корнем дерева [math]T[/math] является вершина начальная [math]s[/math]. Это необходимо для того, чтобы была возможность работать c неявным описанием графа [math]G[/math] через функцию successor (функция, возвращающая список исходящих ребер из данной вершины). На протяжение статьи будем считать граф [math]G[/math] конечным, если не будет сказано иное. Заметим, что А* корректен на конечных графах. Будем следовать литературному соглашению, предполагая, что стоимость бесконечного пути неограниченна.

4.2 Стоимость объезда

Рисунок 3. Исходный граф, в котором сплошные линии представляют построенное A* дерево поиска [math]T[/math]. Пунктирные линии являются запасными ребрами.

Для ребра [math](u, v)[/math] стоимость объезда (англ. detour) [math]\delta(u, v)[/math] представляет стоимость ущерба (англ. disadvantage) из-за взятия ребра объезда [math](u,v)[/math] в сравнении с кратчайшим путем [math]s-t[/math] через [math]v[/math]. Ни длина кратчайшего пути [math]s-t[/math] через [math]v[/math], ни длина пути [math]s-t[/math], включающего запасные ребра [math](u, v)[/math] не известны, когда A* обнаруживает [math](u, v)[/math]. Обе длины могут быть оценены с помощью функции оценки [math]f[/math], которая использует эвристическую функцию [math]h[/math]. Пусть [math]f(v)[/math] будет [math]f[/math]-значением с соответствии с деревом поиска [math]T[/math] и [math]f_u(v)[/math] будет [math]f[/math]-значением в соответствии с родителем u, т.е. [math]f_u(v) = g(u) + c(u, v) + h(v)[/math]. Тогда [math]\delta(u, v)[/math] может быть определена так:

[math]\delta(u, v) = f_u(v) - f(v) = g(u) + c(u, v) + h(v) - g(v) - h(v) = g(u) + c(u, v) - g(v)[/math]

Заметим, что [math]\delta(u, v)[/math] дает точную объездную метрику, поскольку оценочное [math]h[/math]-значение не появляется в определении функции [math]\delta(u, v)[/math].

4.3 Структура графа путей

Структура графа путей [math]P(G)[/math] довольно сложная. В принципе, [math]P(G)[/math] будет ориентированным графом, вершины которого соответствуют ребрам в исходном графе [math]G[/math]. Он будет организован как коллекция взаимосвязанных куч (англ. heap). 2 бинарные кучи минимума присвоены к каждой вершине [math]v[/math] в графе [math]G[/math], которые называются входящей кучей (англ. incoming heap)[math]H_{in}(v)[/math] и деревянной кучей (англ. tree heap) [math]H_{T}(v)[/math]. Эти кучи являются базисом [math]P(G)[/math]. Как мы покажем далее, использование этих куч также играет главную роль в поддержании асимптотической сложности K*, также как в EA и LVEA.

Входящая куча [math]H_{in}(v)[/math] содержит узлы для каждого запасного ребра к вершине [math]v[/math], которые до сих пор были обнаружены A*. Узлы [math]H_{in}(v)[/math] будут упорядочены в соответствии с [math]\delta[/math]-значением соответствующих переходов. Узел владеющий ребром с минимальной стоимостью ущерба будет расположен на вершине кучи. Мы ограничим структуру кучи [math]H_{in}(v)[/math] таким образом, что её корень в отличие от остальных узлов, будет иметь не более 1 ребенка. Обозначим его [math]root_{in}(v)[/math].

Пример 4. Рисунок 4 иллюстрирует входящие кучи графа из рисунка 3. Цифры рядом с узлами кучи соответствуют [math]\delta[/math]-значениям.

Рисунок 4. Входящие кучи [math]H_{in}(s_i)[/math], полученные из графа, показанного на рисунке 3.

Деревянная куча [math]H_{T}(v)[/math] для произвольной вершины [math]v[/math] строится следующим образом. Если [math]v[/math] - стартовая вершина, т.е. [math]v = s[/math], то [math]H_{T}(v)[/math] будет изначально пустой кучей. Затем в неё будет добавлен [math]root_{in}(s)[/math], если [math]H_{in}(s)[/math] не пустая. Если [math]v[/math] не стартовая вершина, то пусть вершина [math]u[/math] будет родителем вершины [math]v[/math] в дереве поиска [math]T[/math]. Мы можем представить, что [math]H_{T}(v)[/math] конструируется как копия [math]H_{T}(u)[/math], в которую добавлен [math]root_{in}(v)[/math]. Если [math]H_{in}(v)[/math] пустая, то [math]H_{T}(v)[/math] идентична [math]H_{T}(u)[/math]. Однако, для экономии памяти мы создаем только дешевую копию [math]H_{T}(u)[/math]. Это осуществляется через создание копий только тех узлов кучи, которые лежат на обновленном пути в [math]H_{T}(u)[/math]. Оставшаяся часть [math]H_{T}(u)[/math] не копируется. Другими словами, [math]root_{in}(v)[/math] вставляется в [math]H_{T}(u)[/math] неразрушающим путем так, что структура [math]H_{T}(u)[/math] сохраняется. В куче [math]H_{T}(v)[/math] к [math]root_{in}(v)[/math] могут быть присоединены 1 или 2 ребенка. К тому же, [math]root_{in}(v)[/math] хранит только 1 собственного ребенка из [math]H_{in}(v)[/math]. Мы обозначим корень [math]H_{T}(v)[/math] как [math]R(v)[/math].

Рисунок 5. Деревянные кучи [math]H_{T}(s_i)[/math], полученные из графа, показанного на рисунке 3.

Назовем ребра, которые берут начало из входящих или деревянных куч, кучными ребрами (англ. heap edges). Сформулируем следующую лемму.

Лемма (1):
Все узлы, достижимые из [math]R(v)[/math] по кучным ребрам, для каждой вершины [math]v[/math] формируют тернарную кучу, упорядоченную в соответствии с [math]\delta[/math]-значением. Мы назовем такую кучу графовой кучей (англ. graph heap) вершины [math]v[/math] и обозначим её как [math]H_{G}(v)[/math].
Доказательство:
[math]\triangleright[/math]
Те узлы, которые находятся в [math]H_{T}(v)[/math] или во входящей куче, на которую ссылается узел из [math]H_{T}(v)[/math], достижимы по кучным ребрам из [math]R(v)[/math]. Деревянная куча [math]H_{T}(v)[/math] формируется через добавление корней входящих куч всех вершин, лежащих на пути из стартовой вершины [math]s[/math] до [math]v[/math] в бинарной куче. Каждый из этих корней имеет максимум 3 детей: до 2 в [math]H_{T}(v)[/math] и дополнительно единственного из входящей кучи. Любой другой узел, живущий во входящей куче имеет не больше 2 детей. Напомним, что каждая входящая куча - это бинарная куча с ограничением, что корень имеет единственного ребенка. Древовидная структура [math]H_{G}(v)[/math] непосредственный результат древовидных структур [math]H_{T}(v)[/math] и входящих куч. Более того, кучная характеристика деревянной кучи обеспечивает упорядочивание в соответствии с [math]\delta[/math]-значением по ребрам из [math]H_{T}(v)[/math], а кучная характеристика входящих куч - по всем ребрам из [math]H_{in}[/math]. Все это приводит к тому, что [math]H_{G}(v)[/math] - тернарная куча, упорядоченная в соответствии с [math]\delta[/math]-значением.
[math]\triangleleft[/math]

Финальная структура [math]P(G)[/math] получется из входящих и деревянных куч следующим образом. К каждому узлу [math]n[/math] из [math]P(G)[/math], несущему ребро [math](u,v)[/math], мы присоединим указатель, ссылающийся на [math]R(u)[/math], который является корневым узлом [math]H_{T}(u)[/math]. Мы назовем такие указатели кросс-ребрами (англ. cross edges), в то время как указатели, возникающие из куч названы кучными ребрами, как упоминалось раньше. Более того, мы добавим специальный узел [math]\mathrm{R}[/math] в [math]P(G)[/math] с одним выходящим кросс-ребром к [math]R(t)[/math].

Более того, мы определим весовую функцию [math]\Delta[/math] на ребрах из [math]P(G)[/math]. Пусть [math](n,n')[/math] обозначает ребро в [math]P(G)[/math], и пусть [math]e[/math] и [math]e'[/math] обозначают ребра из [math]G[/math], соответствующие узлам [math]n[/math] и [math]n'[/math]. Тогда определим [math]\Delta(n,n')[/math] следующим образом:

[math]
 \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}
 [/math]

Лемма 1 подразумевает, что куча упорядоченная в соответствии с [math]\delta[/math]-значанием поддерживается для любого кучного ребра из [math]P(G)[/math]. Эта упорядочивание кучи подразумевает, что [math]\Delta(n,n')[/math] неотрицательна для любого кучного ребра [math](n,n')[/math]. Следовательно, [math]\Delta[/math] также неотрицательна, т.е. [math]\Delta(n,n') \gt = 0[/math] для любого ребра [math](n,n')[/math] в [math]P(G)[/math]. Стоимость пути [math]\sigma[/math], т.е. [math]C_{P(G)}(\sigma)[/math] равна [math]\sum_{e \in \sigma}\Delta(e)[/math].

Пример 6.

В оставшейся части этого раздела мы проиллюстрируем особенности структуры графа путей, которые актуальны для нахождения кратчайших путей [math]s-t[/math].

Первое наблюдение в том, что [math]P(G)[/math] ориентированный взвешенный граф. Каждый узел в [math]P(G)[/math] несет запасное ребро из G. Использование бинарных куч в конструкции [math]P(G)[/math] извлекает выгоду из следующих 2 свойств. Во-первых, произвольный узел в [math]P(G)[/math] имеет не более 4 выходящих ребер. Одним из ребер будет точно кросс-ребро в то время, как оставшимися будут кучные ребра. Во-вторых, функция веса [math]\Delta[/math] неотрицательна. Как станет ясно в разделе 5, эти свойства необходимы для доказательства правильности и определения сложности K*.

Второе наблюдение заключается в существовании соответствия один-к-одному между путей [math]s-t[/math] в [math]G[/math] и путей в [math]Р(G)[/math], которые начинаются в [math]\mathrm{R}[/math].

...

Лемма (2):
Пусть [math]n[/math] будет узлом графовой кучи [math]H_{G}(w)[/math] для какой-нибудь вершины [math]w[/math]. Пусть [math](u,v)[/math] будет ребром связанным с [math]n[/math]. Тогда существует путь в дереве поиска [math]T[/math] из [math]v[/math] в [math]w[/math].
Доказательство:
[math]\triangleright[/math]
...
[math]\triangleleft[/math]

4.4 Алгоритмическая структура K*

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

Data: A graph given by its start vertex s ∈ V and its successor function succ and a natural number k Result: A list R containing k sidetrack edge sequences representing k solution paths

  1  [math]open_D[/math] ← пустая приоритетная очередь
  2  [math]closed_D[/math] ← пустая хеш-таблица
  3  [math]R[/math] ← пустой список
  4  [math]P(G)[/math] ← пустой граф путей
  5  Выполняем A* на графе [math]G[/math] пока [math]t[/math] не будет выбрана для раскрытия
  6  Если вершина [math]t[/math] не была достигнута, то выходим без ответа
  7  Кладем [math]\mathrm{R}[/math] в очередь [math]open_D[/math]
  8  while A queue or open D is not empty:
  9     if A queue is not empty:
  10       if очередь [math]open_D[/math] не пуста:
  11          Let u be the head of the search queue of A ∗ and n the head of [math]open_D[/math]
  12          [math]d = max\{ d(n) + \Delta(n, n') | n' \in succ(n) \}[/math]
  13          if [math]g(t) + d \lt = f[/math] (u) then переходим на строку 17.
  14       Возобновляем A* для того, чтобы исследовать более большую часть графа [math]G[/math]
  15       Обновляем [math]P(G)[/math] and bring Dijkstra’s search into a consistent status
  16       Переходим на строку 8
  17    if очередь [math]open_D[/math] пуста: переходим на строку 8.
  18    Remove from [math]open_D[/math] and place on [math]closed_D[/math] the node n with the minimal d-value.
  19    foreach [math]n'[/math] referred by n in P(G):
  20       [math]d(n') = d(n) + \Delta(n, n')[/math]
  21       Attach to [math]n'[/math] a parent link referring to [math]n[/math].
  22       Insert n 0 into [math]open_D[/math]
  23    Пусть [math]\sigma[/math] будет путем в [math]P(G)[/math], через который узел n был достигнут.
  24    Добавим [math]seq(\sigma)[/math] в конец списка [math]R[/math].
  25    if [math]|R| = k[/math]: переходим на строку 26.
  26 Return R and exit.

Алгоритм 1 содержит псевдокод K*. Код с 8 по 25 строчку образует главный цикл K*. Цикл завершается, когда очереди обоих алгоритмов А* и Дейкстры пусты. До 8 строчки выполняет некоторые подготовительные вещи. После инициализации, А* запускает на 5 строчке пока вершина [math]t[/math] не будет выбрана им для рассмотрения, в этом случае кратчайший путь [math]s-t[/math] будет найден. Если [math]t[/math] не достигнута, то алгоритм завершается без ответа. Отметим, что он не завершится на бесконечных графах. Иначе, алгоритм добавляет специальную вершину [math]R[/math], которая назначена корнем [math]P(G)[/math], в поисковую очередь алгоритма Дейкстры. Затем, K* входит в главный цикл.

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

Строки 18-22 представляют обычный шаг рассмотрения узла алгоритмом Дейкстры. Отметим, что когда successor-узел [math]n'[/math] сгенерирован, K* не проверяет был ли [math]n'[/math] уже посещен до этого. Другими словами, каждый раз, когда узел генерируется, он рассматривает как новый. Эта стратегия обоснована на наблюдении, что путь s-t может содержать одно и то же ребро несколько раз. Строка 24 добавляет следующий путь [math]s-t[/math] в результирующее множество R. Это делается путем конструирования последовательности запасных ребер [math]seq(\sigma)[/math] из пути [math]\sigma[/math], через которые Дейкстра достигла узла [math]n[/math], который был только что рассмотрен. Алгоритм завершается, когда в результирующее множество добавлено [math]k[/math] последовательностей запасных ребер (строка 25).

4.5 Взаимосвязь алгоритмов Дейкстры и A*

Тот факт, что оба алгоритма A* и Дейкстры делят между собой граф путей [math]P(G)[/math], вызывает обеспокоенность в отношении правильности работы Дейкстры на [math]P(G)[/math]. Возобновление A* приводит к изменениям в структуре [math]P(G)[/math]. Таким образом, после возобновления A*, мы обновляем [math]P(G)[/math] и проверяет статус поиска Дейкстры (строка 15). В основном, A* может добавить новые узлы, менять [math]\delta[/math]-значения существующих узлов или даже удалять узлы. A* может также существенно изменять дерево поиска [math]T[/math], которое будет в худшем случае разрушать структуру все деревянных куч [math]H_{T}[/math]. Эти изменения могут приводить к глобальной реструктуризации или даже перестроению [math]P(G)[/math] с нуля. В худшем случае это может сделать предыдущие поиски Дейкстры на [math]P(G)[/math] бесполезными таким образом, что нам придется перезапускать алгоритм Дейкстры с нуля.

Если использованная эвристическая оценка допустимая, то наше положение лучше. Нам по-прежнему может понадобится перестроение [math]P(G)[/math], но мы покажем, что это перестроение не мешает корректности поиска Дейкстры на [math]P(G)[/math]. Другими словами, мы не теряем результаты, до сих пор полученные поиском Дейкстры.

В случае монотонной эвристической оценки мы даже не нуждаемся в восстановлении или перестроении [math]P(G)[/math]. Если [math]h[/math] монотонная, то дерево поиска A* является деревом кратчайшего пути для всех раскрытых вершин. Следовательно, g-значения раскрытых вершин не меняются. Это означает, что [math]\delta[/math]-значения для внутренних ребер никогда не изменятся. Ребра дерева раскрытых вершин не изменятся также. Следовательно, обновление [math]\delta[/math]-значений, heaping-up, heaping-down (операции в кучах) или удаление узлов не влекут за собой каких-либо изменений в [math]P(G)[/math]. Только добавление новых узлов приводит к изменениям в [math]P(G)[/math]. Следовательно, восстановление или глобальное перестроение не требуется в данном случае.

В оставшейся части этого раздела, мы сначала покажем, что корректность поиска Дейкстры на [math]P(G)[/math] поддерживается в случае допустимой эвристической оценки. После этого мы покажем, что изменения в [math]P(G)[/math] могут помешать завершенности поиска Дейкстры независимо от того, является ли эвристика допустимой или даже монотонной. Следовательно, мы предложим механизм для её поддержания.

Мы фокусируемся дальше на корректности поиска Дейкстры на [math]P(G)[/math] в случае допустимой эвристической оценки. Сначала, мы заявляем, что если [math]h[/math] допустимая, то узлы исследованной части [math]P(G)[/math] не поменяют свои [math]\delta[/math]-значения.

Лемма (6):
Пусть [math]n[/math] будет произвольным узлов в [math]P(G)[/math] и пусть [math](u,v)[/math] будет ребром, связанным с [math]n[/math]. Если [math]h[/math] допустимая функция, то значение [math]\delta(u, v)[/math] никогда не изменится после того, как [math]n[/math] будет рассмотрен алгоритмом Дейкстры.
Доказательство:
[math]\triangleright[/math]
...
[math]\triangleleft[/math]

Из леммы 6 мы может вывести следующее следствие.

Лемма (следствие 3):
Пусть [math]n[/math] будет произвольным узлом в [math]P(G)[/math]. Если [math]h[/math] допустимая функция, то [math]n[/math] никогда не будет удален из [math]P(G)[/math] после того, как [math]n[/math] был рассмотрен алгоритмом Дейкстры.
Доказательство:
[math]\triangleright[/math]
...
[math]\triangleleft[/math]

Более того, мы докажем, что структура исследованной части [math]P(G)[/math] не изменится.

Лемма (7):
Пусть [math]n[/math] будет произвольным узлов в [math]P(G)[/math]. Если [math]h[/math] допустимая функция, то [math]n[/math] никогда не изменит свою позицию после того, как он был рассмотрен алгоритмом Дейкстры.
Доказательство:
[math]\triangleright[/math]
...
[math]\triangleleft[/math]


Леммы 6 и 7 обеспечивают, что изменения в [math]P(G)[/math], которые индуцируются A*, не влияют на часть [math]P(G)[/math], которую алгоритм Дейкстры уже исследовал. Это гарантирует корректность поиска Дейкстры на [math]P(G)[/math], если используемая эвристика допустимая. Таким образом, каждый путь, который предоставляет алгоритм Дейкстры корректен и его длина действительна. Однако, это не обеспечивает завершенность поиска Дейкстры на [math]P(G)[/math].

Возможно, что узел [math]n'[/math] присоединяется к другом узлу n как ребенок, после раскрытия узла [math]n[/math]. В этом случае братья [math]n'[/math] будут рассотрены до того, как [math]n'[/math] станет ребенком n. Поэтому мы должны рассмотреть то, что было упущено во время поиска в связи с отсутствием [math]n'[/math]. Мы добиваемся этого путем применения строк 20-22 к [math]n'[/math] для каждого раскрытого направленного predecessor-а узла [math]n'[/math]. Если [math]n'[/math] ещё не выполняет условие планирования, A* будет неоднократно возобновляться пока механизм планирования не допустит алгоритму Дейкстры положить [math]n'[/math] в поисковую очередь. Заметим, что таким образом не требуется каких-либо дополнительных усилий во время типичного поиска Дейкстры.

Мы может быть уверены, что нерассмотренные узлы не будут принудительно опущены после применения операции heaping-up к [math]n'[/math]. Иначе, мы могли бы иметь узел [math]n''[/math], который являлся бы ребенком n и впоследствии был бы заменен узлом [math]n'[/math]. Заметим, что [math]n''[/math] должен быть рассмотрен, поскольку [math]n'[/math] был раскрыт. Однако, это противоречение к лемме 7, которая гарантирует, что этого не произойдет.

Более того, следующее следствие гарантирует, что наилучшее [math]d(n')[/math] не лучше, чем [math]d[/math]-значение любой рассмотренной вершины, в частности, раскрытой вершины. Это означает, что мы не упустим возможность раскрыть [math]n'[/math].

Лемма (следствие 3):
Пусть [math]n[/math] будет узлом в [math]P(G)[/math], который был раскрыт Дейкстрой. Кроме того, пусть [math]m[/math] будет узлом, который заново добавляется в [math]P(G)[/math] или его позиция изменена, после того как [math]n[/math] был раскрыт. Если [math]h[/math] допустимая, тогда выполяется следующее: [math]C_{P(G)}(R,m) \gt = d(n)[/math]
Доказательство:
[math]\triangleright[/math]
...
[math]\triangleleft[/math]

4.6 Пример

Мы проиллюстрируем работу алгоритма K* следующим примером. Мы будем рассматривать ориентированный взвешанный граф G на рисунке 7. Стартовой вершиной будет называться [math]s_0[/math] и конечной вершиной - [math]s_6[/math]. Нас интересует поиск 9 лучших путей из [math]s_0[/math] в [math]s_6[/math]. Для достижения этой цели мы применим алгоритм K* к [math]G[/math]. Предположим, что эвристическая оценка существует. Значения эвристики даны в пометках c [math]h(s_0)[/math] по [math]h(s_6)[/math] на рисунке 7. Легко заметить, что эвристическая функция допустима.

Первый раз A* делает итерации на графе [math]G[/math] до тех пор, пока не будет найдена вершина [math]s_6[/math]. Часть графа [math]G[/math], которая уже была рассмотрена иллиюстрируется на рисунке 8. Ребра, изображенные сплошными линиями, обозначают ребра дерева, в то время, как все остальные - запасные ребра. Они будет храниться в кучах [math]H_{in}[/math], показанных на рисунке 9. Номера, присвоенные узлах кучи, соответствуют [math]\delta[/math]-значениям. На этом этапе поиска A* приостановлен и [math]P(G)[/math] построен. Первоначально, только назначенный корень [math]R[/math] явно доступен в [math]P(G)[/math]. Инициализируется алгоритм Дейкстры. Это означает, что узел [math]R[/math] добавляется в поискую очередь Дейкстры. Планировщику требуется доступ к successors К для того, чтобы решить следует ли возобновлять Дейкстру или A*. На данном этапе должна быть построена деревянная куча [math]H_{T}(s_6)[/math]. Куча [math]H_{T}(s_4)[/math] требуется для построения [math]H_{T}(s_6)[/math]. Следовательно, строются деревянные кучи [math]H_{T}(s_6)[/math], [math]H_{T}(s_4)[/math], [math]H_{T}(s_2)[/math] и [math]H_{T}(s_0)[/math]. Результат показан на рисунке 10, где сплошные линии представляют кучные ребра и пунктирные линии показывают кросс-ребра. Во избежание путаницы на рисунке некоторые из ребер не полностью изображены. Мы указываем каждое из них, используя короткую стрелку с конретной целью.

После построения, как показано 10, планировщик проверяет только ребенка [math](s_4, s_2)[/math] узла [math]R[/math] на предмет того, что [math]g(s_6) + d(s_4,s_2) \lt = f(s_1)[/math]. Отметим, что [math]s_1[/math] является головой поисковой очереди A*. Значение [math]d(s_4,s_2)[/math] равно 2, т.е. [math]g(s_6) + d(s_4,s_2) = 7 + 2 = 9 = f(s_1)[/math]. Следовательно, планировщик позволяет Дейкстре раскрыть [math]R[/math] и вставить [math](s_4,s_2)[/math] в поисковую очередь. При раскрытии [math]R[/math] находится первый путь из ответа. Он строится из пути [math]P(G)[/math], содержащего единственный узел [math]R[/math]. Этот путь приводит к пустой последовательности запасных ребер. Напомним, что пустая последовательность запасных ребер соответствует пути из [math]s_0[/math] в [math]s_6[/math] в дереве поиска, а именно [math]s_0s_2s_4s_6[/math] длиной 7. Затем поиск Дейкстры приостанавливается, потому что для successor-ов узла [math](s_4,s_2)[/math] не выполняется условие [math]g(s_6)+d(n)\lt =f(s_1)[/math]. Следовательно, возобновляется A*.

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