Изменения

  1) K* применяет A* на графе <tex>G</tex> вместо обратного алгоритма Дейкстры, который использует алгоритм Eppsteinиспользуется алгоритмом Эппштейна.

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> конечным, если не будет сказано иное. Заметим, что А* корректен на конечных графах. Будем следовать литературному соглашению, предполагая, что стоимость бесконечного пути неограниченна.

[[Файл: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)</tex> дает точную объездную метрику, поскольку функция оценки оценочное <tex>h</tex>-значения значение не появляется в определении функции <tex>\delta(u, v)</tex>.

Структура графа путей <tex>P(G)</tex> довольно сложная. В принципе, <tex>P(G)</tex> будет ориентированным графом, вершины которого соответствуют ребрам в исходном графе <tex>G</tex>. Он будет организован как коллекция взаимосвязанных '''куч ''' (англ. ''heap''). 2 бинарные минимальные кучи минимума присвоены к каждой вершине <tex>v</tex> в графе <tex>G</tex>, которые называются '''входящей кучей ''' (англ. ''incoming heap'')<tex>H_{in}(v)</tex> и '''деревянной кучей ''' (англ. ''tree heap'') <tex>H_{T}(v)</tex>. Эти кучи являются базисом <tex>P(G)</tex>. Как мы покажем далее, испльзование использование этих куч также играет главную роль в поддержании асимптотической сложности K*, также как в EA и LVEA. Входящая куча <tex>H_{in}(v)</tex> содержит узлы для каждого запасного ребра к вершине <tex>v</tex>, которые до сих пор были обнаружены A*. Узлы <tex>H_{in}(v)</tex> будут упорядочены в соответствии с <tex>\delta</tex>-значением соответствующих переходов. Узел владеющий ребром с минимальной стоимостью ущерба будет расположен на вершине кучи. Мы ограничим структуру кучи <tex>H_{in}(v)</tex> таким образом, что её корень в отличие от остальных узлов, будет иметь не более 1 ребенка. Обозначим его <tex>root_{in}(v)</tex>. '''Пример 4.''' Рисунок 4 иллюстрирует входящие кучи графа из рисунка 3. Цифры рядом с узлами кучи соответствуют <tex>\delta</tex>-значениям. [[Файл:kstar-figure-4.png|600px|thumb|center|'''Рисунок 4.''' Входящие кучи <tex>H_{in}(s_i)</tex>, полученные из графа, показанного на рисунке 3.]]

Входящая Деревянная куча <tex>H_{inT}(v)</tex> содержит узлы для каждого запасного ребра к вершине произвольной вершины <tex>v</tex> строится следующим образом. Если <tex>v</tex>- стартовая вершина, которые до сих пор были обнаружены A*т.е. Узлы <tex>v = s</tex>, то <tex>H_{inT}(v)</tex> будут упорядочены будет изначально пустой кучей. Затем в соответствии с неё будет добавлен <tex>\deltaroot_{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>root_H_{inT}(v)</tex> как <tex>R(v)</tex>.

Деревянная куча <tex>H_{T}(v)</tex> для произвольной вершины <tex>v</tex> строится следующим образом. Если <tex>v</tex> [[Файл:kstar-figure- стартовая вершина, т5.еpng|600px|thumb|center|'''Рисунок 5. <tex>v = s</tex>, то ''' Деревянные кучи <tex>H_{T}(v)</tex> будет изначально пустой кучей. Затем узел в неё будет добавлен <tex>root_{in}(ss_i)</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> 1 или 2 ребенка могут быть присоединены к <tex>root_{in}(v)</tex>. К тому же, <tex>root_{in}(v)</tex> хранит только 1 собственного ребенка из <tex>H_{in}(v)</tex>. Мы обозначим корень <tex>H_{T}(v)</tex> как <tex>R(v)</tex>рисунке 3.]]

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

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

Более того, мы определим весовую функцию <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> следующим образом:

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

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

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

Если использованная эвристическая оценка допустимая, то наше положение лучше. Нам по-прежнему может понадобится перестроение <tex>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>. Следовательно, восстановление или глобальное перестроение или глобальная реструктуризация не требуется в данном случае.

Следствие 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=...}}