418
правок
Изменения
м
== 4. 1 Поиск A* на G. == ) K* применяет A* к входному графу на графе <tex>G для того</tex> вместо обратного алгоритма Дейкстры, чтобы определить дерево поиска Tкоторый используется алгоритмом Эппштейна. В отличие от алгоритма Eppstein в K* 2) Мы запускаем A* применяется к графу на <tex>G</tex> и Дейкстру на <tex>P(G )</tex> в прямом поочередном порядке из-за чего коренем дерева T является вершина s. Это необходимо для того, чтобы была возможность работать c неявным описанием графа G через функцию successor. На протяжении статьи будем считать граф G конечным, если не будет сказано иначе. Заметим, что Акоторый позволяет Дейкстре вычислить требуемые пути до заверешения полного поиска алгоритма A* корректен на конечных графах. Будем следовать литературному соглашению, предполагая, что стоимость бесконечного пути неограниченнаграфе <tex>G</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>H_{Tin}(v) </tex> содержит узлы для произвольной вершины v строится следующим образом. Если каждого запасного ребра к вершине <tex>v - стартовая вершина</tex>, ткоторые до сих пор были обнаружены A*.е. v=s, то Узлы <tex>H_{Tin}(v) будет изначально пустой кучей. Затем узел </tex> будут упорядочены в неё будет добавлен root_{in}(s), если H_{in}(s) не пустаясоответствии с <tex>\delta</tex>-значением соответствующих переходов. Если v не стартовая вершина, то пусть вершина u Узел владеющий ребром с минимальной стоимостью ущерба будет родителем вершины v в дереве поиска Tрасположен на вершине кучи. Мы можем представить, что ограничим структуру кучи <tex>H_{Tin}(v) конструируется как копия H_{T}(u)</tex> таким образом, что её корень в которую добавлен root_{in}(v). Если H_{in}(v) пустая, то H_{T}(v) идентична H_{T}(u). Однако, для экономии памяти мы создаем только дешевую копию H_{T}(u). Это осуществляется через создание копий только отличие от остальных узлов кучи, которые лежат на обновленном пути H_{T}(u). Оставшаяся часть H_{T}(u) будет иметь не копируется. Другими словами, root_{in}(v) вставляется в H_{T}(u) неразрушающим путем так, что структура H_{T}(u) сохраняется. В куче H_{T}(v) более 1 или 2 ребенка могут быть присоединены к root_{in}(v). К тому же, Обозначим его <tex>root_{in}(v) хранит только 1 собственного ребенка из H_{in}(v). Мы обозначим корень H_{T}(v) как R(v)</tex>.
Обратимся к ребрам, которые берут начало '''Пример 4.''' Рисунок 4 иллюстрирует входящие кучи графа из входящих или деревянных куч, как к кучным ребрамрисунка 3. Сформулируем следующую лемму.Лемма 1. Все узлы, которые достижимы из R(v) через кучные ребра для каждой вершины v, формируют тернарную кучу, упорядоченную в соответствии Цифры рядом с узлами кучи соответствуют <tex>\delta</tex>-значением. Мы назовем такую кучу графовой кучей вершины v и обозначим его как H_{G}(v)значениям.
Финальная структура P(G) получется из входящих и деревянных куч следующим образом. К каждому узлу n из P(G), несущему ребро (u,v), мы присоединим указатель, ссылающийся на R(u), который является корневым узлом H_{T}(u). Мы назовем такие указатели кросс-ребрами, в то время как указатели, возникающие из куч названы кучными ребрами, как упоминалось раньше. Более того, мы добавим специальный узел R в P(G) с одним выходящим кросс-ребром к R(t)'''Пример 6.'''
Более того, В оставшейся части этого раздела мы определим весовую функцию \Delta на ребрах из P(G). Пусть (n, n') обозначает ребро в P(G)проиллюстрируем особенности структуры графа путей, и пусть e и e' обозначают ребра из G соответствующие узлам n и n'которые актуальны для нахождения кратчайших путей <tex>s-t</tex>. Тогда определим \Delta(n,n') следующим образом:
\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-значанием поддерживается по любому кучному ребру из P(t</tex> в <tex>G). Эта упорядочивание кучи подразумевает, что \Delta(n,n') неотрицательна для любого кучного ребра (n,n'). Следовательно, \Delta также неотрицательна, т.е. \Delta(n,n') </tex>= 0 для любого ребра (n,n') и путей в P<tex>Р(G). Стоимость пути \sigma</tex>, т.е. C_{P(G)}(которые начинаются в <tex>\sigma) равна \sum_mathrm{e \in \sigmaR}\Delta(e)</tex>.
== Алгоритмическая структура K* ==Алгоритмический принцип K* следующий. Будем запускать алгоритмы Дейкстры и Data: A* на G с чередованием. Сначала, мы запустим A* на G пока вершина t не будет выбрана из очереди для рассмотрения. Затем, вы запустим алгоритмы Дейкстры на доступной части P(G). Каждый узел рассмотрел Дейкстрой представляет путь решения. Если точнее, то путь \sigma в P(G), по которому Дейкстра достигла этого узла является решением. Путь graph given by its start vertex s-t может быть построен из \sigma за линейное время путем вычисления последовательности запасных ребер seq(\sigma) и затем s-t пути из неё. Если Дейкстра находит ∈ V and its successor function succ and anatural number k кратчайших путей, то K* завершается успешно. Иначе, Result: A* возобновляется для исследования большей части G. Это приводит к росту P(G), на котором алгоритм Дейкстры затем будет возобновлен. Мы будем повторять этот процесс до тех пор, пока алгоритм Дейкстры не найдет list R containing k sidetrack edge sequences representing k кратчайших путей. solution paths
Алгоритм 1 содержит псевдокод K*. Код с 8 по 25 строчку образует главный цикл K <tex>open_D</tex> ← пустая приоритетная очередь 2 <tex>closed_D</tex> ← пустая хеш-таблица 3 <tex>R</tex> ← пустой список 4 <tex>P(G)</tex> ← пустой граф путей 5 Выполняем A*. Цикл завершается, когда очереди обоих алгоритмов А* и Дейкстры пусты. До 8 строчки выполняет некоторые подготовительные вещи. После инициализации, А* запускает на 5 строчке графе <tex>G</tex> пока вершина <tex>t </tex> не будет выбрана им для рассмотрения, в этом случае кратчайший путь s-t будет найден. раскрытия 6 Если вершина <tex>t </tex> не была достигнута, то алгоритм завершается выходим без решения. Отметим, что он не завершится на бесконечных графах. Иначе, алгоритм добавляет специальную вершину ответа 7 Кладем <tex>\mathrm{R, которая назначена корнем P(G), }</tex> в поисковую очередь алгоритма Дейкстры. Затем, K* входит в главный цикл.<tex>open_D</tex> 8 '''while''' A queue or open D is not empty:K* поддерживает механизм планирования для контролирования, когда 9 '''if''' A* или Дейкстра будет возобновлены. Если queue is not empty: 10 '''if''' очередь из A* <tex>open_D</tex> не пуста, что означает, что А* ещё не завершил исследования всего графа G, то Дейкстра возобновляется тогда и только тогда, когда g: 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(tn) + d <= f\Delta(un, n'). Значение d является максимальным d-значением среди всех successor-ов головы поисковой очереди | n' \in succ(n алгоритма Дейкстры. Вершина u является головой поисковой очереди A*. Напомним, что d - функция расстояния, используемая в алгоритме Дейкстры. Если очередь поиска Дейкстры пуста или ) \}</tex> 13 '''if''' <tex>g(t) + d <= f</tex> f(u), то Аthen переходим на строку 17. 14 Возобновляем A* возобновляется для того, чтобы исследовать более большую часть графа <tex>G </tex> 15 Обновляем <tex>P(строка 14G)</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). С другой стороны, мы вызываем накладные расходы путем переключения A* и Дейкстры и поэтому должны ограничить количество переключений. Эти накладные расходы вызваны тем фактом, что после возобновления A* : 20 <tex>d(n') = d(строка 14n)+ \Delta(n, структура графа P(Gn') может измениться</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) (строка 15)</tex>, как мы будет широко обсуждать в разделе 4через который узел n был достигнут.5. Это требует последующую проверку статуса Дейкстры. Мы должны быть уверены, что Дейкстра поддерживает согласованное состояние после изменений в P 24 Добавим <tex>seq(G\sigma)</tex> в конец списка <tex>R</tex>. K* предусматривает условие, которые управляет решением, когда остановить A*, которое мы назовем 25 '''if'условие расширения''. Для того, чтобы поддерживать аналогичную асимптотическую сложность как у EA и LVEA, мы должны определить условие расширения так, чтобы A* выполнялся пока количество рассмотренных вершин и количество внутренних ребер удваивается или G полностью исследован. Мы обсудим эту проблему несколько подробнее позже. В качестве полезного свойства, K* позволяет другое определения этого условия, которое может быть более эффективным <tex>|R| = k</tex>: переходим на практикестроку 26. В наших экспериментах в разделе 6, мы определили условие расширения так, что количество рассмотренных вершин или количество рассмотренных ребер ребер возрастает на 20% при каждом запуске A*. Этот механизм планирования включен до тех пор, пока A* не закончит исследовать весь граф G. Как только A* исследует весь граф G (строка 9), механизм планирования отключается и в дальнейшем работает только алгоритм Дейкстры 26 Return R and exit.
Строки 18-22 представляют обычный шаг рассмотрения узла алгоритмом ДейкстрыАлгоритм 1 содержит псевдокод K*. Отметим, что когда successor-узел n' сгенерирован, Код с 8 по 25 строчку образует главный цикл K* не проверяет был ли n' уже посещен до этого. Другими словами, каждый разЦикл завершается, когда узел генерируетсяочереди обоих алгоритмов А* и Дейкстры пусты. До 8 строчки выполняет некоторые подготовительные вещи. После инициализации, он рассматривает как новый. Эта стратегия обоснована А* запускает на наблюдении5 строчке пока вершина <tex>t</tex> не будет выбрана им для рассмотрения, что в этом случае кратчайший путь <tex>s-t может содержать одно и </tex> будет найден. Если <tex>t</tex> не достигнута, то же ребро несколько разалгоритм завершается без ответа. Отметим, что он не завершится на бесконечных графах. Строка 24 Иначе, алгоритм добавляет следующий путь s-t в результирующее множество специальную вершину <tex>R. Это делается путем конструирования последовательности запасных ребер seq</tex>, которая назначена корнем <tex>P(\sigmaG) из пути \sigma</tex>, через которые Дейкстра достигла узла n, который был только что рассмотренв поисковую очередь алгоритма Дейкстры. Алгоритм завершаетсяЗатем, когда K* входит в результирующее множество добавлено k последовательностей запасных ребер (строка 25)главный цикл.
== Взаимосвязь алгоритмов Дейкстры и 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> - функция расстояния, используемая в алгоритме Дейкстры. Если очередь поиска Дейкстры делят между собой граф путей Pпуста или <tex>g(t) + d > f(u)</tex>, то А* возобновляется для того, чтобы исследовать более большую часть графа <tex>G</tex> (строка 14). То, как долго мы ему позволим работать, является компромиссом. Если мы запустим его только на маленьком количестве шагов, вызывает обеспокоенность то мы дадим Дейкстре шанс найти необходимое количество путей скорее, чем они будут доступны в отношении правильности работы Дейкстры на <tex>P(G)</tex>. Возобновление С другой стороны, мы вызываем накладные расходы путем переключения A* приводит к изменениям в структуре P(G)и Дейкстры и поэтому должны ограничить количество переключений. Таким образомЭти накладные расходы вызваны тем фактом, что после возобновления A*(строка 14), мы обновляем структура графа <tex>P(G)</tex> может измениться. Следовательно нам необходимо обновить <tex>P(G) и проверяет статус поиска Дейкстры </tex> (строка 15), как мы будет широко обсуждать в разделе 4. В основном5. Это требует последующую проверку статуса Дейкстры. Мы должны быть уверены, Aчто Дейкстра поддерживает согласованное состояние после изменений в <tex>P(G)</tex>. K* может добавить новые узлыпредусматривает условие, которые управляет решением, менять \delta-значения существующих узлов или даже удалять узлы. когда остановить A* может также существенно изменять дерево поиска T, которое будет в худшем случае разрушать структуру все деревянных куч H_{T}мы назовем ''условие расширения''. Эти изменения могут приводить к глобальной реструктуризации Для того, чтобы поддерживать аналогичную асимптотическую сложность как у EA и LVEA, мы должны определить условие расширения так, чтобы A* выполнялся пока количество рассмотренных вершин и количество внутренних ребер удваивается или даже перестроению P(<tex>G) с нуля</tex> полностью исследован. Мы обсудим эту проблему несколько подробнее позже. В худшем случае это качестве полезного свойства, K* позволяет другое определения этого условия, которое может сделать предыдущие поиски Дейкстры быть более эффективным на практике. В наших экспериментах в разделе 6, мы определили условие расширения так, что количество рассмотренных вершин или количество рассмотренных ребер ребер возрастает на P20% при каждом запуске A*. Этот механизм планирования включен до тех пор, пока A* не закончит исследовать весь граф <tex>G</tex>. Как только A* исследует весь граф <tex>G</tex> (Gстрока 9) бесполезными таким образом, что нам придется перезапускать механизм планирования отключается и в дальнейшем работает только алгоритм Дейкстры с нуля.
Если использованная эвристическая оценка допустимаяСтроки 18-22 представляют обычный шаг рассмотрения узла алгоритмом Дейкстры. Отметим, то наше положение лучше. Нам почто когда successor-прежнему может понадобится перестроение P(G)узел <tex>n'</tex> сгенерирован, но мы покажем, что это перестроение K* не мешает корректности поиска Дейкстры на P(G)проверяет был ли <tex>n'</tex> уже посещен до этого. Другими словами, мы не теряем результатыкаждый раз, когда узел генерируется, до сих пор полученные поиском Дейкстрыон рассматривает как новый. В случае монотонной эвристической оценки мы даже не нуждаемся в перестроении P(G). Если h монотоннаяЭта стратегия обоснована на наблюдении, что путь s-t может содержать одно и то дерево поиска A* является деревом кратчайшего пути для всех раскрытых вершинже ребро несколько раз. Следовательно, gСтрока 24 добавляет следующий путь <tex>s-значения раскрытых вершин не изменитсяt</tex> в результирующее множество R. Это означает, что делается путем конструирования последовательности запасных ребер <tex>seq(\delta-значения для внутренних ребер никогда не изменятся. Ребра дерева раскрытых вершин не изменятся также. Следовательно, обновление sigma)</tex> из пути <tex>\delta-значенийsigma</tex>, heaping-upчерез которые Дейкстра достигла узла <tex>n</tex>, heaping-down (операции в кучах) или удаление узлов не влекут за собой каких-либо изменений в P(G)который был только что рассмотрен. Только добавление новых узлов приводит к изменениям Алгоритм завершается, когда в Pрезультирующее множество добавлено <tex>k</tex> последовательностей запасных ребер (Gстрока 25). Следовательно, перестроение или глобальная реструктуризация не требуется в данном случае.
В оставшейся части этого раздела== 4.5 Взаимосвязь алгоритмов Дейкстры и A* ==Тот факт, мы сначала покажемчто оба алгоритма A* и Дейкстры делят между собой граф путей <tex>P(G)</tex>, что корректность поиска вызывает обеспокоенность в отношении правильности работы Дейкстры на <tex>P(G) поддерживается </tex>. Возобновление A* приводит к изменениям в случае допустимой эвристической оценкиструктуре <tex>P(G)</tex>. После этого Таким образом, после возобновления A*, мы покажем, что изменения в обновляем <tex>P(G) могут помешать завершенности </tex> и проверяет статус поиска Дейкстры независимо от того(строка 15). В основном, A* может добавить новые узлы, менять <tex>\delta</tex>-значения существующих узлов или даже удалять узлы. A* может также существенно изменять дерево поиска <tex>T</tex>, является ли эвристика допустимой которое будет в худшем случае разрушать структуру все деревянных куч <tex>H_{T}</tex>. Эти изменения могут приводить к глобальной реструктуризации или даже монотоннойперестроению <tex>P(G)</tex> с нуля. СледовательноВ худшем случае это может сделать предыдущие поиски Дейкстры на <tex>P(G)</tex> бесполезными таким образом, мы предложим механизм для её поддержаниячто нам придется перезапускать алгоритм Дейкстры с нуля.
Мы фокусируемся дальше на корректности поиска Дейкстры на Если использованная эвристическая оценка допустимая, то наше положение лучше. Нам по-прежнему может понадобится перестроение <tex>P(G) в случае допустимой эвристической оценки. Сначала</tex>, но мы заявляемпокажем, что если h допустимая, то узлы исследованной части это перестроение не мешает корректности поиска Дейкстры на <tex>P(G) </tex>. Другими словами, мы не поменяют свои \delta-значениятеряем результаты, до сих пор полученные поиском Дейкстры.
Лемма 6. Пусть n будет произвольным узлов В случае монотонной эвристической оценки мы даже не нуждаемся в восстановлении или перестроении <tex>P(G) и пусть (u,v) будет ребром, связанным с n</tex>. Если <tex>h допустимая функция</tex> монотонная, то значение дерево поиска A* является деревом кратчайшего пути для всех раскрытых вершин. Следовательно, g-значения раскрытых вершин не меняются. Это означает, что <tex>\delta</tex>-значения для внутренних ребер никогда не изменятся. Ребра дерева раскрытых вершин не изменятся также. Следовательно, обновление <tex>\delta</tex>-значений, heaping-up, heaping-down (u,vоперации в кучах) никогда или удаление узлов не изменится после тоговлекут за собой каких-либо изменений в <tex>P(G)</tex>. Только добавление новых узлов приводит к изменениям в <tex>P(G)</tex>. Следовательно, как n будет рассмотрен алгоритмом Дейкстрывосстановление или глобальное перестроение не требуется в данном случае.
Из леммы 6 Мы фокусируемся дальше на корректности поиска Дейкстры на <tex>P(G)</tex> в случае допустимой эвристической оценки. Сначала, мы может вывести следующее следствиезаявляем, что если <tex>h</tex> допустимая, то узлы исследованной части <tex>P(G)</tex> не поменяют свои <tex>\delta</tex>-значения.
Следствие 2. {{Лемма|about=6|statement=Пусть <tex>n </tex> будет произвольным узлов в <tex>P(G)</tex> и пусть <tex>(u,v)</tex> будет ребром, связанным с <tex>n</tex>. Если <tex>h </tex> допустимая функция, то n значение <tex>\delta(u, v)</tex> никогда не будет удален из P(G) изменится после того, как <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=...}}
Лемма 7. Пусть n будет произвольным узлов в Более того, мы докажем, что структура исследованной части <tex>P(G). Если h допустимая функция, то n никогда </tex> не изменит свою позицию после того, как он был рассмотрен алгоритмом Дейкстрыизменится.
Леммы 6 и 7 обеспечивают, что изменения в P(G), которые индуцируются A*, не влияют на часть P(G), которую алгоритм Дейкстры уже исследовал. Это гарантирует корректность поиска Дейкстры на P(G), если используемая эвристика допустимая. Таким образом, каждый путь, который предоставляет алгоритм Дейкстры корректен и его длина действительна. Однако, это не обеспечивает завершенность поиска Дейкстры на P(G).
ВозможноЛеммы 6 и 7 обеспечивают, что узел n' присоединяется к другом узлу n как ребенокизменения в <tex>P(G)</tex>, которые индуцируются A*, после раскрытия узла nне влияют на часть <tex>P(G)</tex>, которую алгоритм Дейкстры уже исследовал. В этом случае братья n' будут рассотрены до тогоЭто гарантирует корректность поиска Дейкстры на <tex>P(G)</tex>, как n' станет ребенком nесли используемая эвристика допустимая. Поэтому мы должны рассмотреть тоТаким образом, что было упущено во время поиска в связи с отсутствием n'. Мы добиваемся этого путем применения строк 20-22 к n' для каждого раскрытого направленного predecessor-а узла n'. Если n' ещё не выполняет условие планированиякаждый путь, A* будет неоднократно возобновляться пока механизм планирования не допустит алгоритму который предоставляет алгоритм Дейкстры положить n' в поисковую очередькорректен и его длина действительна. ЗаметимОднако, что таким образом это не требуется каких-либо дополнительных усилий во время типичного обеспечивает завершенность поиска Дейкстрына <tex>P(G)</tex>.
Мы может быть увереныВозможно, что нерассмотренные узлы не будут принудительно опущены узел <tex>n'</tex> присоединяется к другом узлу n как ребенок, после применения операции heaping-up к раскрытия узла <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> в поисковую очередь. Однако, это противоречение к лемме 7, которая гарантируетЗаметим, что этого таким образом не произойдеттребуется каких-либо дополнительных усилий во время типичного поиска Дейкстры.
Более тогоМы может быть уверены, следующее следствие гарантируетчто нерассмотренные узлы не будут принудительно опущены после применения операции heaping-up к <tex>n'</tex>. Иначе, мы могли бы иметь узел <tex>n''</tex>, который являлся бы ребенком n и впоследствии был бы заменен узлом <tex>n'</tex>. Заметим, что наилучшее d(<tex>n') не лучше'</tex> должен быть рассмотрен, чем d-значение любой рассмотренной вершиныпоскольку <tex>n'</tex> был раскрыт. Однако, в частностиэто противоречение к лемме 7, раскрытой вершины. Это означаеткоторая гарантирует, что мы этого не упустим возможность раскрыть n'произойдет.
Следствие 3. Пусть Более того, следующее следствие гарантирует, что наилучшее <tex>d(n будет узлом в P(G')</tex> не лучше, который был раскрыт Дейкстрой. Кроме того, пусть m будет узломчем <tex>d</tex>-значение любой рассмотренной вершины, который заново добавляется в P(G) или его позиция измененачастности, после того как n был раскрытраскрытой вершины. Если h допустимая, тогда выполяется следующее:C_{P(G)}(RЭто означает,m) что мы не упустим возможность раскрыть <tex>= d(n)'</tex>.
→4.5 Взаимосвязь алгоритмов Дейкстры и A*
Также как и алгоритм EppsteinЭппштейна, K* выполняет поиск пути на графе <tex>G </tex> и использует граф путей <tex>P(G)</tex>. Граф путей ищется с помощью алгоритма Дейкстры для того, чтобы вычислить пути <tex>s-t </tex> в виде последовательности запасных путей. Общий принцип работы алгоритма K* следующий:1) K* применяет A* на графе G вместо обратного алгоритма Дейкстры, который использует алгоритм Eppstein.2) Мы запускаем A* на G и Дейкстру на P(G) поочередно порядке, который позволяет Дейкстре доставить пути решение до заверешения поиска на G алгоритма A*.
== 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) </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.Входящая куча H_{in}(v) содержит узлы для каждого запасного ребра к вершине v, которые до сих пор были обнаружены A*. Узлы H_{in}(v) будут упорядочены в соответствии с \delta-значением соответствующих переходов. Узел владеющий ребром с минимальной стоимостью ущерба будет расположен на вершине кучи. Мы ограничим структуру кучи H_{in}(v) таким образом, что её корень в отличие от остальных узлов, имеет не более 1 ребенка. Мы обозначим его root_{in}(v).
[[Файл:kstar-figure-4.png|600px|thumb|center|'''Рисунок 4.''' Входящие кучи <tex>H_{in}(s_i)</tex>, полученные из графа, показанного на рисунке 3.]] Деревянная куча <tex>H_{T}(v)</tex> для произвольной вершины <tex>v</tex> строится следующим образом. Если <tex>v</tex> - стартовая вершина, т.е. <tex>v = s</tex>, то <tex>H_{T}(v)</tex> будет изначально пустой кучей. Затем в неё будет добавлен <tex>root_{in}(s)</tex>, если <tex>H_{in}(s)</tex> не пустая. Если <tex>v</tex> не стартовая вершина, то пусть вершина <tex>u</tex> будет родителем вершины <tex>v</tex> в дереве поиска <tex>T</tex>. Мы можем представить, что <tex>H_{T}(v)</tex> конструируется как копия <tex>H_{T}(u)</tex>, в которую добавлен <tex>root_{in}(v)</tex>. Если <tex>H_{in}(v)</tex> пустая, то <tex>H_{T}(v)</tex> идентична <tex>H_{T}(u)</tex>. Однако, для экономии памяти мы создаем только дешевую копию <tex>H_{T}(u)</tex>. Это осуществляется через создание копий только тех узлов кучи, которые лежат на обновленном пути в <tex>H_{T}(u)</tex>. Оставшаяся часть <tex>H_{T}(u)</tex> не копируется. Другими словами, <tex>root_{in}(v)</tex> вставляется в <tex>H_{T}(u)</tex> неразрушающим путем так, что структура <tex>H_{T}(u)</tex> сохраняется. В куче <tex>H_{T}(v)</tex> к <tex>root_{in}(v)</tex> могут быть присоединены 1 или 2 ребенка. К тому же, <tex>root_{in}(v)</tex> хранит только 1 собственного ребенка из <tex>H_{in}(v)</tex>. Мы обозначим корень <tex>H_{T}(v)</tex> как <tex>R(v)</tex>. [[Файл:kstar-figure-5.png|600px|thumb|center|'''Рисунок 5.''' Деревянные кучи <tex>H_{T}(s_i)</tex>, полученные из графа, показанного на рисунке 3.]] Назовем ребра, которые берут начало из входящих или деревянных куч, '''кучными ребрами''' (англ. ''heap edges''). Сформулируем следующую лемму.{{Лемма|about=1|statement=Все узлы, достижимые из <tex>R(v)</tex> по кучным ребрам, для каждой вершины <tex>v</tex> формируют тернарную кучу, упорядоченную в соответствии с <tex>\delta</tex>-значением. Мы назовем такую кучу '''графовой кучей''' (англ. ''graph heap'') вершины <tex>v</tex> и обозначим её как <tex>H_{G}(v)</tex>.|proof=Те узлы, которые находятся в <tex>H_{T}(v)</tex> или во входящей куче, на которую ссылается узел из <tex>H_{T}(v)</tex>, достижимы по кучным ребрам из <tex>R(v)</tex>. Деревянная куча <tex>H_{T}(v)</tex> формируется через добавление корней входящих куч всех вершин, лежащих на пути из стартовой вершины <tex>s</tex> до <tex>v</tex> в бинарной куче. Каждый из этих корней имеет максимум 3 детей: до 2 в <tex>H_{T}(v)</tex> и дополнительно единственного из входящей кучи. Любой другой узел, живущий во входящей куче имеет не больше 2 детей. Напомним, что каждая входящая куча - это бинарная куча с ограничением, что корень имеет единственного ребенка. Древовидная структура <tex>H_{G}(v)</tex> непосредственный результат древовидных структур <tex>H_{T}(v)</tex> и входящих куч. Более того, кучная характеристика деревянной кучи обеспечивает упорядочивание в соответствии с <tex>\delta</tex>-значением по ребрам из <tex>H_{T}(v)</tex>, а кучная характеристика входящих куч - по всем ребрам из <tex>H_{in}</tex>. Все это приводит к тому, что <tex>H_{G}(v)</tex> - тернарная куча, упорядоченная в соответствии с <tex>\delta</tex>-значением.}} Финальная структура <tex>P(G)</tex> получется из входящих и деревянных куч следующим образом. К каждому узлу <tex>n</tex> из <tex>P(G)</tex>, несущему ребро <tex>(u,v)</tex>, мы присоединим указатель, ссылающийся на <tex>R(u)</tex>, который является корневым узлом <tex>H_{T}(u)</tex>. Мы назовем такие указатели '''кросс-ребрами''' (англ. ''cross edges''), в то время как указатели, возникающие из куч названы кучными ребрами, как упоминалось раньше. Более того, мы добавим специальный узел <tex>\mathrm{R}</tex> в <tex>P(G)</tex> с одним выходящим кросс-ребром к <tex>R(t)</tex>. Более того, мы определим весовую функцию <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>.
...
{{Лемма |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> кратчайших путей.
В оставшейся части этого раздела, мы сначала покажем, что корректность поиска Дейкстры на <tex>P(G)</tex> поддерживается в случае допустимой эвристической оценки.После этого мы покажем, что изменения в <tex>P(G)</tex> могут помешать завершенности поиска Дейкстры независимо от того, является ли эвристика допустимой или даже монотонной.Следовательно, мы предложим механизм для её поддержания.
{{Лемма|about=7|statement=Пусть <tex>n</tex> будет произвольным узлов в <tex>P(G)</tex>.Если <tex>h</tex> допустимая функция, то <tex>n</tex> никогда не изменит свою позицию после того, как он был рассмотрен алгоритмом Дейкстры.|proof=...}}
{{Лемма|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.
