The Shortest Path Problem — различия между версиями
Материал из SEWiki
| Строка 1: | Строка 1: | ||
| − | * Студент: Алексей Гуревич | + | * Студент: [[Участник:Alexey.Gurevich|Алексей Гуревич]] |
* Руководитель: Валерий Лесин | * Руководитель: Валерий Лесин | ||
| Строка 24: | Строка 24: | ||
* исследование и реализация алгоритмов "contraction hierarchies" (начало апреля), | * исследование и реализация алгоритмов "contraction hierarchies" (начало апреля), | ||
* исследование и реализация алгоритмов "transit node routing" (начало мая), | * исследование и реализация алгоритмов "transit node routing" (начало мая), | ||
| − | * <возможный этап> слияние с проектом Евгения Баталова (АУ, кафедра SE, 5 курс) с целью создание многопользовательского приложения с web-интерфейсом для поиска кратчайших путей на графе дорог на основе разработанных алгоритмов. (конец мая) | + | * <возможный этап> слияние с [[Shortest_Path_Service|проектом]] [[Участник:Eabatalov89|Евгения Баталова]] (АУ, кафедра SE, 5 курс) с целью создание многопользовательского приложения с web-интерфейсом для поиска кратчайших путей на графе дорог на основе разработанных алгоритмов. (конец мая) |
Ожидаемый результат: | Ожидаемый результат: | ||
* Приложение, реализующее быстрый поиск кратчайших путей между двумя точками на графе дорог. | * Приложение, реализующее быстрый поиск кратчайших путей между двумя точками на графе дорог. | ||
Текущая версия на 02:11, 17 марта 2011
- Студент: Алексей Гуревич
- Руководитель: Валерий Лесин
Описание: Целью проекта является создание приложения, решающего задачу поиска кратчайшего пути между двумя точками на карте дорог. В приложении должны быть реализованы как классические алгоритмы Дейкстры и A-star, так и их наиболее современные быстрые модификации.
Положение на начало весеннего семестра:
- разработана графическая оболочка для тестирования алгоритмов,
- реализованы следующие алгоритмы:
- алгоритм Дейкстры,
- a-star.
- а также их оптимизации на основе:
- использования двунаправленного поиска,
- якорных точек (landmark) - ALT,
- подсчета достижимости (reach) - REAL.
Предполагаемые этапы:
- ускорение алгоритма подсчета достижимости (использование механизма shortcut, распараллеливание вычилений),
- исследование и реализация алгоритмов "contraction hierarchies" (начало апреля),
- исследование и реализация алгоритмов "transit node routing" (начало мая),
- <возможный этап> слияние с проектом Евгения Баталова (АУ, кафедра SE, 5 курс) с целью создание многопользовательского приложения с web-интерфейсом для поиска кратчайших путей на графе дорог на основе разработанных алгоритмов. (конец мая)
Ожидаемый результат:
- Приложение, реализующее быстрый поиск кратчайших путей между двумя точками на графе дорог.
