Стратегия, чтобы найти свой лучший маршрут только на общественном транспорте?

Question

Найти маршрут для автомобиля довольно легко: вы сохраняете взвешенный график всех дорог, и вы можете использовать алгоритм Джикстры [1]. Автобусный маршрут менее очевиден. С шиной вы должны представлять такие вещи, как «подождите 10 минут до следующей шины» или «пройти один квартал до другой автобусной остановки» и передать их в свой алгоритм поиска пути.

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

Как бы вы эффективно представили этот вид графика, зависящего от времени, и нашли бы маршрут? Нет необходимости доказуемо оптимального решения; если бы путешественник хотел быть вовремя, он купил бы машину. ; -)

[1] Прекрасный алгоритм, который нужно упомянуть в примере, потому что все о нем слышали, хотя A * - более вероятный выбор для этого приложения.

Answer 1

Вы сами отвечаете на вопрос. Используя алгоритм A * или Dijkstra, все, что вам нужно сделать, это выбрать хорошую цену за часть каждого маршрута.

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

Алгоритм поиска наиболее подходящего маршрута остается тем же, что и раньше. С A * все волшебство происходит в функции стоимости ...

Answer 2

Чрезвычайно неэффективный способ, который мог бы работать, состоял бы в том, чтобы хранить копию каждого перекрестка в городе для каждой минуты дня. Автобусный маршрут от ул. Вязов и 2-го до Мейн-стрит и 25-го будет представлен, скажем,

elm_st_and_2nd[12][30].edges :
 elm_st_and_1st[12][35] # 5 minute walk to the next intersection
   time = 5 minutes
   transport = foot
 main_st_and_25th[1][15] # 40 minute bus ride
   time = 40 minutes
   transport = bus
 elm_st_and_1st[12][36] # stay in one place for one minute
   time = 1 minute
   transport = stand still

Запустите ваш любимый алгоритм поиска пути на этом графике и помолитесь за хорошую реализацию виртуальной памяти.

Answer 3

Если бы я занимался этой проблемой, я бы, вероятно, начал с аннотированного графика. Каждый узел на графике будет представлять все перекрестки в городе, независимо от того, останавливается ли там общественная транспортная система - это помогает учесть необходимость ходить и т. Д. На перекрестках с транзитной службой вы отмечаете их метками остановки - метки, позволяющие вам посмотреть расписание обслуживания для остановки.

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

Если вам нужно вычисление «в реальном времени», вы, вероятно, захотите использовать своего рода жадный алгоритм, я думаю, что A * алгоритм , вероятно, вполне удовлетворительно подходит к этой проблемной области.

Если вам нужны оптимальные решения, вам следует взглянуть на динамическое программирование решений для графика ... оптимальные решения, вероятно, займут гораздо больше времени, но вам нужно найти их только один раз, тогда они могут быть кэшированным. Возможно, ваш алгоритм A * может использовать заранее рассчитанные оптимальные пути, чтобы сообщать свои решения о «похожих» маршрутах.

Answer 4

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

Что касается ожидания и прочего, то это факторы, которые связаны с определенным узлом, верно? Вы можете перевести этот фактор в узел маршрута для каждой из ветвей, прикрепленных к узлу. Например, вы можете сказать для каждой ветви от узла X, если есть ожидание, скажем, m минут на узле X, то увеличьте вес ветви на [m / Некоторое базовое значение * 100]% (только пример). Таким образом, вы учитываете другие факторы единообразно, но в то же время сохраняете простое представление о проблеме, которую хотите решить.