Изменения

==Решение методом полос==[[Файл:cgslabs.png|200px|right]]Проведём через каждую вершину вертикальную прямую. Получим полосы (slabs). Пусть каждой полосе соответствует точкаТакже как и алгоритм Эппштейна, через которую проведён левый край полосы. Будем хранить отсортированный массив K* выполняет поиск пути на графе <tex>xG</tex>-координат, тогда за и использует граф путей <tex>OP(\log nG)</tex> можно найти. Граф путей ищется с помощью алгоритма Дейкстры для того, в какой полосе лежит чтобы вычислить пути <tex>Ps-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> в прямом направлении в отличие от алгоритма Эппштейна, из способов сделать дерево частично персистентным — node-copying (или path-copying, в разных источниках по-разному). Храним массив корней за чего корнем дерева<tex>T</tex> является вершина начальная <tex>s</tex>. Когда нам нужно изменить нодуЭто необходимо для того, мы создаём в этом массиве новый кореньчтобы была возможность работать c неявным описанием графа <tex>G</tex> через функцию successor (функция, но его поля left и right совпадают с таковыми в предыдущем корне. Далее мы идём от корня к ноде, которую хотим изменить. Все возвращающая список исходящих ребер из данной вершины по пути мы «копируем» так же, как и корень, при этом у предка меняем соответствующий указатель на новый). После этого мы меняем нужную нам ноду. Таким образом, для такого дерева нам нужно На протяжение статьи будем считать граф <tex>O(n \log n)G</tex> памятиконечным, если не будет сказано иное. Заметим, что А* корректен на конечных графах. Будем следовать литературному соглашению, предполагая, что стоимость бесконечного пути неограниченна.

Можно усовершенствовать этот способ== 4. Теперь 2 Стоимость объезда ==[[Файл:kstar-figure-3.png|600px|thumb|center|'''Рисунок 3.''' Исходный граф, в каждой ноде будет храниться номер версии и поля для ленивого изменения дерева: фиксированное количество запасных указателей left и right и номера версий для нихкотором сплошные линии представляют построенное 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>. Этот способ называется limited node copyingТогда <tex>\delta(u, v)</tex> может быть определена так: <tex>\delta(u, для него нужно Ov) = f_u(v) - f(nv) памяти= g(u) + c(u, потому что амортизированно за один апдейт копируем Ov) + h(v) - g(v) - h(v) = g(u) + c(u, v) - g(1v) нод.</tex>

===Локализация Заметим, что <tex>\delta(u, v)</tex> дает точную объездную метрику, поскольку оценочное <tex>h</tex>-значение не появляется в полосе===Воспользуемся сбалансированным частично персистентным деревом для хранения отрезков в полосах. Каждая полоса — это новая версия дереваопределении функции <tex>\delta(u, v)</tex>.

==Время и память4.3 Структура графа путей ==На запрос нужно Структура графа путей <tex>P(G)</tex> довольно сложная. В принципе, <tex>P(G)</tex>Oбудет ориентированным графом, вершины которого соответствуют ребрам в исходном графе <tex>G</tex>. Он будет организован как коллекция взаимосвязанных '''куч''' (\log nангл. ''heap''). 2 бинарные кучи минимума присвоены к каждой вершине <tex>v</tex> в графе <tex>G</tex>, на препроцессинг — которые называются '''входящей кучей''' (англ. ''incoming heap'')<tex>H_{in}(v)</tex>Oи '''деревянной кучей''' (n \log nангл. ''tree heap'') <tex>H_{T}(v)</tex>; памяти нужно . Эти кучи являются базисом <tex>OP(nG)</tex>. Как мы покажем далее, использование этих куч также играет главную роль в поддержании асимптотической сложности K*, также как в EA и LVEA.

==Алгоритм Киркпатрика==Существует ли метод локализации со временем поиска за Входящая куча <tex>OH_{in}(\log nv)</tex> содержит узлы для каждого запасного ребра к вершине <tex>v</tex>, использующий менее чем квадратичную память? Эта задача оставалась не решенной довольно долгокоторые до сих пор были обнаружены A*. Но все же была решена Липтоном и Тарьяном Узлы <tex>H_{in}(v)</tex> будут упорядочены в 1977соответствии с <tex>\delta</tex>-1980 ггзначением соответствующих переходов. Но их метод оказался Узел владеющий ребром с минимальной стоимостью ущерба будет расположен на столько громоздкимвершине кучи. Мы ограничим структуру кучи <tex>H_{in}(v)</tex> таким образом, а оценки времени его эффективности содержат слишком большую константучто её корень в отличие от остальных узлов, что сами авторы будет иметь не считали этот метод практичным, но более 1 ребенка. Обозначим его существование заставляет думать, что может найтись практичный алгоритм с временной оценкой <tex>Oroot_{in}(\log nv)</tex> и линейной памятью.

Недавно Киркпатриком был предложен оптимальный метод, дающий ответ на ожидания Липтона и Тарьяна, {{---}} детализация триангуляции'''Пример 4.''' Рисунок 4 иллюстрирует входящие кучи графа из рисунка 3.===Предобработка===Цифры рядом с узлами кучи соответствуют <wikitextex>[[Файл:кирк1.png|right|300px]]Пусть планарный N-вершинный граф задает триангуляцию нашего многоугольника (если это не так, то воспользуемся методом триангуляции многоугольника за время $O (n \log n)$. Напомним, что триангуляция на множестве вершин $V$ есть планарный граф с не более чем $3 |V| - 6$ ребрами ([[Формула_Эйлера |формула Эйлера]]). Для удобства описания алгоритма поместим нашу триангуляцию в охватывающий треугольник и построим триангуляцию области между нашими объектами. После этого преобразования все триангуляции будут обладать тремя границами и ровно $3 |V| - 6$ ребрами.delta</wikitextex>-значениям.

===Структура данных===<wikitex>[[Файл:кирк2kstar-figure-4.png|right600px|300px]][[Файл:кирк3.pngthumb|rightcenter|300px]]Итак, имеется N-вершинная триангуляция $G$, и пусть строится последовательность триангуляций $S_1, S_2, \dots, S_'''Рисунок 4.''' Входящие кучи <tex>H_{hin}(Ns_i)}$, где $S_1 = G$</tex>, а $S_i$ получается из $S_{i - 1}$ по следующим правилам:* Шаг 1. Удалим некоторое количество неграничных и независимых (попарно несмежных друг с другом) вершин и инцидентные им ребра (от выбора этого множества напрямую зависит оптимальность алгоритма).* Шаг 2. Построить триангуляцию получившихся в результате шага 1 многоугольников.Таким образом $S_{h(N)}$ состоит полученные из одного треугольника. Заметим, что все триангуляции имеют одну общую границу, так как удаляются только внутренние узлы. Далее, будем обозначать все треугольники как $R$, а также будем говорить, что треугольник $R_ij$ принадлежит триангуляции $S_i$графа, если он был создан показанного на шаге (2) при построении этой триангуляциирисунке 3.]]

