realhum/pathfinding

Pathfinding

Программа для построения графа дорог города Кострома на основе данных проекта OpenStreetMap.

Среда разработки: Visual Studio 2017. Используемый язык: C#.

Использование Скачайте любым способом .osm файл с необходимым участком карты, назовите его "map.osm".

Запустите файл "graphs.exe", следуйте инструкциям.

К проекту прикреплены результаты для моего города (Кострома), вводилась точка с координатами LAT=57,8 LON=41.

Чёрным кругом на карте отмечена стартовая точка, ближайшая точка отмечена красным кругом.

Анализ тестирования Проводится тестирование алгоритма на 100 равномерно распределенных точках.

Алгоритм Дейкстры: среднее время выполнения около 6.89 секунд на точку.

Алгоритм Левита: среднее время выполнения около 7.47 секунды на точку.

Алгоритм A*:

С метрикой "Евклидово расстояние": среднее время выполнения около 5.12 секунды на точку.

С метрикой "Манхеттоновское расстояние": среднее время выполнения около 5.97 секунды на точку.

С метрикой "Расстояние Чебышева": среднее время выполнения около 8.03 секунды на точку.

Вывод: Алгоритм Дейкстры имеет сравнимое с алгоритмом Левита среднее время выполнения. Алгоритм A* в зависимости от метрики может показывать лучшее время, чем предыдущие два алгоритма.