Изменения

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

== Поиск A* на G. == 1) K* применяет A* к входному графу на графе <tex>G</tex> для тоговместо обратного алгоритма Дейкстры, чтобы определить дерево поиска <tex>T</tex>который используется алгоритмом Эппштейна. В отличие от алгоритма Eppstein в K* 2) Мы запускаем A* применяется к графу на <tex>G</tex> в прямом порядке из-за чего коренем дерева и Дейкстру на <tex>T P(G)</tex> является вершина <tex>s</tex>. Это необходимо для тогов поочередном порядке, чтобы была возможность работать c неявным описанием графа который позволяет Дейкстре вычислить требуемые пути до заверешения полного поиска алгоритма A* на графе <tex>G</tex> через функцию successor. На протяжении статьи будем считать граф <tex>G</tex> конечным, если не будет сказано иначе. Заметим, что А* корректен на конечных графах. Будем следовать литературному соглашению, предполагая, что стоимость бесконечного пути неограниченна.

== 4.1 Поиск A* на G == K* применяет A* к входному графу <tex>G</tex> для того, чтобы построить дерево поиска <tex>T</tex>. Заметим, что A*, также как и алгоритм Дейкстры, строит дерево поиска в процессе нахождения кратчайшего пути <tex>s-t</tex> . Эти деревья формируются с помощью ссылок на родительские узлы, которые хранятся в том время, как A* производит итерации для того, чтобы восстановить путь <tex>s-t</tex>, когда вершина <tex>t</tex> ещё не найдена. Запасные ребра, открытые в процессе поиска A* на графе G, немедленно добавляются в граф P(G), структура которого будет объясняться в разделе 4.3.  В K* A* применяется к графу <tex>G</tex> в прямом направлении в отличие от алгоритма Эппштейна, из-за чего корнем дерева <tex>T</tex> является вершина начальная <tex>s</tex>. Это необходимо для того, чтобы была возможность работать c неявным описанием графа <tex>G</tex> через функцию successor (функция, возвращающая список исходящих ребер из данной вершины). На протяжение статьи будем считать граф <tex>G</tex> конечным, если не будет сказано иное. Заметим, что А* корректен на конечных графах. Будем следовать литературному соглашению, предполагая, что стоимость бесконечного пути неограниченна. == 4.2 Стоимость объезда ==[[Файл:kstar-figure-3.png|600px|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>\deltaH_{in}(u, vs_i)</tex> дает точную объездную метрику, поскольку функция оценки <tex>h</tex>-значения не появляется в определении функции <tex>\delta(uполученные из графа, v)</tex>показанного на рисунке 3.]]

Деревянная куча <tex>H_{T}(v)</tex> для произвольной вершины <tex>v</tex> строится следующим образом. Если <tex>v</tex> - стартовая вершина, т.е. <tex>v == Структура графе путей ==Структура графа путей s</tex>, то <tex>PH_{T}(Gv)</tex> довольно сложнаябудет изначально пустой кучей. В принципеЗатем в неё будет добавлен <tex>root_{in}(s)</tex>, если <tex>PH_{in}(Gs)</tex> не пустая. Если <tex>v</tex> не стартовая вершина, то пусть вершина <tex>u</tex> будет ориентированным графом, родителем вершины которого соответствуют ребрам <tex>v</tex> в исходном графе Gдереве поиска <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>. heapОднако, для экономии памяти мы создаем только дешевую копию <tex>H_{T}(u)</tex>. 2 бинарные минимальные Это осуществляется через создание копий только тех узлов кучи присвоены к каждой вершине v в графе G, которые называются входящей кучей лежат на обновленном пути в <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>PH_{in}(Gv)</tex>. Как мы покажем далее, испльзование этих куч также играет главную роль в поддержании асимптотической сложности K*, также Мы обозначим корень <tex>H_{T}(v)</tex> как в EA и LVEA<tex>R(v)</tex>.