Теперь построим структуру данных $Деревянная куча <tex>H_{T$ }(v)</tex> для поискапроизвольной вершины <tex>v</tex> строится следующим образом. Эта структура представляет собой направленный ацикличный графЕсли <tex>v</tex> - стартовая вершина, вершинами которого будут наши треугольникит.е. Определим эту структуру следующим образом: из треугольника $R_k$ <tex>v = s</tex>, то <tex>H_{T}(v)</tex> будет вести ребро изначально пустой кучей. Затем в треугольник $R_j$неё будет добавлен <tex>root_{in}(s)</tex>, если при построении $S_i$ из $S_<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_{i-1T}$ (u)</tex>. Однако, для экономии памяти мы имеем* $R_j$ удалятся из $S_создаем только дешевую копию <tex>H_{i - 1T}$ (u)</tex>. Это осуществляется через создание копий только тех узлов кучи, которые лежат на шаге обновленном пути в <tex>H_{T}(1u)</tex>. Оставшаяся часть <tex>H_{T}(u)</tex> не копируется. Другими словами, <tex>root_{in}(v)* $R_k$ создается </tex> вставляется в $S_<tex>H_{T}(u)</tex> неразрушающим путем так, что структура <tex>H_{T}(u)</tex> сохраняется. В куче <tex>H_{T}(v)</tex> к <tex>root_{iin}$ на шаге (v)</tex> могут быть присоединены 1 или 2ребенка. К тому же, <tex>root_{in}(v)* $R_j \cap R_k \ne \varnothing $</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>, что треугольники полученные из $S_1$ (и только они) не имеют исходящих реберграфа, показанного на рисунке 3.]]

