Лекция, 31 января 2010, 13:00

Автострадная размерность и доказуемо эффективные алгоритмы нахождения кратчайших путей

бесплатно
Описание встречи

Задача о нахождении оптимального маршрута породила множество эвристических алгоритмов, отвечающих на запросы на континентальных картах с десятками миллионов перекрестков в реальном времени с весьма скромными затратами по памяти.

Мы приводим первый теоретический анализ таких алгоритмов на нетривиальном классе графов. С этой целью мы вводим понятие автострадной размерности (highway dimension). Рассматриваемый анализ применим к графам с низкой размерностью и дает единообразное объяснение эффективности нескольких, на первый взгляд различных, алгоритмов.

Посетили
Показать Всех
Смотрите также