Алгоритм поиска проезда на общественном транспорте

Question

[dobeer]

Подскажите метод (алгоритм) или ссылки по теме поиска проезда на общественном транспорте. Имеется в БД список остановок автобусов (троллейбусов, трамваев), у каждой остановки имеются координаты, список маршрутов проходящих через нее, также имеется в БД список самих маршрутов и координаты линий (координаты точек описывающих линию маршрута). Как реализовать поиск маршрута (с учетом возможных пересадок) по аналогии с 2ГИС или Яндекс карт?

Answer 1

[dobeer]

Спасибо за ответы, надо курить алгоритм поиска A*

Answer 2

[cat_crash]

Пытался решить данную задачу алгоритмом прохождения графа, перебирая каждую остановку и ищя смежные маршруты. Например на остановке 1 есть марршруты A,B,C; на остановке 2 C,Z,K. Значит от остановки 1 до остановки 2 можно добраться маршрутом C. Для «пересадок» делал рекурсивный обход остановок каждого из маршрутов начальной оставки.
НО как показала практика — алгоритм ООООЧЕНЬ тормозной и генерит много запросов. Уверен что есть более правильные алгоритмы

Comments

[cat_crash]

Вот нашел хорошую подборку аналитики по этому вопорсу ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D1%83%D1%82%D0%B8

Answer 3

[DanielWolf]

Поиск по графу?
из влгоритмов — A*, MST, TSP

Answer 4

[dobeer]

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

Answer 5

[mresc]

У нас в системе резервирования Twiton.com пересадки для автобусных линий перебором считаются, все маршруты в память грузятся в древовидную структуру и перебираются. Более эфективные алгоритмы не пошли т.к. пользователи могут при поиске маршрута задавать макс. время ожидания на пересадке.