Входящая куча <tex>H_{in}(v)</tex> содержит узлы для каждого запасного ребра к вершине v, которые до сих пор были обнаружены A*. Узлы <tex>H_{in}(v)</tex> будут упорядочены в соответствии с <tex>\delta</tex>[[Файл:kstar-figure-значением соответствующих переходов5. Узел владеющий ребром с минимальной стоимостью ущерба будет расположен на вершине кучиpng|600px|thumb|center|'''Рисунок 5. Мы ограничим структуру ''' Деревянные кучи <tex>H_{inT}(vs_i)</tex> таким образом, что её корень в отличие от остальных узловполученные из графа, имеет не более 1 ребенка. Мы обозначим его <tex>root_{in}(v)</tex>показанного на рисунке 3.]]

Деревянная куча Назовем ребра, которые берут начало из входящих или деревянных куч, '''кучными ребрами''' (англ. ''heap edges''). Сформулируем следующую лемму.{{Лемма|about=1|statement=Все узлы, достижимые из <tex>H_{T}R(v)</tex> по кучным ребрам, для произвольной каждой вершины <tex>v</tex> строится следующим образом. Если формируют тернарную кучу, упорядоченную в соответствии с <tex>v\delta</tex> - стартовая вершина, тзначением.еМы назовем такую кучу '''графовой кучей''' (англ. ''graph heap'') вершины <tex>v = s</tex>, то и обозначим её как <tex>H_{TG}(v)</tex> будет изначально пустой кучей. Затем узел в неё будет добавлен <tex>root_{in}(s)</tex>|proof=Те узлы, если <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}(uv)</tex>, в которую добавлен достижимы по кучным ребрам из <tex>root_{in}R(v)</tex>. Если Деревянная куча <tex>H_{inT}(v)</tex> пустаяформируется через добавление корней входящих куч всех вершин, то лежащих на пути из стартовой вершины <tex>H_{T}(v)s</tex> идентична до <tex>H_{T}(u)v</tex>в бинарной куче. Однако, для экономии памяти мы создаем только дешевую копию Каждый из этих корней имеет максимум 3 детей: до 2 в <tex>H_{T}(uv)</tex>и дополнительно единственного из входящей кучи. Это осуществляется через создание копий только узлов кучиЛюбой другой узел, которые лежат на обновленном пути <tex>H_{T}(u)</tex>. Оставшаяся часть <tex>H_{T}(u)</tex> живущий во входящей куче имеет не копируетсябольше 2 детей. Другими словамиНапомним, что каждая входящая куча - это бинарная куча с ограничением, что корень имеет единственного ребенка. Древовидная структура <tex>root_H_{inG}(v)</tex> вставляется в непосредственный результат древовидных структур <tex>H_{T}(uv)</tex> неразрушающим путем таки входящих куч. Более того, что структура кучная характеристика деревянной кучи обеспечивает упорядочивание в соответствии с <tex>H_{T}(u)\delta</tex> сохраняется. В куче -значением по ребрам из <tex>H_{T}(v)</tex> 1 или 2 ребенка могут быть присоединены к <tex>root_{in}(v)</tex>. К тому же, root_{in}(v) хранит только 1 собственного ребенка а кучная характеристика входящих куч - по всем ребрам из <tex>H_{in}(v)</tex>. Мы обозначим корень Все это приводит к тому, что <tex>H_{TG}(v)</tex> как - тернарная куча, упорядоченная в соответствии с <tex>R(v)\delta</tex>-значением.}}

Обратимся к ребрам, которые берут начало Финальная структура <tex>P(G)</tex> получется из входящих или и деревянных куч, как к кучным ребрамследующим образом. Сформулируем следующую лемму.Лемма 1. Все узлы, которые достижимы К каждому узлу <tex>n</tex> из <tex>RP(vG)</tex> через кучные ребра для каждой вершины , несущему ребро <tex>(u,v)</tex>, формируют тернарную кучумы присоединим указатель, упорядоченную в соответствии с ссылающийся на <tex>R(u)</tex>, который является корневым узлом <tex>\deltaH_{T}(u)</tex>-значением. Мы назовем такую кучу графовой кучей вершины такие указатели '''кросс-ребрами''' (англ. ''cross edges''), в то время как указатели, возникающие из куч названы кучными ребрами, как упоминалось раньше. Более того, мы добавим специальный узел <tex>v\mathrm{R}</tex> и обозначим его как в <tex>H_{P(G})</tex> с одним выходящим кросс-ребром к <tex>R(vt)</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>.

