[Из песочницы] Поиск кратчайшего пути в транспортном графе (концепт) + исходники
Был как-то проект у меня, который был связан с картой города. И возникла идея, что раз есть карта с маршрутами и соответствующими остановками городского транспорта, то почему бы не сделать поиск пути из пункта А в пункт Б на ней. Так как железо, где предполагалось размещать софт, имеет крайне узкий канал интернета, то поиск должен был бы полностью осуществляться локально, то есть без привлечения мощностей сервера. Кроме того, конечно же, хотелось не потерять внимание пользователя и выдать ему результат как можно быстрее. Где-то около часа или двух я сидел и не мог ничего придумать, а потом появилась идея, что я могу рассматривать маршрут, не как множество остановок, а как 1 точку. И если я сверну маршруты в точку, то я получу очень простой граф. Идея показалось неплохой, и мне понравилась. Первое что сделал это запарсил с сайтов маршруты транспорта. Далее принялся за граф. Это оказалась не сложная задача, берем каждую остановку маршрута и смотрим, нет ли остановок любого другого маршрута в заданном нами радиусе. Радиус взял 600 м (в последней версии 400 м) — предполагаемое расстояние, которое человек может пройти безболезненно пешком от одной остановки до другой в случае необходимости пересадки. Вероятно, это расстояние можно сократить, скажем, до 200 м, так как расстояние от одной остановки до другой на перекрестке не превышает эту дистанцию. Итак, после всех этих манипуляций я получил граф, по которому достаточно быстро можно построить путь от одного маршрута к другому. Таким образом, получился граф, который хранит информацию о переходах с одного маршрута городского транспорта на другой, эдакий, мета-граф. За несколько месяцев алгоритм переписывался пару раз, далее поподробнее расскажу о последней реализации. Качество видео ужас, но как сделать получше я так и не обнаружил. Усредненное время, затрачиваемое на выполнение шагов: gpt — 0.009с, найти ближайшие остановки к точке клика grt — 0.001с, найти кратчайший путь от маршрута к маршруту apt — 0.0001с, добавляем остановки и точки поворота к нашему маршруту all — 0.01c, суммарное время выполнения поиска путиЧитать дальше →
