P
из
s
в
t
, то радиус достижения по отношениюк
P, r
(
v, P
)
есть ми-
нимум от длины префикса
P
(часть пути от
s
к
v
) и длины суффикса
(часть пути от
v
к
t
). Радиус достижения узла
v, r
(
v
)
— это максимум
r
(
v, P
)
по всем кратчайшим путям, которые содержат
v
. Вычислив
предварительно
r
(
v
)
для всех узлов можно использовать эту инфор-
мациюво время работы алгоритма Дейкстры. Техника
прямоугольника
кратчайших узлов
похожа на метод
ограничения угла
. На этапе пре-
процессинга обрабатываются все деревья кратчайших путей. Для ка-
ждого ребра
e
∈
E
вычисляется набор узлов
S
(
e
)
, кратчайшие пути
к которым проходят через ребро
e
, и для каждого
e
∈
E
сохраняет-
ся ограничивающий прямоугольник
S
(
e
)
. Во время работы алгоритма
можно быстро узнать, по какому ребру необходимо двигаться дальше,
исключая “на лету” те ребра, которые не ведут к цели.
Оригинальный алгоритм поиска оптимального пути на пасса-
жирском транспорте.
В разработанной информационно-справочной
системе используется оригинальный алгоритм поиска, который строго
решает двухкритериальнуюзадачу поиска пути с минимальным чи-
слом пересадок и с наискорейшим временем прибытия [9, 10].
На первом этапе проводится оптимистический поиск по виртуаль-
ному графу. В результате находятся все пути с одинаковым минималь-
ным числом пересадок. Найденные пути анализируются на следую-
щем шаге алгоритма, где проверяется допустимость каждого с уче-
том дней курсирования и решается задача наискорейшего прибытия.
Затем среди допустимых путей выбирается оптимальный (наискорей-
ший). Если все пути оказались недопустимы, то повторяется первый
этап поиска по графу. Важно, что поиск по графу должен быть опти-
мистическим (находить все возможные пути с минимальным числом
пересадок) — обеспечивается точностьюалгоритма.
Есть два широко распространенных способа представления графа
G
= (
V, E
)
: как набор смежных вершин или как матрицу смежности.
Но оригинальный алгоритм реализован на встроенном языке базы дан-
ных и адаптирован к работе с таблицами, и граф в явном виде вообще
не хранится в системе. Оригинальный алгоритм оперирует со специ-
ально преобразованными исходными данными. Это позволяет решать
задачу точно, не сводя ее к эвристическим методам. Также преиму-
ществом является то, что в оригинальной реализации не требуется
полного препроцессинга, при изменениях в исходных данных.
Алгоритм Дейкстры, адаптированный к работе с преобразован-
ными данными, также может быть применен для поиска. Но он
не является достаточно быстрым для практической реализации в
информационно-справочной системе. Для ускорения работы ориги-
нального алгоритма применяются специальные техники. Известные
104 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 4