Финальная структура <tex>P(G)</tex> получется из входящих и деревянных куч следующим образом. К каждому узлу <tex>n</tex> из <tex>P(G)</tex>, несущему ребро <tex>(u,v)</tex>, мы присоединим указатель, ссылающийся на <tex>R(u)</tex>, который является корневым узлом <tex>H_{T}(u)</tex>. Мы назовем такие указатели кросс-ребрами, в то время как указатели, возникающие из куч названы кучными ребрами, как упоминалось раньше. Более того, мы добавим специальный узел <tex>R</tex> в <tex>P(G)</tex> с одним выходящим кросс-ребром к <tex>R(t)</tex>'''Пример 6.'''

Более того, В оставшейся части этого раздела мы определим весовую функцию <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's-t</tex>. Тогда определим <tex>\Delta(n,n')</tex> следующим образом:

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

Лемма 1 подразумевает, что куча упорядоченная Второе наблюдение заключается в соответствии с \deltaсуществовании соответствия один-к-одному между путей <tex>s-значанием поддерживается по любому кучному ребру из t</tex> в <tex>P(G)</tex>. Эта упорядочивание кучи подразумевает, что \Delta(n,n') неотрицательна для любого кучного ребра (n,n'). Следовательно, \Delta также неотрицательна, т.е. \Delta(n,n') >= 0 для любого ребра (n,n') и путей в <tex>PР(G)</tex>. Стоимость пути \sigma, т.е. C_{P(G)}(\sigma) равна которые начинаются в <tex>\sum_mathrm{e \in \sigmaR}\Delta(e)</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 Пусть <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* входит в главный цикл.

== Алгоритмическая структура 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* на G пока вершина . Напомним, что <tex>d</tex> - функция расстояния, используемая в алгоритме Дейкстры. Если очередь поиска Дейкстры пуста или <tex>g(t не будет выбрана из очереди ) + d > f(u)</tex>, то А* возобновляется для рассмотрениятого, чтобы исследовать более большую часть графа <tex>G</tex> (строка 14). ЗатемТо, как долго мы ему позволим работать, вы является компромиссом. Если мы запустим алгоритмы Дейкстры его только на доступной части маленьком количестве шагов, то мы дадим Дейкстре шанс найти необходимое количество путей скорее, чем они будут доступны в <tex>P(G)</tex>. Каждый узел рассмотрел Дейкстрой представляет путь решенияС другой стороны, мы вызываем накладные расходы путем переключения A* и Дейкстры и поэтому должны ограничить количество переключений. Если точнееЭти накладные расходы вызваны тем фактом, что после возобновления A* (строка 14), то путь структура графа <tex>\sigmaP(G)</tex> в может измениться. Следовательно нам необходимо обновить <tex>P(G)</tex>(строка 15), по которому Дейкстра достигла этого узла является решениемкак мы будет широко обсуждать в разделе 4.5. Это требует последующую проверку статуса Дейкстры. Путь s-t может Мы должны быть построен из \sigma за линейное время путем вычисления последовательности запасных ребер seqуверены, что Дейкстра поддерживает согласованное состояние после изменений в <tex>P(\sigmaG) и затем s-t пути из неё</tex>. Если Дейкстра находит k кратчайших путейK* предусматривает условие, которые управляет решением, то Kкогда остановить A* завершается успешно, которое мы назовем ''условие расширения''. ИначеДля того, чтобы поддерживать аналогичную асимптотическую сложность как у EA и LVEA, мы должны определить условие расширения так, чтобы A* возобновляется для исследования большей части G. Это приводит к росту выполнялся пока количество рассмотренных вершин и количество внутренних ребер удваивается или <tex>P(G)</tex>полностью исследован. Мы обсудим эту проблему несколько подробнее позже. В качестве полезного свойства, K* позволяет другое определения этого условия, которое может быть более эффективным на практике. В наших экспериментах в разделе 6, мы определили условие расширения так, что количество рассмотренных вершин или количество рассмотренных ребер ребер возрастает на котором алгоритм Дейкстры затем будет возобновлен20% при каждом запуске A*. Мы будем повторять этот процесс Этот механизм планирования включен до тех пор, пока A* не закончит исследовать весь граф <tex>G</tex>. Как только A* исследует весь граф <tex>G</tex> (строка 9), механизм планирования отключается и в дальнейшем работает только алгоритм Дейкстры не найдет k кратчайших путей.

