Перечислим некоторые ускоряющие подходы, которые позволя-
ют повысить производительность алгоритма поиска. При применении
техники
ограничение угла
используют информацию о пространствен-
ном расположении географических объектов. На этапе
препроцессинга
(предварительной обработки данных) применяют алгоритм Дейкстры,
чтобы вычислить кратчайшие пути из узла до всех других станций [6].
Результаты вычислений не сохраняются, так как это потребовало бы
слишком много места, но сохраняются два значения углов
a
(
v, w
)
и
b
(
v, w
)
, которые сопоставляются ребру графа. Эти значения вычисля-
ются и хранятся в системе для каждого ребра. Углы рассчитываются
следующим образом. Пусть
(
v, w
)
— ребро, соединяющее событие
v
c другим событием
w
на время–расширенном графе, и пусть
S
v
и
S
w
— станции, к которым принадлежат эти события. Нарисуем угловой
сектор между углами
a
(
v, w
)
и
b
(
v, w
)
с вершиной в точке
S
v
. Углы
a
и
b
определяются таким образом, что конечные точки кратчайших
путей, проходящих через ребро, будут внутри сектора. Позднее, во
время работы алгоритма ребра
(
v, w
)
могут быть проигнорированы
поиском, если целевой узел не входит в угловой сектор. Алгоритм
является точным, но требует предварительной обработки данных.
Основная идея другой техники
выбора станций
применяется при
планировании маршрута на транспорте [7]. В результате число рас-
сматриваемых узлов может уменьшиться в несколько раз. Пусть
G
= (
V, E
)
означает маршрутный граф;
V
∼
— набор выбранных
узлов, из которых строится вспомогательный граф
G
∼
. Вспомога-
тельный граф
G
и веса ребер создаются и задаются только один
раз на этапе препроцессинга. После этого любой запрос может быть
обработан на вспомогательном графе
G
, и путь будет соответство-
вать кратчайшему пути на графе
G
. Техника
поиск в направлении
цели
использует потенциальнуюфункциюнабора узлов. Веса ребер в
очереди изменяются так, чтобы направить поиск по графу в сторону
цели. Пусть
λ
— эта потенциальная функция. Новый вес ребра
(
v, w
)
определяется как
l
(
v, w
) =
l
(
v, w
)
−
λ
(
v
) +
λ
(
w
)
.
Двунаправленный поиск
, ускоряющий алгоритм Дейкстры, может
быть успешно применен и для графа транспортных маршрутов. Пря-
мой алгоритм Дейкстры ищет из узла отправления, а обратный — из
узла прибытия.
Иерархический поиск
требует препроцессинга, во время которого
исходный граф
G
= (
V, E
)
разбивается на несколько уровней
(
l
+ 1)
и дополняется дополнительными кратчайшими путями между опреде-
ленными узлами [8]. Чтобы найти кратчайший путь между узлами с
помощьюалгоритма Дейкстры достаточно рассмотреть меньший под-
граф многоуровневого графа. Еще одна интересная техника использует
понятие
радиуса достижения
. Если
v
— вершина на кратчайшем пути
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 4 103
