The Shortest Path Problem — различия между версиями
Материал из SEWiki
(Новая страница: «* Студент: Алексей Гуревич * Руководитель: Валерий Лесин Описание: Целью проекта является …») |
|||
| Строка 1: | Строка 1: | ||
* Студент: Алексей Гуревич | * Студент: Алексей Гуревич | ||
* Руководитель: Валерий Лесин | * Руководитель: Валерий Лесин | ||
| + | |||
Описание: Целью проекта является создание приложения, решающего задачу поиска кратчайшего пути между двумя точками на карте дорог. В приложении должны быть реализованы как классические алгоритмы Дейкстры и A-star, так и их наиболее современные быстрые модификации. | Описание: Целью проекта является создание приложения, решающего задачу поиска кратчайшего пути между двумя точками на карте дорог. В приложении должны быть реализованы как классические алгоритмы Дейкстры и A-star, так и их наиболее современные быстрые модификации. | ||
| + | |||
Положение на начало весеннего семестра: | Положение на начало весеннего семестра: | ||
* разработана графическая оболочка для тестирования алгоритмов, | * разработана графическая оболочка для тестирования алгоритмов, | ||
* реализованы следующие алгоритмы: | * реализованы следующие алгоритмы: | ||
| − | + | '' - алгоритм Дейкстры, '' | |
| − | + | ||
| + | '' - a-star.'' | ||
* а также их оптимизации на основе: | * а также их оптимизации на основе: | ||
| − | + | '' - использования двунаправленного поиска,'' | |
| − | + | ||
| − | + | '' - якорных точек (landmark) - ALT,'' | |
| + | |||
| + | '' - подсчета достижимости (reach) - REAL.'' | ||
| + | |||
Предполагаемые этапы: | Предполагаемые этапы: | ||
| Строка 19: | Строка 25: | ||
* исследование и реализация алгоритмов "transit node routing" (начало мая), | * исследование и реализация алгоритмов "transit node routing" (начало мая), | ||
* <возможный этап> слияние с проектом Евгения Баталова (АУ, кафедра SE, 5 курс) с целью создание многопользовательского приложения с web-интерфейсом для поиска кратчайших путей на графе дорог на основе разработанных алгоритмов. (конец мая) | * <возможный этап> слияние с проектом Евгения Баталова (АУ, кафедра SE, 5 курс) с целью создание многопользовательского приложения с web-интерфейсом для поиска кратчайших путей на графе дорог на основе разработанных алгоритмов. (конец мая) | ||
| + | |||
Ожидаемый результат: | Ожидаемый результат: | ||
* Приложение, реализующее быстрый поиск кратчайших путей между двумя точками на графе дорог. | * Приложение, реализующее быстрый поиск кратчайших путей между двумя точками на графе дорог. | ||
Версия 01:56, 14 марта 2011
- Студент: Алексей Гуревич
- Руководитель: Валерий Лесин
Описание: Целью проекта является создание приложения, решающего задачу поиска кратчайшего пути между двумя точками на карте дорог. В приложении должны быть реализованы как классические алгоритмы Дейкстры и A-star, так и их наиболее современные быстрые модификации.
Положение на начало весеннего семестра:
- разработана графическая оболочка для тестирования алгоритмов,
- реализованы следующие алгоритмы:
- алгоритм Дейкстры,
- a-star.
- а также их оптимизации на основе:
- использования двунаправленного поиска,
- якорных точек (landmark) - ALT,
- подсчета достижимости (reach) - REAL.
Предполагаемые этапы:
- ускорение алгоритма подсчета достижимости (использование механизма shortcut, распараллеливание вычилений),
- исследование и реализация алгоритмов "contraction hierarchies" (начало апреля),
- исследование и реализация алгоритмов "transit node routing" (начало мая),
- <возможный этап> слияние с проектом Евгения Баталова (АУ, кафедра SE, 5 курс) с целью создание многопользовательского приложения с web-интерфейсом для поиска кратчайших путей на графе дорог на основе разработанных алгоритмов. (конец мая)
Ожидаемый результат:
- Приложение, реализующее быстрый поиск кратчайших путей между двумя точками на графе дорог.