Алгоритм 1 содержит псевдокод K*. Код с 8 по 25 строчку образует главный цикл K*. Цикл завершается, когда очереди обоих алгоритмов А* и Строки 18-22 представляют обычный шаг рассмотрения узла алгоритмом Дейкстры пусты. До 8 строчки выполняет некоторые подготовительные вещи. После инициализации, А* запускает на 5 строчке пока вершина t не будет выбрана им для рассмотрения, в этом случае кратчайший путь s-t будет найден. Если t не достигнута, то алгоритм завершается без решения. Отметим, что он не завершится на бесконечных графах. Иначе, алгоритм добавляет специальную вершину R, которая назначена корнем когда successor-узел <tex>P(G)n'</tex>, в поисковую очередь алгоритма Дейкстры. Затемсгенерирован, K* входит в главный цикл.K* поддерживает механизм планирования для контролирования, когда A* или Дейкстра будет возобновлены. Если очередь из A* не пуста, что означает, что А* ещё не завершил исследования всего графа G, то Дейкстра возобновляется тогда и только тогда, когда g(t) + d проверяет был ли <= f(u). Значение d является максимальным d-значением среди всех successor-ов головы поисковой очереди tex>n алгоритма Дейкстры. Вершина u является головой поисковой очереди A*'</tex> уже посещен до этого. НапомнимДругими словами, что d - функция расстояниякаждый раз, используемая в алгоритме Дейкстры. Если очередь поиска Дейкстры пуста или g(t) + d > f(u), то А* возобновляется для того, чтобы исследовать более большую часть графа G (строка 14). Токогда узел генерируется, он рассматривает как долго мы ему позволим работать, является компромиссомновый. Если мы запустим его только Эта стратегия обоснована на маленьком количестве шаговнаблюдении, что путь s-t может содержать одно и то мы дадим Дейкстре шанс найти необходимое количество путей скорее, чем они будут доступны в же ребро несколько раз. Строка 24 добавляет следующий путь <tex>P(G)s-t</tex>в результирующее множество R. С другой стороны, мы вызываем накладные расходы Это делается путем переключения A* и Дейкстры и поэтому должны ограничить количество переключений. Эти накладные расходы вызваны тем фактом, что после возобновления A* (строка 14), структура графа конструирования последовательности запасных ребер <tex>Pseq(G\sigma)</tex> может измениться. Следовательно нам необходимо обновить из пути <tex>P(G)\sigma</tex> (строка 15), как мы будет широко обсуждать в разделе 4.5. Это требует последующую проверку статуса Дейкстры. Мы должны быть уверены, что через которые Дейкстра поддерживает согласованное состояние после изменений в достигла узла <tex>P(G)n</tex>, который был только что рассмотрен. K* предусматривает условие, которые управляет решениемАлгоритм завершается, когда остановить A*, которое мы назовем ''условие расширения''. Для того, чтобы поддерживать аналогичную асимптотическую сложность как у EA и LVEA, мы должны определить условие расширения так, чтобы A* выполнялся пока количество рассмотренных вершин и количество внутренних ребер удваивается или G полностью исследован. Мы обсудим эту проблему несколько подробнее позже. В качестве полезного свойства, K* позволяет другое определения этого условия, которое может быть более эффективным на практике. В наших экспериментах в разделе 6, мы определили условие расширения так, что количество рассмотренных вершин или количество рассмотренных результирующее множество добавлено <tex>k</tex> последовательностей запасных ребер ребер возрастает на 20% при каждом запуске A*. Этот механизм планирования включен до тех пор, пока A* не закончит исследовать весь граф G. Как только A* исследует весь граф G (строка 925), механизм планирования отключается и в дальнейшем работает только алгоритм Дейкстры.

