Участник:Kabanov
4 Алгоритм K* Также как и алгоритм Eppstein, K* выполняет поиск пути на графе G и использует граф путей P(G). Граф путей ищется с помощью алгоритма Дейкстры для того, чтобы пути s-t в виде последовательности запасных путей. Общий принцип работы алгоритма K* следующий: 1) K* применяет A* на графе G вместо обратного алгоритма Дейкстры, который использует алгоритм Eppstein. 2) Мы запускаем A* на G и Дейкстру на P(G) поочередно порядке, который позволяет Дейкстре доставить пути решение до заверешения поиска на G алгоритма A*.
4.1 Поиск A* на G. K* применяет A* к входному графу G для того, чтобы определить дерево поиска T. В отличие от алгоритма Eppstein в K* A* применяется к графу G в прямом порядке из-за чего коренем дерева T является вершина s. Это необходимо для того, чтобы была возможность работать c неявным описанием графа G через функцию successor. На протяжении статьи будем считать граф G конечным, если не будет сказано иначе. Заметим, что А* корректен на конечных графах. Будем следовать литературному соглашению, предполагая, что стоимость бесконечного пути неограниченна.
4.2 Стоимость объезда Для ребра (u, v) стоимость объезда \delta(u, v) является стоимостью ущерба из-за взятия ребра объезда (u, v) в сравнении с кратчайшим путем s-t через v. Ни длина кратчайшего пути s-t через v, ни длина пути s-t, включающего запапасные ребра (u, v) не известны, когда A* обнаруживает (u, v). Обе длины могут быть оценены с помощью функции оценки f, которая использует эвристическую функцию h. Путь f(v) будет f-значением с соответствии с деревом поиска T и f_u(v) будет f-значанием в соответствии с родителем u, т.е. f_u(v) = g(u) + c(u, v) + h(v). \delta(u, v) может быть определена так:
\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)
Заметим, что \delta(u, v) дает точную объездную метрику, поскольку функция оценки h-значения не появляется в определении функции \delta(u, v).
4.3 Структура графе путей Структура графа путей P(G) довольно сложная. В принципе, P(G) будет ориентированным графом, вершины которого соответствуют ребрам в исходном графе G. Он будет организован как коллекция взаимосвязанных куч (англ. heap). 2 бинарные минимальные кучи присвоены к каждой вершине v в графе G, которые называются входящей кучей H_{in}(v) и деревянной кучей H_{T}(v). Эти кучи являются базисом P(G). Как мы покажем далее, испльзование этих куч также играет главную роль в поддержании асимптотической сложности K*, также как в EA и LVEA. Входящая куча H_{in}(v) содержит узлы для каждого запасного ребра к вершине v, которые до сих пор были обнаружены A*. Узлы H_{in}(v) будут упорядочены в соответствии с \delta-значением соответствующих переходов. Узел владеющий ребром с минимальной стоимостью ущерба будет расположен на вершине кучи. Мы ограничим структуру кучи H_{in}(v) таким образом, что её корень в отличие от остальных узлов, имеет не более 1 ребенка. Мы обозначим его root_{in}(v).
Деревянная куча H_{T}(v) для произвольной вершины v строится следующим образом. Если v - стартовая вершина, т.е. v=s, то H_{T}(v) будет изначально пустой кучей. Затем узел в неё будет добавлен root_{in}(s), если H_{in}(s) не пустая. Если v не стартовая вершина, то пусть вершина u будет родителем вершины v в дереве поиска T. Мы можем представить, что H_{T}(v) конструируется как копия H_{T}(u), в которую добавлен 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). К тому же, root_{in}(v) хранит только 1 собственного ребенка из H_{in}(v). Мы обозначим корень H_{T}(v) как R(v).
Обратимся к ребрам, которые берут начало из входящих или деревянных куч, как к кучным ребрам. Сформулируем следующую лемму. Лемма 1. Все узлы, которые достижимы из R(v) через кучные ребра для каждой вершины v, формируют тернарную кучу, упорядоченную в соответствии с \delta-значением. Мы назовем такую кучу графовой кучей вершины v и обозначим его как H_{G}(v).
...
Финальная структура P(G) получется из входящих и деревянных куч следующим образом. К каждому узлу n из P(G), несущему ребро (u,v), мы присоединим указатель, ссылающийся на R(u), который является корневым узлом H_{T}(u). Мы назовем такие указатели кросс-ребрами, в то время как указатели, возникающие из куч названы кучными ребрами, как упоминалось раньше. Более того, мы добавим специальный узел R в P(G) с одним выходящим кросс-ребром к R(t).
Более того, мы определим весовую функцию \Delta на ребрах из P(G). Пусть (n, n') обозначает ребро в P(G), и пусть e и e' обозначают ребра из G соответствующие узлам n и n'. Тогда определим \Delta(n,n') следующим образом:
\Delta(n,n')=\delta(e') - \delta(e) если (n,n') кучное ребро \Delta(n,n')=\delta(e') если (n,n') кросс-ребро.
Лемма 1 подразумевает, что куча упорядоченная в соответствии с \delta-значанием поддерживается по любому кучному ребру из P(G). Эта упорядочивание кучи подразумевает, что \Delta(n,n') неотрицательна для любого кучного ребра (n,n'). Следовательно, \Delta также неотрицательна, т.е. \Delta(n,n') >= 0 для любого ребра (n,n') в P(G). Стоимость пути \sigma, т.е. C_{P(G)}(\sigma) равна \sum_{e \in \sigma}\Delta(e).
...
Лемма 2. Пусть n будет узлов графовой кучи H_{G}(w) для какой-нибудь вершины w. Пусть (u,v) будет ребром связанным с n. Тогда существует путь в дереве поиска T из v в w.
...
4.4 Алгоритмическая структура K* Алгоритмический принцип K* следующий. Будем запускать алгоритмы Дейкстры и A* на G с чередованием. Сначала, мы запустим A* на G пока вершина t не будет выбрана из очереди для рассмотрения. Затем, вы запустим алгоритмы Дейкстры на доступной части P(G). Каждый узел рассмотрел Дейкстрой представляет путь решения. Если точнее, то путь \sigma в P(G), по которому Дейкстра достигла этого узла является решением. Путь s-t может быть построен из \sigma за линейное время путем вычисления последовательности запасных ребер seq(\sigma) и затем s-t пути из неё. Если Дейкстра находит k кратчайших путей, то K* завершается успешно. Иначе, A* возобновляется для исследования большей части G. Это приводит к росту P(G), на котором алгоритм Дейкстры затем будет возобновлен. Мы будем повторять этот процесс до тех пор, пока алгоритм Дейкстры не найдет k кратчайших путей. Алгоритм 1 содержит псевдокод K*. Код с 8 по 25 строчку образует главный цикл K*. Цикл завершается, когда очереди обоих алгоритмов А* и Дейкстры пусты. До 8 строчки выполняет некоторые подготовительные вещи. После инициализации, А* запускает на 5 строчке пока вершина t не будет выбрана им для рассмотрения, в этом случае кратчайший путь s-t будет найден. Если t не достигнута, то алгоритм завершается без решения. Отметим, что он не завершится на бесконечных графах. Иначе, алгоритм добавляет специальную вершину R, которая назначена корнем P(G), в поисковую очередь алгоритма Дейкстры. Затем, K* входит в главный цикл. K* поддерживает механизм планирования для контролирования, когда A* или Дейкстра будет возобновлены. Если очередь из A* не пуста, что означает, что А* ещё не завершил исследования всего графа G, то Дейкстра возобновляется тогда и только тогда, когда g(t) + d <= f(u). Значение d является максимальным d-значением среди всех successor-ов головы поисковой очереди n алгоритма Дейкстры. Вершина u является головой поисковой очереди A*. Напомним, что d - функция расстояния, используемая в алгоритме Дейкстры.
