Клуб API Карт

Заголовок не указан

Jonstonrich
3 августа 2012, 13:24

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

Есть база остановок и маршрутов городского транспорта.Каждый номер маршрута занесен как две записи в таблице mysql.Вернее несколько таблиц связанные между собой внешними ключами отношением многие ко многим.Эти два маршрута - это как бы один но с 2 направлениями туда и обратно.Так вот.Клиент выбирает две произвольные точки на карте в пределах города после чего кликает проложить маршрут.Далее вступает сам алгоритм.Сначала скрипт ищет 10 близжайших точек по отношению к той что пользователь поставил первой (точка "От") с учетом разных маршрутов.Далее в цикле скрипт оббегает эти точки и выбирает близжайщие точки по отношению к точке "До" но уже с условием что точка принадлежит к тому маршруту итерация которой производится сейчас, причем  нужно понимать что скрипт может выбрать маршрут который движется в противоположном направлении нужного пользователю поэтому дополнительно проверяется что бы точка "До" имела id связи больше чем точка "От" (При составлении маршрута точки записываются по возрастанию от начала до конца).

Я все правильно рассчитал или все сделаю а потом какой то косяк и все заново?

3 комментария
Подписаться на комментарии к посту
Ну, для начала нужно определить метрику.
У вас есть:
- расстояние, которое нужно пройти пешком до начальной остановки
- время проезда
- количество пересадок
- расстояние, которое придётся пройти пешком от конечной остановки.

В зависимости от метрики будет меняться алгоритм.
Что касается просто поиска пути из одной вершины графа до другой, то посмотрите алгоритм Дейкстры.

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

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

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

jonstonrich , а насколько велика база данных остановок? Для 1 или нескольких городов? Можно увидеть ваш результат в действии?