Строки 18-22 представляют обычный шаг рассмотрения узла алгоритмом == 4.5 Взаимосвязь алгоритмов Дейкстры. Отметими A* ==Тот факт, что когда successor-узел n' сгенерированоба алгоритма A* и Дейкстры делят между собой граф путей <tex>P(G)</tex>, Kвызывает обеспокоенность в отношении правильности работы Дейкстры на <tex>P(G)</tex>. Возобновление A* не проверяет был ли n' уже посещен до этогоприводит к изменениям в структуре <tex>P(G)</tex>. Другими словамиТаким образом, каждый разпосле возобновления A*, когда узел генерируетсямы обновляем <tex>P(G)</tex> и проверяет статус поиска Дейкстры (строка 15). В основном, он рассматривает как новый. Эта стратегия обоснована на наблюденииA* может добавить новые узлы, что путь sменять <tex>\delta</tex>-t значения существующих узлов или даже удалять узлы. A* может содержать одно и то же ребро несколько раз. Строка 24 добавляет следующий путь s-t также существенно изменять дерево поиска <tex>T</tex>, которое будет в результирующее множество Rхудшем случае разрушать структуру все деревянных куч <tex>H_{T}</tex>. Это делается путем конструирования последовательности запасных ребер seqЭти изменения могут приводить к глобальной реструктуризации или даже перестроению <tex>P(\sigmaG) из пути \sigma, через которые Дейкстра достигла узла n, который был только что рассмотрен</tex> с нуля. Алгоритм завершается, когда в результирующее множество добавлено k последовательностей запасных ребер В худшем случае это может сделать предыдущие поиски Дейкстры на <tex>P(строка 25G)</tex> бесполезными таким образом, что нам придется перезапускать алгоритм Дейкстры с нуля.

== Взаимосвязь алгоритмов Дейкстры и A* ==Тот фактЕсли использованная эвристическая оценка допустимая, что оба алгоритма A* и Дейкстры делят между собой граф путей <tex>P(G)</tex>, вызывает обеспокоенность в отношении правильности работы Дейкстры на <tex>P(G)</tex>то наше положение лучше. Возобновление A* приводит к изменениям в структуре Нам по-прежнему может понадобится перестроение <tex>P(G)</tex>. Таким образом, после возобновления A*, но мы обновляем <tex>P(G)</tex> и проверяет статус поиска Дейкстры (строка 15). В основномпокажем, A* может добавить новые узлы, менять \delta-значения существующих узлов или даже удалять узлы. A* может также существенно изменять дерево что это перестроение не мешает корректности поиска T, которое будет в худшем случае разрушать структуру все деревянных куч H_{T}. Эти изменения могут приводить к глобальной реструктуризации или даже перестроению <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 (операции в кучах) или удаление узлов не влекут за собой каких-либо изменений в <tex>P(G)</tex>. Только добавление новых узлов приводит к изменениям в <tex>P(G)</tex>. Следовательно, восстановление или глобальное перестроение или глобальная реструктуризация не требуется в данном случае.

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

{{Лемма |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=...}}

Следствие 2. {{Лемма|about=следствие 3|statement=Пусть <tex>n </tex> будет произвольным узлов узлом в <tex>P(G)</tex>. Если <tex>h </tex> допустимая функция, то <tex>n </tex> никогда не будет удален из <tex>P(G)</tex> после того, как <tex>n </tex> был рассмотрен алгоритмом Дейкстры. |proof=...}}

{{Лемма |about=7. |statement=Пусть <tex>n </tex> будет произвольным узлов в <tex>P(G)</tex>. Если <tex>h </tex> допустимая функция, то <tex>n </tex> никогда не изменит свою позицию после того, как он был рассмотрен алгоритмом Дейкстры.|proof=...}}

Возможно, что узел <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>d(n') </tex> не лучше, чем <tex>d</tex>-значение любой рассмотренной вершины, в частности, раскрытой вершины. Это означает, что мы не упустим возможность раскрыть <tex>n'</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=...}}

== 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_{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(s1s_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*.

Мы предполагаем, что условие раскрытия определено как раскрытие одной вершины для того, чтобы пример был простым и иллюстративным. Поэтому 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.