Поиск Кратчайшего Пути В Транспортном Графе (Концепция) + Исходники

Однажды у меня был проект, связанный с картой города.

И возникла идея, что раз есть карта с маршрутами и соответствующими остановками общественного транспорта, то почему бы не поискать на ней путь из точки А в точку Б.

Поскольку оборудование, на котором должно было находиться программное обеспечение, имеет крайне узкий интернет-канал, поиск пришлось бы полностью осуществлять локально, то есть без привлечения серверных мощностей.

Кроме того, конечно, мне хотелось не потерять внимание пользователя и дать ему результат как можно быстрее.

Где-то час-два я сидел и ничего не мог придумать, а потом появилась идея, что можно считать маршрут не количеством остановок, а 1 точкой.

А если я сверну маршруты в точку, то получу очень простой график.

Идея показалась хорошей, и она мне понравилась.

Первое, что я сделал, это разобрал транспортные маршруты с сайтов.

Затем он принялся за счет. Это оказалось несложной задачей; мы берем каждую остановку на маршруте и смотрим, есть ли остановки на каком-либо другом маршруте в указанном нами радиусе.

Радиус составил 600м (в последней версии 400м) — расчетное расстояние, которое человек может безболезненно пройти от одной остановки до другой, если необходима пересадка.

Вероятно, это расстояние можно сократить, скажем, до 200 м, поскольку расстояние от одной остановки до другой на перекрестке не превышает этого расстояния.

Итак, после всех этих манипуляций у меня получился граф, по которому можно быстро построить путь от одного маршрута к другому.

Таким образом, у нас есть граф, хранящий информацию о переходах с одного маршрута городского транспорта на другой, своего рода метаграф.

В течение нескольких месяцев алгоритм пару раз переписывался; далее расскажу подробнее о последней реализации.

Качество видео ужасное, но как его улучшить я не нашел.

Среднее время, потраченное на выполнение шагов: gpt — 0,009 с, найти ближайшие остановки к точке щелчка grt - 0,001с, найти кратчайший путь от маршрута к маршруту apt - 0,0001 с, добавьте остановки и повороты к нашему маршруту all — 0,01 с, общее время выполнения поиска пути



Данные:

Имеем некую карту города, на которой отмечены маршруты городского транспорта (90 маршрутов) и координаты соответствующих остановок, принадлежащих этим маршрутам.

На карте маршруты выглядят так:

Поиск кратчайшего пути в транспортном графе (концепция) + исходники

Скучное описание структуры базы данных Данные представлены в следующих таблицах: Теги: #алгоритмы поиска #Алгоритмы

Вместе с данным постом часто просматривают: