Изменения

{{nohate}}Также как и алгоритм Эппштейна, K* выполняет поиск пути на графе <tex>G</tex> и использует граф путей <tex>P(G)</tex>. Граф путей ищется с помощью алгоритма Дейкстры для того, чтобы вычислить пути <tex>s-t</tex> в виде последовательности запасных путей. Общий принцип работы алгоритма K* следующий:  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> конечным, если не будет сказано иное. Заметим, что А* корректен на конечных графах. Будем следовать литературному соглашению, предполагая, что стоимость бесконечного пути неограниченна. |definition== 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|definition='''Триангуляция Делоне множества точекРисунок 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.]]

|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>.

По лемме 1 очевидноБолее того, что внутри окружностеймы определим весовую функцию <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>

== Критерий Делоне для рёбер =={{Определение|definition='''Критерий Делоне Лемма 1 подразумевает, что куча упорядоченная в соответствии с <tex>\delta</tex>-значанием поддерживается для любого кучного ребра''': на ребре можно построить такую окружностьиз <tex>P(G)</tex>. Эта упорядочивание кучи подразумевает, что внутри неё не будет лежать никаких точек.}}{{Лемма|about=2|statement=Триангуляции Делоне принадлежат те и только те рёбра <tex>\Delta(с поправкой на точкиn, лежащие на одной окружностиn')</tex> неотрицательна для любого кучного ребра <tex>(n, которые удовлетворяют критерию Делонеn')</tex>.|proof=[[Файл:Good edges.png|400px|thumb|right|Для рёбер AB и CD выполняется критерий ДелонеСледовательно, на них построены окружности]]То<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.'''

ПредположимВ оставшейся части этого раздела мы проиллюстрируем особенности структуры графа путей, что это ребро (назовём его которые актуальны для нахождения кратчайших путей <tex>ABs-t</tex>) не принадлежит триангуляции Делоне. Тогда существует пересекающее его ребро <tex>CD</tex>, принадлежащее триангуляции. Рассмотрим четырёхугольник <tex>ACBD</tex>. Точки <tex>C</tex> и <tex>D</tex> лежат вне окружности, построенной на <tex>AB</tex> как на хорде, поэтому сумма углов <tex>C</tex> и <tex>D</tex> меньше 180°. Аналогичным образом доказывается, что сумма углов <tex>A</tex> и <tex>B</tex> тоже меньше 180°. Значит, сумма углов четырёхугольника <tex>ACBD</tex> меньше 360°, что невозможно. Противоречие. Значит, ребро <tex>AB</tex> принадлежит триангуляции Делоне.}}