Для ясности удобно изобразить $T$ в рассмотренном видеНазовем ребра, которые берут начало из входящих или деревянных куч, то есть помещая его '''кучными ребрами''' (англ. ''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)</wikitextex> непосредственный результат древовидных структур <tex>====Выбор множества удаляемых вершин====H_{T}(v)<wikitex/tex>Как уже упоминалосьи входящих куч. Более того, от выбора множества вершит триангуляциикучная характеристика деревянной кучи обеспечивает упорядочивание в соответствии с <tex>\delta</tex>-значением по ребрам из <tex>H_{T}(v)</tex>, которые будут удалены при построении $S_i$ а кучная характеристика входящих куч - по $S_всем ребрам из <tex>H_{i-1in}$ существенно зависит эффективность метода</tex>. ПредположимВсе это приводит к тому, что можно выбрать это множество так<tex>H_{G}(v)</tex> - тернарная куча, чтобы выполнялись следующие ''свойства'' ($N_i$ обозначает число вершин упорядоченная в $S_i$):соответствии с <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>. Мы назовем такие указатели '''Свойство 1кросс-ребрами'''(англ. $N_i = a_i N_''cross edges''), в то время как указатели, возникающие из куч названы кучными ребрами, как упоминалось раньше. Более того, мы добавим специальный узел <tex>\mathrm{iR}</tex> в <tex>P(G)</tex> с одним выходящим кросс-1}$, где $a_i \le a ребром к < 1$ для $i = 2,\dots , htex>R(Nt)$</tex>.

'''Свойство 2'''. Каждый треугольник $R_i Более того, мы определим весовую функцию <tex>\in S_i$ пересекается не более чем с $H$ треугольниками Delta</tex> на ребрах из $S_{i-1}$ и наоборот<tex>P(G)</tex>.Первое свойство немедленно влечет за собой следствиеПусть <tex>(n, что $hn')</tex> обозначает ребро в <tex>P(NG) \le \left \lceil \log_{1</tex>, и пусть <tex>e</tex> и <tex>e'</tex> обозначают ребра из <tex>G</tex>, соответствующие узлам <tex>n</tex> и <tex>n'</a}N \right tex>. Тогда определим <tex>\rceil = ODelta(log Nn,n')$, поскольку при переходе от $S_{i-1}$ к $S_i$ удаляется по меньшей мере фиксированная доля вершин.</tex> следующим образом:

