The Shortest Path Problem

Материал из SEWiki
Перейти к: навигация, поиск


Описание: Целью проекта является создание приложения, решающего задачу поиска кратчайшего пути между двумя точками на карте дорог. В приложении должны быть реализованы как классические алгоритмы Дейкстры и A-star, так и их наиболее современные быстрые модификации.


Положение на начало весеннего семестра:

  • разработана графическая оболочка для тестирования алгоритмов,
  • реализованы следующие алгоритмы:

- алгоритм Дейкстры,

- a-star.

  • а также их оптимизации на основе:

- использования двунаправленного поиска,

- якорных точек (landmark) - ALT,

- подсчета достижимости (reach) - REAL.


Предполагаемые этапы:

  • ускорение алгоритма подсчета достижимости (использование механизма shortcut, распараллеливание вычилений),
  • исследование и реализация алгоритмов "contraction hierarchies" (начало апреля),
  • исследование и реализация алгоритмов "transit node routing" (начало мая),
  • <возможный этап> слияние с проектом Евгения Баталова (АУ, кафедра SE, 5 курс) с целью создание многопользовательского приложения с web-интерфейсом для поиска кратчайших путей на графе дорог на основе разработанных алгоритмов. (конец мая)


Ожидаемый результат:

  • Приложение, реализующее быстрый поиск кратчайших путей между двумя точками на графе дорог.