== Локальный критерий Делоне =={{Определение|definition='''Локальный критерий Делоне''': для пары треугольников, которым принадлежит это ребро, выполняется критерий Делоне (то есть вершина, противолежащая ребру Первое наблюдение в одном треугольнике, не лежит в окружности, описанной вокруг другого, и наоборот).}}Будем называть '''хорошими''' те рёбра, для которых выполняется локальный критерий Делоне.{{Лемма|about=3|id=fliplemma|statement=Из двух рёбер, которые можно провести для пары треугольников, как минимум одно хорошее.|proof=[[Файл:Bad edges.png|400px|thumb|right|Рёбра AB и BC плохие]]Предположимтом, что это не так, то есть оба ребра (назовём их <tex>AB</tex> и <tex>CD</tex>P(G) плохие. Рассмотрим четырёхугольник <tex>ACBD</tex> и окружность, описанную вокруг треугольника <tex>ABC</tex>ориентированный взвешенный граф. Точка Каждый узел в <tex>DP(G)</tex> лежит внутри этой окружности, значит, сумма углов <tex>C</tex> и <tex>D</tex> больше 180°несет запасное ребро из G. Аналогично доказывается, что сумма углов Использование бинарных куч в конструкции <tex>AP(G)</tex> и <tex>B</tex> больше 180°извлекает выгоду из следующих 2 свойств. ЗначитВо-первых, сумма углов четырёхугольника произвольный узел в <tex>ACBDP(G)</tex> больше 360°, что невозможно.}}{{Лемма|about=имеет не более 4|statement=Если для всех рёбер выполняется локальный критерий Делоне, то выполняется и глобальный критерий Делоневыходящих ребер.|proof=[[Файл:Bad triangle.png|400px|thumb|right|Все рёбра треугольника хорошие, но описанная окружность содержит точки]]Предположим, что это не так, Одним из ребер будет точно кросс-ребро в то есть все рёбра хорошиевремя, но существуют треугольники, описанная окружность которых содержат какие-либо точки триангуляциикак оставшимися будут кучные ребра. Возьмём какуюВо-либо конфликтную точку вторых, функция веса <tex>E\Delta</tex>неотрицательна. Рассмотрим такой треугольник <tex>ABC</tex> из тех, Как станет ясно в описанную окружность которых попадает <tex>E</tex>разделе 5, что угол <tex>BEC</tex> максимален, если <tex>BC</tex> — ближайшая к точке <tex>E</tex> сторона. Пусть треугольник <tex>BDC</tex> — смежный с <tex>ABC</tex>эти свойства необходимы для доказательства правильности и определения сложности K*.

Докажем, что точка Второе наблюдение заключается в существовании соответствия один-к-одному между путей <tex>Es-t</tex> лежит в окружности, описанной вокруг <tex>BDC</tex>. Предположим, что это не так. Посмотрим на окружность, описанную вокруг треугольника <tex>ABC</tex>: <tex>\angle BAC + \angle BEC > 180^\circG</tex> и <tex>\angle BAC + \angle BDC < 180^\circ</tex>. Если точка <tex>E</tex> не лежит путей в окружности, описанной вокруг треугольника <tex>BDCР(G)</tex>, то которые начинаются в <tex>\angle BEC < \angle BDCmathrm{R}</tex>, что противоречит предыдущим двум неравенствам.

Очевидно, что угол <tex>BED</tex> больше, чем угол <tex>BEC</tex>. При этом точка <tex>E</tex> лежит в окружности, описанной вокруг <tex>BDC</tex>. Значит, при выборе треугольника нужно было взять не <tex>ABC</tex>, а <tex>BDC</tex>. Противоречие.}}

== Динамическая триангуляция =={{ОпределениеЛемма|definitionabout=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=.. Операция замены этой диагонали на другую называется '''flip''' ('''флип''').

Проведём через какой-нибудь == 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>, лежит ниже этой плоскости по которому Дейкстра достигла этого узла является решением. Путь <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> кратчайших путей.

После флипа станет выполняться локальный критерий Делоне, то есть тело станет включать в себя тетраэдр. Поэтому после флипа плохого ребра объём тела увеличится на объём этого тетраэдра.}}{{Лемма|about=6|statement=Флипами можно достичь хорошей триангуляции за конечное время.|proof=Всего триангуляций заданного множества точек конечное число, и среди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов параболоида и спроецированной на него триангуляции убывает ([[#volumelemma|по лемме 5]]). Эта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, требуемых для достижения триангуляции Делоне, тоже конечно.}}Data: A graph given by its start vertex s ∈ V and its successor function succ and a{{Леммаnatural number k|about=7|statement=Если в триангуляцию Делоне вставить точку в некоторый треугольник и соединить его вершины с этой точкой, то получившиеся рёбра будут хорошими.|id=newedgeslemma|proof=[[ФайлResult:Good A list R containing k sidetrack edge.png|400px|thumb|right|Точка V вставлена в треугольник ABC]]Предположим, точка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>VC</tex>. Проведём окружность, описывающую треугольник <tex>ABC</tex>. По критерию Делоне в ней не будет никаких точек триангуляции. На ребре <tex>VC</tex> можно построить окружность, изнутри касающуюся окружности, описанной вокруг треугольника. В ней тоже нет никаких точек. Значит, для <tex>VC</tex> выполняется критерий Делоне для рёбер, значит, ребро должно принадлежать триангуляции с добавленной точкой <tex>V</tex>, значит, оно хорошее.sequences representing k solution paths

Случай, когда точка вставляется 1 <tex>open_D</tex> ← пустая приоритетная очередь 2 <tex>closed_D</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> пуста:Insert переходим на строку 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 triangleP(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>.png|200px|thumb|left|Вставка 22 Insert n 0 into <tex>open_D</tex> 23 Пусть <tex>\sigma</tex> будет путем в треугольник]]<tex>P(G)</tex>, через который узел n был достигнут.[[Файл:Insert on edge 24 Добавим <tex>seq(\sigma)</tex> в конец списка <tex>R</tex>.png 25 '''if''' <tex>|200pxR|thumb|right|Вставка = 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* входит в главный цикл.

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).

Итого у нас появилось несколько новых рёбер== 4. Они все хорошие 5 Взаимосвязь алгоритмов Дейкстры и A* ==Тот факт, что оба алгоритма A* и Дейкстры делят между собой граф путей <tex>P(G)</tex>, вызывает обеспокоенность в отношении правильности работы Дейкстры на <tex>P(G)</tex>. Возобновление A* приводит к изменениям в структуре <tex>P(G)</tex>. Таким образом, после возобновления A*, мы обновляем <tex>P(G)</tex> и проверяет статус поиска Дейкстры (по [[#newedgeslemma|лемме 7]]строка 15). В основном, плохими A* может добавить новые узлы, менять <tex>\delta</tex>-значения существующих узлов или даже удалять узлы. A* может также существенно изменять дерево поиска <tex>T</tex>, которое будет в худшем случае разрушать структуру все деревянных куч <tex>H_{T}</tex>. Эти изменения могут оказаться только рёбра, противолежащие вставленной точкеприводить к глобальной реструктуризации или даже перестроению <tex>P(G)</tex> с нуля. Флипаем рёбраВ худшем случае это может сделать предыдущие поиски Дейкстры на <tex>P(G)</tex> бесполезными таким образом, пока триангуляция не станет хорошейчто нам придется перезапускать алгоритм Дейкстры с нуля.

==== Вставка точкиЕсли использованная эвристическая оценка допустимая, лежащей снаружи триангуляции ====Представимто наше положение лучше. Нам по-прежнему может понадобится перестроение <tex>P(G)</tex>, но мы покажем, что вне триангуляции — бесконечные треугольники, основания которых — рёбра выпуклой оболочки триангуляции, а противолежащая ребру вершина — это бесконечно удалённая точкаперестроение не мешает корректности поиска Дейкстры на <tex>P(G)</tex>. Тогда понятно, что вставка точкиДругими словами, мы не лежащей в триангуляциитеряем результаты, сведётся к вставке точки внутрь триангуляции, если мы научимся обрабатывать бесконечные фейсыдо сих пор полученные поиском Дейкстры.

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

Тогда проверка на тоВ оставшейся части этого раздела, является ли хорошим ребромы сначала покажем, инцидентное бесконечно удалённой точкечто корректность поиска Дейкстры на <tex>P(G)</tex> поддерживается в случае допустимой эвристической оценки. После этого мы покажем, упрощается:что изменения в <tex>\begin{vmatrix}a_x & a_y & a_x^2 + a_y^2 & 1 \\b_x & b_y & b_y^2 + b_y^2 & 1 \\c_x & c_y & c_x^2 + c_y^2 & 1 \\0 & 0 & 1 & 0\end{vmatrix} = \begin{vmatrix}a_x & a_y & 1 \\b_x & b_y & 1 \\c_x & c_y & 1\end{vmatrix}P(G)</tex>могут помешать завершенности поиска Дейкстры независимо от того, является ли эвристика допустимой или даже монотонной. Следовательно, то есть достаточно проверить поворот трёх остальных точек образованного двумя бесконечными треугольниками четырёхугольникамы предложим механизм для её поддержания.

Проверка, принадлежит ли точка бесконечному треугольнику, тоже проста: нужноМы фокусируемся дальше на корректности поиска Дейкстры на <tex>P(G)</tex> в случае допустимой эвристической оценки. Сначала, чтобы из точки было видно ребромы заявляем, противолежащее бесконечно удалённой точкечто если <tex>h</tex> допустимая, в бесконечном треугольнике. Это проверяется предикатом поворотато узлы исследованной части <tex>P(G)</tex> не поменяют свои <tex>\delta</tex>-значения.

|about=86|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> будет рассмотрен алгоритмом Дейкстры.|proof=[[Файл:Flip edges.png|400px|thumb|right|V — вставленная точка, ребро AC — плохое]]..Доказательство по индукции.}}

База. По [[#newedgeslemma|лемме 7]] изначально не будут флипаться новые рёбра, инцидентные точке, то есть плохими могут оказаться только рёбра, противолежащие точкеИз леммы 6 мы может вывести следующее следствие.

Переход. Рассмотрим, что произойдёт с противолежащим точке {{Лемма|about=следствие 3|statement=Пусть <tex>Vn</tex> ребром будет произвольным узлом в <tex>ACP(G)</tex> после флипа, если оно плохое. До вставки точки Если <tex>Vh</tex> для триангуляции выполнялся глобальный критерий Делонедопустимая функция, поэтому в окружности, описанной вокруг треугольника то <tex>ACDn</tex>, никогда не будет лежать никаких точек, кроме точки удален из <tex>VP(G)</tex>. Можно построить окружностьпосле того, касающуюся её изнутри в точке как <tex>D</tex> и проходящую через точку <tex>Vn</tex>был рассмотрен алгоритмом Дейкстры. В ней тоже не окажется никаких точек, так как она касается изнутри|proof=. Значит, для ребра <tex>VD</tex> выполняется критерий Делоне. Значит, после флипа ребро <tex>AC</tex> уже не будет флипаться. Так как для рёбер <tex>AV</tex> и <tex>CV</tex> выполняется критерий Делоне, то плохими после флипа могут стать только рёбра <tex>AD</tex> и <tex>CD</tex> — то есть рёбра, противолежащие точке <tex>V</tex>.

|about=97|statement=Средняя степень вершины после вставки её Пусть <tex>n</tex> будет произвольным узлов в триангуляцию Делоне равна <tex>OP(1G)</tex>. Если <tex>h</tex> допустимая функция, то <tex>n</tex> никогда не изменит свою позицию после того, как он был рассмотрен алгоритмом Дейкстры.|idproof=deglemma...}}  Леммы 6 и 7 обеспечивают, что изменения в <tex>P(G)</tex>, которые индуцируются A*, не влияют на часть <tex>P(G)</tex>, которую алгоритм Дейкстры уже исследовал. Это гарантирует корректность поиска Дейкстры на <tex>P(G)</tex>, если используемая эвристика допустимая. Таким образом, каждый путь, который предоставляет алгоритм Дейкстры корректен и его длина действительна. Однако, это не обеспечивает завершенность поиска Дейкстры на <tex>P(G)</tex>.|proof=ПредположимВозможно, что узел <tex>n'</tex> присоединяется к другом узлу n как ребенок, после раскрытия узла <tex>n</tex>. В этом случае братья <tex>n'</tex> будут рассотрены до того, как <tex>n'</tex> станет ребенком n. Поэтому мы вставляем должны рассмотреть то, что было упущено во время поиска в связи с отсутствием <tex>n'</tex>. Мы добиваемся этого путем применения строк 20-22 к <tex>i+1n'</tex>для каждого раскрытого направленного predecessor-ую точку из последовательности из а узла <tex>n'</tex> точек. Рассмотрим все перестановки из этих Если <tex>i+1n'</tex> точекещё не выполняет условие планирования, означающие порядок вставки этих точек. Всего таких перестановок A* будет неоднократно возобновляться пока механизм планирования не допустит алгоритму Дейкстры положить <tex>(i+1)!n'</tex>в поисковую очередь. Заметим, что таким образом не требуется каких-либо дополнительных усилий во время типичного поиска Дейкстры. Тогда средняя степень последней вершины среди перестановок равна:

Мы может быть уверены, что нерассмотренные узлы не будут принудительно опущены после применения операции heaping-up к <tex>E(\operatorname{deg}(v_{i+1}))=\frac {\sum_{p=perm(v_1n'</tex>. Иначе, v_2мы могли бы иметь узел <tex>n''</tex>, который являлся бы ребенком n и впоследствии был бы заменен узлом <tex>n'</tex>...Заметим, что <tex>n''</tex> должен быть рассмотрен, v_{i+1})} \operatorname{deg} (p[i+1])} {(i+1)!}поскольку <tex>n'</tex>был раскрыт. Однако, это противоречение к лемме 7, которая гарантирует, что этого не произойдет.

Каждая из Более того, следующее следствие гарантирует, что наилучшее <tex>i+1d(n')</tex> вершин побывает последней ровно не лучше, чем <tex>i!d</tex> раз-значение любой рассмотренной вершины, в частности, поэтому:раскрытой вершины. Это означает, что мы не упустим возможность раскрыть <tex>n'</tex>.

<tex>E(\operatorname{deg} (v_{i+1}))Лемма|about=\frac {\sum_{kследствие 3|statement=0}^{i} i! \operatorname{deg} Пусть <tex>n</tex> будет узлом в <tex>P(v_kG)} {</tex>, который был раскрыт Дейкстрой. Кроме того, пусть <tex>m</tex> будет узлом, который заново добавляется в <tex>P(i+1G)!} = \frac {\sum_</tex> или его позиция изменена, после того как <tex>n</tex> был раскрыт. Если <tex>h</tex> допустимая, тогда выполяется следующее:<tex>C_{k=0}^i \operatorname{deg}P(v_kG)} {i+1} = \frac {O(i+1R,m)} {i+1} >= Od(1n)</tex>|proof=...

=== Удаление точки =4.6 Пример ====== Алгоритм ====Мы проиллюстрируем работу алгоритма 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. Легко заметить, что эвристическая функция допустима. При удалении точки получится Первый раз 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_{Acronym|звёздный многоугольник, который можно затриангулировать за линию|Общеизвестный факт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, где сплошные линии представляют кучные ребра и пофлипатьпунктирные линии показывают кросс-ребра. Во избежание путаницы на рисунке некоторые из ребер не полностью изображены. Мы указываем каждое из них, если нужноиспользуя короткую стрелку с конретной целью.==== Время работы ===={{Acronym|Средняя степень вершины в триангуляции — После построения, как показано 10, планировщик проверяет только ребенка <tex>(s_4, s_2)</tex> узла <tex>R</tex> на предмет того, что <tex>Og(1s_6) + d(s_4,s_2) <= f(s_1)</tex>|Общеизвестный факт}}. Отметим, поэтому триангуляция звёздного многоугольника будет тоже за что <tex>s_1</tex> является головой поисковой очереди A*. Значение <tex>Od(1s_4,s_2)</tex>равно 2, т.е. Новых рёбер получится <tex>Og(s_6) + d(1s_4,s_2) = 7 + 2 = 9 = f(s_1)</tex>. Следовательно, проверить их на локальный критерий Делоне планировщик позволяет Дейкстре раскрыть <tex>R</tex> и пофлипать тоже можно за вставить <tex>(s_4,s_2)</tex> в поисковую очередь. При раскрытии <tex>OR</tex> находится первый путь из ответа. Он строится из пути <tex>P(1G)</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>Oне выполняется условие <tex>g(1s_6)+d(n)<=f(s_1)</tex>. Следовательно, возобновляется A*.

== Constraints =={{Определение|definition='''Констрейнты''' — рёбраМы предполагаем, что условие раскрытия определено как раскрытие одной вершины для того, которые нельзя флипатьчтобы пример был простым и иллюстративным.}}{{Утверждение|statement=Хорошая триангуляция с констрейнтом может быть хорошей с точностью до видимости через констрейнтПоэтому A* раскрывает <tex>s_1</tex> и останавливается.}}=== Вставка ===[[Файл:ConstraintИсследованная часть <tex>G</tex> на текущем этапе показана на рисунке 11.png|400px|thumb|right|Красным выделен вставляемый констрейнт]]Смотрим на список рёберРезультат раскрытия приведет к обнаружению 2 новых запасных ребер <tex>(s_1, пересечённых ещё не вставленным констрейнтом, и флипаем их. Последнее флипнутое ребро s_2)</tex> и будет констрейнтом {{Acronym|<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.