Разработка алгоритмов для применения в больших сетях: различия между версиями

Альтернативная техника иерархической декомпозиции под названием иерархии магистралей была предложена в [7]. Этот подход использует свойство изначально присущих системе иерархий, которым обладают дорожные сети материального мира, и вычисляет иерархию более крупноблочных представлений входного графа. Затем алгоритм поиска кратчайших путей рассматривает главным образом именно эти крупноблочные представления, размер которых намного меньше, что способствует значительному сокращению времени выполнения запроса. Пересмотр и улучшение этого метода были произведены в работе [8]. Мощное сочетание иерархии магистралей с идеями из статьи [3] было рассмотрено в [2].

Ответы на запросы о кратчайших путях в большим графам требуются в множестве различных приложений, в частности, в системах управления информацией о дорожном движении, работающих по вышеупомянутому сценарию: центральный сервер должен максимально быстро отвечать на большое число запросов от клиентов в реальном времени, которым необходим лучший путь или оптимальный маршрут. Среди других вариантов применения этого сценария можно упомянуть системы планирования маршрутов для автомобилей, велосипедистов и туристов-пешеходов; системы общественного транспорта с информацией о графике транспортных средств на маршруте (например, поездов или автобусов); ответы на запросы в пространственных базах данных и Интернет-поиск. Все эти примеры относятся к системам реального времени, в которых пользователи постоянно задают вопросы для поиска лучшего подключения или маршрута. Поэтому основной целью является сокращение (среднего) времени выполнения запроса.

Код, используемый в [6, 11], доступен на сайте http://doi.acm.org/ 10.1145/351827.384254.

Код, используемый в [3], доступен на сайте http://www. avglab.com/andrew/soft.html.