методики, например методика “ограничения угла”, не могут быть при-
менены. Поскольку в оригинальной реализации информация о ребрах
графа вообще не хранится в системе.
В качестве альтернативы разработаны несколько техник ускорения,
используемых в системе. Метод
пересадочного подграфа
заключается
в выделении потенциальных узлов пересадки. В процессе загрузки ис-
ходных данных о расписаниях можно анализировать указанные в рас-
писании маршрута станции и определять потенциальные узлы пере-
садки. Разработаны несколько критериев, на основе которых станция
добавляется в пересадочный подграф. Техника
пересадочный подграф
схожа с техникой
иерархического поиска
, но в отличие от последней
пересчет пересадочного подграфа проводится очень быстро. Еще один
очень эффективный метод
балансировка двунаправленным поиском
за-
ключается в особом выборе прямого или обратного поиска на каждом
шаге итерации. Разработан также метод
ускорения последней итера-
ции
. Для каждой станции вычисляется ограничивающий прямоуголь-
ник станций, достижимых без пересадок. На последнем шаге ите-
рации используется информация об ограничивающем прямоугольнике
каждой станции для выяснения, может ли станция быть пересадочным
пунктом или ее заведомо можно исключить. Еще один эффективный
метод ускорения, хотя и не являющийся точным, — это метод
ускоре-
ния
А
∗
, основанный на эвристическом алгоритме
А
∗
. Хотя алгоритм
А
∗
в данной задаче не является методом, сохраняющим расстояния,
но на практике почти всегда оказывается точным.
Данные о наличии свободных мест — наиболее быстро обновляю-
щаяся часть транспортной информации. Если пропускная способность
канала связи с автоматизированными системами ограничена, а объем
данных велик, то физически невозможно импортировать актуальную
информациюо наличии свободных мест из автоматизированных си-
стем. Поэтому проверка наличия мест проводится на последнем шаге
работы алгоритма, в тот момент когда уже найден оптимальный путь
проезда по остальным критериям.
Разработанный алгоритм положен в основу информационно-спра-
вочной системы.
Архитектура и принципы построения автоматизированной
информационно-справочной системы.
Разработанная информаци-
онно-справочная система — это целый комплекс программ и про-
граммных модулей, которые обеспечивают ее функционирование [11].
Программный комплекс включает следующие программные компо-
ненты.
1. Специализированная база данных геоинформации и расписаний.
2. Средства подготовки данных для информационно-справочной
системы.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 4 105
