Визуализация алгоритмов построения маршрутов показывает как A* для жилых домов Москвы может расчитываться день
В прошлых публикациях на Хабре я находил все жилые дома в пешей доступности от входов в метро и МЦК и жилье в 500 м от сетевых продуктовых магазинов в Москве.
Когда настал момент объединить все метрики для мегаполиса, включая пешеходные расстояния в единую модель. У меня вышло итоговых 36.5 млн кратчайших пешеходных дистанций на расстояния до 2 км в городе, не считая тех что отбросил при расчетах. И это только для домов поблизости от метро. Написал многопоточный код и перепробовал множество оптимизаций для чтения исходных домов + точек интереса, записи в базу маршрутов. Эти части программы в итоге завершались за несколько минут, а производительность упиралась в GraphHopper.
Я попопробовал роутинг «многие ко многим» с помощью алгоритма Дейкстры. Этот эксперимент показал что на дорожной сети Москвы он выполнялся медленнее поиска маршрута 1:1 в цикле для тех же начальных и конечных точек. В радиусе 2500 м каждое пешеходное расстояние вычислялось на моем ноутбуке около миллисикунды. Расстояния «на сфере» Земли в базе данных рассчитались за 2.5 минуты для 1.4 млн. дистанций в радиусе 500 м. Явно что производительность расчета расстояния по прямой и на графе дорог различается на порядки.
Когда пытаешься ускорить вычисления забываешь про тот объем вычислений, который выполняет компьютер по программе, чтобы рассчитать маршруты. Почти любой движок маршрутизации это не просто реализация графового алгоритма поиска кратчайшего маршрута с эвристиками, но еще и учет дополнительных факторов из реального мира при построении маршрута и предпочтений пользователя. В GraphHopper можно указать профиль или матрицу весов, программа учитывает общедоступна ли дорога или частная, тип дороги и тп.
И в этот же день в чате OpenStreetMap RU появляется ссылка на проект, который визуализирует алгоритмы поиска кратчайшего маршрута и еще делает анимацию по шагам на реальных данных OSM прямо в браузере. Поделюсь с вами виртуальной прогулкой из Серебряного бора в Большой театр с помощью honzaap/pathfinding. Эта визуализация алгоритма гораздо нагляднее и применимее другого проекта на JavaScript, потому что использует реальные картографические данные из OpenStreetMap и решает не абстрактную задачу, а вполне реальную и делает это зрелищно.
Я иду, шагаю по Москве
Маршрут я выбрал по любимым местам. Маршрут от озера Бездонного до Большого театра это 14 км прогулки на 3 часа:
Старт
Финиш
Как шагают разные алгоритмы
Для этого откроем онлайн версию визуализатора и введем точки маршрута https://honzaap.github.io/Pathfinding/
Первый алгоритм один из самых популярных — это А* алгоритм, графовый алгоритм с эвристикой. На Хабре есть хороший перевод «Введение в алгоритм A*» где рассказывается почему A* быстрее алгоритма Дейкстры.
А* добрался достаточно быстро:
Алгоритм Дейкстры для машрутизации обошел почти четверть Москвы, пока добрался до Большого театра:
Двунаправленный поиск нашел не самый оптимальный маршрут, но обошел меньше улиц чем алгоритм Дейкстры:
Жадный алгоритм быстро нашел как добраться из Серебряного бора в Большой театр
Проект на GitHub
Исходный код доступен https://github.com/honzaap/pathfinding. Для его сборки нужен npm и с помощью vite результат из библиотек и кода собирается в статический html+javascript.
Последняя версия в виде сайта доступна https://honzaap.github.io/Pathfinding/
Алгоритмы могут быть зрелищными
На лекциях по алгоритмам и структурам данных часто монотонный голос лектора нагонял тоску. Но оказывается, если визуально отображать что же происходит в алгоритме на каждом шаге поиска кратчейшего пути в графе, да еще и на данных реального мира, то сразу появляется интерес! Когда сразу видишь задачу которую решает алгоритм и как он это делает. Такие наглядные примеры это именно то, что может заинтересовать учеников.
