Программа поиска кратчайшего пути между улицами

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

Скажите, пожалуйста, что и где почитать по теме? По каким ключевым словам искать ресурсы?

Поиск кратчайшего (в данном случае по времени) пути на графе.

Задача несколько осложняется ожиданием транспорта, учетом расписания.

Цитата MBo @ 06.09.16, 02:55

Поиск кратчайшего (в данном случае по времени) пути на графе.

Задача несколько осложняется ожиданием транспорта, учетом расписания.

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

Поделить улицы на сегменты в точках слияния/разделения и занести всё в таблицу орграфа.

Цитата Subway_ @ 06.09.16, 05:59

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

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

Цитата Akina @ 06.09.16, 06:55

Поделить улицы на сегменты в точках слияния/разделения и занести всё в таблицу орграфа.

Хороший подход, но, имхо, несколько "не с той стороны".

Subway_, не нужно изобретать велосипеды. Проще пройти уже давно используемым методом в картографии - разбить карту города на квадраты. А уже к квадратам привязывать атрибуты, как-то "Список адресов (с улицами и домами) в квадрате" и "Список остановок общественного транспорта". Ну и отдельно уже таблицы маршрутов, расписание движения по маршрутам. Тогда задача значительно упрощается - нужно попасть из квадрата A - в квадрат Б. Далее детализация.

Но нюансов все равно не мало - движение по маршруту достаточно часто предполагает пересадки, и не только в местах одной и той же остановки. Следовательно нужно учитывать и возможность пешего перемещения между остановками (например, вышли из метро и пошли на автобус). Также бывает, что короткий путь - не самый быстрый. Как пример, "перемещение на метро" vs "наземный транспорт".

Цитата JoeUser @ 06.09.16, 07:48

несколько "не с той стороны".

Это ещё почему?
При поиске маршрута, особенно оптимального маршрута, укрупнение приведёт к неустойчивости и возможному пропуску оптимума.

Цитата Akina @ 06.09.16, 07:53

возможному пропуску оптимума.

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

Деление карты на квадраты - лишь позволит ускорить время пересчета, отсекая при переборе заведомо невозможные ветки перебора. Как мы строим путь? Путь, грубо говоря, есть вектор смежных точек, от пункта старта до пункта назначения. Укрупняя точки до квадратов - мы сперва манипулируем "большим", соответственно и отсекаем при расчетах большее.

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

Ну как-то так.

Цитата JoeUser @ 06.09.16, 08:17

Деление карты на квадраты - лишь позволит ускорить время пересчета, отсекая при переборе заведомо невозможные ветки перебора

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

Уж если говорить об оптимизации, то разумнее построить сеть неких "узловых" точек транспортной сети и в первую очередь рассматривать маршруты через них. Это укрупнение действительно может упростить и ускорить расчёты - за счёт предрасчёта времени движения между узлами и повторного использования этих данных.

Цитата Akina @ 06.09.16, 12:24

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

Если не одно "но" ... Тогда нужна привязка всех транспортных точек ко всем адресам города по расстоянию, а это неоптимально. В случае "квадратов" - привязка только к адресам квадрата. Аргументировать смысла нет, очевидно.

Цитата Akina @ 06.09.16, 12:24

Это не так. При делении на квадраты между смежными квадратами неминуемо наличие нескольких "входов-выходов".

Именно так! Наличие свойства смежности квадратов относительно маршрутов позволяет нам выбрать "следующий возможный квадрат" (а возможно и сам себя), но ... выбрав квадрат, мы перебираем точки остановки транспорта единожды (единичное посещение). Это же позволит возможность нам прыгать из маршрута в маршрут.

Пример:

Пусть есть автобусный маршрут A, и метро M. Выберем последовательность смежных квадратов и построим путь.

1[a1] ,2[a2], 3[a3,m1], 4[a4], ... , n[an,mm], n+1[an+1], n+2[an+2], тогда

Пассажир садиться в квадрате 1 на автобус. В принципе, он может спокойно ехать до n+2[an+2]. Но оптимальнее пересесть в квадрате 3 на метро, пошустрику приехать без пробок в n[an,mm], и опять пересесть на тот же маршрут и доехать хвост до n+2[an+2].

И ничего не мешает остановкам a1,a2, ...an быть в одном квадрате - мы же выбираем очередной смежный квадрат пока не обследовали все остановки всех маршрутов в текущем.