Также из этих свойств следует, что память для $T$ равна $O(N)$. Действительно, заметим, что эта память используется для хранения узлов и указателей на их потомков. Из [[Формула_Эйлера|теоремы Эйлера]] о плоских графах следует, что $S_i$ содержит $F_i < 2N_i$ треугольников. Число узлов в $T$, представляющих треугольники из $S_i$, не превосходит $F_i$ tex> \Delta(только те треугольникиn, которые действительно принадлежат $S_i$, появляются на соответствующем «ярусе» $T$n'). Отсюда следует, что общее число узлов в $T$ меньше, чем=\begin{cases}$2 \delta(N_1 + N_2 + e') - \dots + N_{hdelta(Ne),& \text{if}\ (n,n') \le 2N_1(1 + a + a^2 + \dots + a^text{hheap edge} \\ \delta(Ne') - 1,& \text{if}\ (n,n') < \frac{2N}\text{1 - across edge}$.Что касается памяти, используемой под указатели, то по свойству 2 каждый узел имеет не более $H$ указателей, поэтому не более $ \fracend{2NHcases}{1-a}$ указателей появится в $T$. Это доказывает последнее утверждение. </tex>

Покажем теперьЛемма 1 подразумевает, что критерий выбора множества удаляемых вершинкуча упорядоченная в соответствии с <tex>\delta</tex>-значанием поддерживается для любого кучного ребра из <tex>P(G)</tex>. Эта упорядочивание кучи подразумевает, удовлетворяющий вышеописанным свойствамчто <tex>\Delta(n, существует.{{Теорема|about=критерий выбора множества удаляемых вершин|statement=Если на шаге (1n') построения последовательности триангуляции удалять несмежные вершины со степенью меньше некоторого целого </tex> неотрицательна для любого кучного ребра <tex>(будет указано позжеn,n') числа $K$</tex>. Следовательно, то свойства<tex>\Delta</tex> также неотрицательна, описанные выше, будут выполненыт.|proof='''1е. <tex>\Delta(n,n''' Для проверки первого свойства воспользуемся некоторыми особенностями плоских графов. Из [[Формула_Эйлера | формулы Эйлера]] ) >= 0</tex> для плоских графовлюбого ребра <tex>(n, n')</tex> в частном случае триангуляции, ограниченной тремя ребрами, следует, что число вершин $N$ и число ребер $e$ связаны соотношением $e = 3N - 6$.Пока в триангнуляции есть внутренние вершины <tex>P(в противном случае задача тривиальнаG), степень каждой из трех граничных вершин не меньше трех</tex>. Поскольку существует $3N - 6$ ребер, а каждое ребро инцидентно двум вершинам, то сумма степеней всех вершин меньше $6N$. Отсюда сразу следует, что не менее $ Стоимость пути <tex>\frac{N}{2}$ вершин имеет степень меньше 12. Следовательноsigma</tex>, пусть $K = 12$т. Пусть также $v$ {{---}} число выбранных вершине. Поскольку каждой из них инцидентно не более $K-1 = 11$ ребер, а три граничные вершины не выбираются, то мы имеем $v \ge \left \lfloor \frac<tex>C_{1}{12P(G)}(\frac{N}{2} - 3sigma) </tex> равна <tex>\right sum_{e \rfloor $.Следовательно, $a in \cong 1 - sigma}\frac{1}{24} < 0,959 < 1$, что доказывает справедливость свойства 1.'''2. ''' Выполнение второго свойства обеспечивается тривиально. Поскольку удаление вершины со степенью меньше $K$ приводит к образованию многоугольника с числом ребер менее $K$, то каждый из удаленных треугольников пересекает не более $K - 2 = H$ новых треугольников.}}Delta(e)</wikitextex>.

'''Пример 6.''' В оставшейся части этого раздела мы проиллюстрируем особенности структуры графа путей, которые актуальны для нахождения кратчайших путей <tex>s-t</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*. Второе наблюдение заключается в существовании соответствия один-к-одному между путей <tex>s-t</tex> в <tex>G</tex> и путей в <tex>Р(G)</tex>, которые начинаются в <tex>\mathrm{R}</tex>. ... {{Лемма|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* ==Алгоритмический принцип 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> кратчайших путей.  Data: A graph given by its start vertex s ∈ V and its successor function succ and anatural number kResult: A list R containing k sidetrack edge 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> пуста: переходим на строку 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 Пусть <wikitextex>\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* входит в главный цикл. 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. Это требует последующую проверку статуса Дейкстры. Мы должны быть уверены, что Дейкстра поддерживает согласованное состояние после изменений в треугольнике $S_1$<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-либо вершине $z$узел <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* приводит к изменениям в триангуляциях $S_1структуре <tex>P(G)</tex>. Таким образом, после возобновления A*, мы обновляем <tex>P(G)</tex> и проверяет статус поиска Дейкстры (строка 15). В основном, A* может добавить новые узлы, менять <tex>\dotsdelta</tex>-значения существующих узлов или даже удалять узлы. A* может также существенно изменять дерево поиска <tex>T</tex>, S_которое будет в худшем случае разрушать структуру все деревянных куч <tex>H_{T}</tex>. Эти изменения могут приводить к глобальной реструктуризации или даже перестроению <tex>P(G)</tex> с нуля. В худшем случае это может сделать предыдущие поиски Дейкстры на <tex>P(G)</tex> бесполезными таким образом, что нам придется перезапускать алгоритм Дейкстры с нуля. Если использованная эвристическая оценка допустимая, то наше положение лучше. Нам по-прежнему может понадобится перестроение <tex>P(G)</tex>, но мы покажем, что это перестроение не мешает корректности поиска Дейкстры на <tex>P(G)</tex>. Другими словами, мы не теряем результаты, до сих пор полученные поиском Дейкстры. В случае монотонной эвристической оценки мы даже не нуждаемся в восстановлении или перестроении <tex>P(G)</tex>. Если <tex>h</tex> монотонная, то дерево поиска A* является деревом кратчайшего пути для всех раскрытых вершин. Следовательно, g-значения раскрытых вершин не меняются. Это означает, что <tex>\delta</tex>-значения для внутренних ребер никогда не изменятся. Ребра дерева раскрытых вершин не изменятся также. Следовательно, обновление <tex>\delta</tex>-значений, heaping-up, heaping-down (Nоперации в кучах)}$или удаление узлов не влекут за собой каких-либо изменений в <tex>P(G)</tex>. Только добавление новых узлов приводит к изменениям в <tex>P(G)</tex>. Следовательно, восстановление или глобальное перестроение не требуется в данном случае. В оставшейся части этого раздела, мы сначала покажем, что корректность поиска Дейкстры на <tex>P(G)</tex> поддерживается в случае допустимой эвристической оценки. После этого мы покажем, что изменения в <tex>P(G)</tex> могут помешать завершенности поиска Дейкстры независимо от того, является ли эвристика допустимой или даже монотонной. Следовательно, откуда и происходит название самого методамы предложим механизм для её поддержания. Мы фокусируемся дальше на корректности поиска Дейкстры на <tex>P(G)</tex> в случае допустимой эвристической оценки. Сначала, мы заявляем, что если <tex>h</tex> допустимая, то узлы исследованной части <tex>P(G)</tex> не поменяют свои <tex>\delta</wikitextex>-значения. {{Лемма|about=6|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=...}} Из леммы 6 мы может вывести следующее следствие. {{Лемма|about=Псевдокодследствие 3|statement=Пусть <tex>n</tex> будет произвольным узлом в <tex>P(G)</tex>. Если <tex>h</tex> допустимая функция, то <tex>n</tex> никогда не будет удален из <tex>P(G)</tex> после того, как <tex>n</tex> был рассмотрен алгоритмом Дейкстры.|proof=...}} Более того, мы докажем, что структура исследованной части <tex>P(G)</tex> не изменится. {{Лемма|about=7|statement=Пусть <tex>n</tex> будет произвольным узлов в <tex>P(G)</tex>. Если <tex>h</tex> допустимая функция, то <tex>n</tex> никогда не изменит свою позицию после того, как он был рассмотрен алгоритмом Дейкстры.|proof=...}}  Леммы 6 и 7 обеспечивают, что изменения в <tex>P(G)</tex>, которые индуцируются A*, не влияют на часть <tex>P(G)</tex>, которую алгоритм Дейкстры уже исследовал. Это гарантирует корректность поиска Дейкстры на <wikitextex>Пусть все потомки узла $u$ из $T$ собраны в список successorsP(uG)</tex>, если используемая эвристика допустимая. Таким образом, а triangleкаждый путь, который предоставляет алгоритм Дейкстры корректен и его длина действительна. Однако, это не обеспечивает завершенность поиска Дейкстры на <tex>P(uG) обозначает треугольник</tex>. Возможно, соответствующий что узел <tex>n'</tex> присоединяется к другом узлу $u$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>d(n')</tex> не лучше, чем <tex>d</tex>-значение любой рассмотренной вершины, в частности, раскрытой вершины. Это означает, что мы не упустим возможность раскрыть <tex>n'</wikitextex>.  procedure localization{{Лемма|about=следствие 3|statement=Пусть <tex>n</tex> будет узлом в <tex>P(G)</tex>, который был раскрыт Дейкстрой. Кроме того, пусть <tex>m</tex> будет узлом, который заново добавляется в <tex>P(zG)</tex> или его позиция изменена, после того как <tex>n</tex> был раскрыт. Если <tex>h</tex> допустимая, тогда выполяется следующее: if <tex>C_{P(z not in triangleG)}(rootR,m)>= d(n)</tex>|proof=... z in infinite region}} else u = root= 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. Легко заметить, что эвристическая функция допустима. while Первый раз 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(us_6)+d(n) !<= nullf(s_1)</tex>. Следовательно, возобновляется A*. for Мы предполагаем, что условие раскрытия определено как раскрытие одной вершины для того, чтобы пример был простым и иллюстративным. Поэтому A* раскрывает <tex>s_1</tex> и останавливается. Исследованная часть <tex>G</tex> на текущем этапе показана на рисунке 11. Результат раскрытия приведет к обнаружению 2 новых запасных ребер <tex>(s_1,s_2)</tex> и <tex>(v s_1,s_6)</tex>, которые будут добавлены в <tex>H_{in successors}(us_2)</tex> и <tex>H_{in}(s_6) if </tex> соответственно. Обновленные кучи <tex>H_{in}(z s_2)</tex> и <tex>H_{in triangle}(s_6)</tex> представлены на рисунке 12. Другие кучи остаются неизменными, как на рисунке 9. Граф путей <tex>P(vG)</tex> перестаивается, как показано на рисунке 13. Затем алгоритм Дейкстры возобновляется. Заметим, что поисковая очередь Дейкстры содержит только <tex>(s_4,s_2) u </tex> с <tex>d = v return u2</tex> на этом моменте. Используя ручное выполнение мы можем легко увидеть, что Дейкстра будет выдавать в ответ пути, перечисленные в таблице 1.