418
правок
Изменения
Нет описания правки
Также как и алгоритм 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> поочередно в поочередном порядке, который позволяет Дейкстре доставить вычислить требуемые пути решение до заверешения полного поиска алгоритма A* на графе <tex>G</tex> алгоритма A*.
== 4.1 Поиск A* на G. == K* применяет A* к входному графу <tex>G</tex> для того, чтобы определить построить дерево поиска <tex>T</tex>. В отличие от алгоритма Eppstein в K* Заметим, что A* применяется к графу <tex>G</tex> , также как и алгоритм Дейкстры, строит дерево поиска в прямом порядке из-за чего коренем дерева <tex>T </tex> является вершина процессе нахождения кратчайшего пути <tex>s-t</tex>. Это необходимо Эти деревья формируются с помощью ссылок на родительские узлы, которые храняться в том время, как A* производит итерации для того, чтобы была возможность работать c неявным описанием графа восстановить путь <tex>Gs-t</tex> через функцию successor. На протяжении статьи будем считать граф , когда вершина <tex>Gt</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 Стоимость объезда ==Для ребра <tex>(u, v)</tex> стоимость объезда <tex>\delta(u, v)</tex> является стоимостью представляет стоимость ущерба из-за взятия ребра объезда <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>, которые называются входящей кучей <tex>H_{in}(v)</tex> и деревянной кучей <tex>H_{T}(v)</tex>. Эти кучи являются базисом <tex>P(G)</tex>. Как мы покажем далее, испльзование этих куч также играет главную роль в поддержании асимптотической сложности K*, также как в EA и LVEA.
Более того, мы определим весовую функцию <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>.
}}
== 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> кратчайших путей.
Алгоритм 1 содержит псевдокод K*. Код с 8 по 25 строчку образует главный цикл K*. Цикл завершается, когда очереди обоих алгоритмов А* и Дейкстры пусты. До 8 строчки выполняет некоторые подготовительные вещи. После инициализации, А* запускает на 5 строчке пока вершина <tex>t</tex> не будет выбрана им для рассмотрения, в этом случае кратчайший путь <tex>s-t</tex> будет найден. Если <tex>t</tex> не достигнута, то алгоритм завершается без ответа. Отметим, что он не завершится на бесконечных графах. Иначе, алгоритм добавляет специальную вершину <tex>R</tex>, которая назначена корнем <tex>P(G)</tex>, в поисковую очередь алгоритма Дейкстры. Затем, K* входит в главный цикл.
K* поддерживает механизм планирования для контролирования, когда A* или Дейкстра будет возобновлены. Если очередь из A* не пуста, что означает, что А* ещё не завершил исследования всего графа G, то Дейкстра возобновляется тогда и только тогда, когда <tex>g(t) + d <= f(u)</tex>. Значение <tex>d </tex> является максимальным <tex>d</tex>-значением среди всех successor-ов головы поисковой очереди <tex>n</tex> алгоритма Дейкстры. Вершина <tex>u</tex> является головой поисковой очереди A*. Напомним, что <tex>d</tex> - функция расстояния, используемая в алгоритме Дейкстры. Если очередь поиска Дейкстры пуста или <tex>g(t) + d > f(u)</tex>, то А* возобновляется для того, чтобы исследовать более большую часть графа <tex>G</tex> (строка 14). То, как долго мы ему позволим работать, является компромиссом. Если мы запустим его только на маленьком количестве шагов, то мы дадим Дейкстре шанс найти необходимое количество путей скорее, чем они будут доступны в <tex>P(G)</tex>. С другой стороны, мы вызываем накладные расходы путем переключения A* и Дейкстры и поэтому должны ограничить количество переключений. Эти накладные расходы вызваны тем фактом, что после возобновления A* (строка 14), структура графа <tex>P(G)</tex> может измениться. Следовательно нам необходимо обновить <tex>P(G)</tex> (строка 15), как мы будет широко обсуждать в разделе 4.5. Это требует последующую проверку статуса Дейкстры. Мы должны быть уверены, что Дейкстра поддерживает согласованное состояние после изменений в <tex>P(G)</tex>. K* предусматривает условие, которые управляет решением, когда остановить A*, которое мы назовем ''условие расширения''. Для того, чтобы поддерживать аналогичную асимптотическую сложность как у EA и LVEA, мы должны определить условие расширения так, чтобы A* выполнялся пока количество рассмотренных вершин и количество внутренних ребер удваивается или <tex>G </tex> полностью исследован. Мы обсудим эту проблему несколько подробнее позже. В качестве полезного свойства, K* позволяет другое определения этого условия, которое может быть более эффективным на практике. В наших экспериментах в разделе 6, мы определили условие расширения так, что количество рассмотренных вершин или количество рассмотренных ребер ребер возрастает на 20% при каждом запуске A*. Этот механизм планирования включен до тех пор, пока A* не закончит исследовать весь граф <tex>G</tex>. Как только A* исследует весь граф <tex>G </tex> (строка 9), механизм планирования отключается и в дальнейшем работает только алгоритм Дейкстры.
Строки 18-22 представляют обычный шаг рассмотрения узла алгоритмом Дейкстры. Отметим, что когда successor-узел <tex>n'</tex> сгенерирован, K* не проверяет был ли <tex>n'</tex> уже посещен до этого. Другими словами, каждый раз, когда узел генерируется, он рассматривает как новый. Эта стратегия обоснована на наблюдении, что путь s-t может содержать одно и то же ребро несколько раз. Строка 24 добавляет следующий путь <tex>s-t</tex> в результирующее множество R. Это делается путем конструирования последовательности запасных ребер <tex>seq(\sigma)</tex> из пути <tex>\sigma</tex>, через которые Дейкстра достигла узла <tex>n</tex>, который был только что рассмотрен. Алгоритм завершается, когда в результирующее множество добавлено <tex>k</tex> последовательностей запасных ребер (строка 25).
== 4.5 Взаимосвязь алгоритмов Дейкстры и A* ==
Тот факт, что оба алгоритма A* и Дейкстры делят между собой граф путей <tex>P(G)</tex>, вызывает обеспокоенность в отношении правильности работы Дейкстры на <tex>P(G)</tex>. Возобновление A* приводит к изменениям в структуре <tex>P(G)</tex>. Таким образом, после возобновления A*, мы обновляем <tex>P(G)</tex> и проверяет статус поиска Дейкстры (строка 15). В основном, A* может добавить новые узлы, менять <tex>\delta</tex>-значения существующих узлов или даже удалять узлы. A* может также существенно изменять дерево поиска <tex>T</tex>, которое будет в худшем случае разрушать структуру все деревянных куч <tex>H_{T}</tex>. Эти изменения могут приводить к глобальной реструктуризации или даже перестроению <tex>P(G)</tex> с нуля. В худшем случае это может сделать предыдущие поиски Дейкстры на <tex>P(G)</tex> бесполезными таким образом, что нам придется перезапускать алгоритм Дейкстры с нуля.
}}
== 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. Легко заметить, что эвристическая функция допустима.
