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

Question

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

Я хочу, чтобы это работало таким образом.Я хочу перейти от станции A -> C. Давайте сначала предположим, что расстояние между станциями для простоты равно одному (1).

Route 1: A -> D -> B -> C -> A
Route 2: A -> C -> E -> F -> A
Route 3: A -> X -> Y -> Z -> A

Поскольку в обоих маршрутах есть путь от A -> Cи Маршруты 2, я выберу один с наименьшей стоимостью, который является Маршрутом 2. Я уже сделал это.

Но если я хочу перейти от Станции C -> Y, нет прямого маршрута от C ->Y. Так что мне нужно перейти от 1 или 2, затем перейти на A, затем от A -> Y. По сути, я просто хочу минимизировать трансферные шаттлы и пройденное расстояние.

Существует ли популярный алгоритм дляэто?

Answer 1

Вы можете решить это с помощью алгоритма Дейкстры .

Настройте график так, чтобы:

Существует узел для каждой станции на маршрутном автобусе. Если два шаттла отправляются в один и тот же пункт, то эта станция получает один узел для каждого маршрута. Итак, в вашем примере есть узлы A1, D1, B1, C1, A2, C2, E2, F2 -> A2 и т. Д. Также создайте узел для каждой станции, но сделайте его независимым от маршрута, например, A, B, С и т. Д.

Если челнок движется непосредственно между двумя станциями, например, в вашем примере между А1 и D1, но не между А1 и В1, то создайте направленный край между этими двумя узлами. Вес для этого края должен быть стоимость (расстояние) между двумя станциями. Так, например, есть ребра (A1, D1) и (D1, C1)

Если два шаттла останавливаются на одной и той же станции, то создайте два направленных ребра между узлами для станции на двух маршрутах, например, создайте ребра (A1, A2) и (A2, A1). Вес для краев должен быть стоимостью для перевода.

Создание двух ребер между каждым узлом станции, специфичным для маршрута, и узлом станции, который не зависит от станции, например, создание ребер (A, A1), (A1, A), (A, A2), (A2, A ). Присвойте каждому из этих узлов стоимость, намного меньшую стоимости предыдущих ребер, например 0,01 * минимальная стоимость.

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

В вашем примере, чтобы перейти от F к X, найдите путь с наименьшей стоимостью между узлами F и X. Возвращенный путь будет F -> F2 -> A2 -> A3 -> X3 -> X со средством start в F садитесь на шаттл 2, езжайте в A, переходите на маршрут 3, затем выходите на станции X.

Answer 2

много, и много оптимизаций для определенных сценариев, ограничений и т. Д.

try dijkstra's , обычно это основа для алгоритмов кратчайшего пути (то есть, где много людей начинают узнавать об этом), хотя, чтобы действительно понять, как это можно эффективно реализовать, вам, вероятно, также следует ознакомиться с соответствующими структурами данных (куча различных описаний и т. д., см. вики)

Answer 3

Это обычно рассматривается при планировании транспортировки.

Дополните график, представляющий сеть, следующим образом:

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

Сейчасминимальный путь между двумя станциями будет стоить:

1. Один тариф на посадку плюс небольшой тариф на соединение в пути, когда обе станции соединены маршрутом.
2. Две или болеетарифы на посадку плюс тариф за соединение для станций, не связанных напрямую с маршрутом.
3. Бесконечно, если не найдено пути между станциями.

Во всех случаях путь будетминимум в отношении посадок и передач и количества ссылок.

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

Answer 4

Я думаю, что это немного сложнее, чем TSP.Вы хотите минимизировать расстояние и используемые шаттлы.

Как взвесить каждый?Если вы хотите минимизировать количество трансферов, используйте наборы

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

Answer 5

множество алгоритмов для таких вещей:

http://en.wikipedia.org/wiki/Shortest_path_problem#Algorithms

Answer 6

Это компонент Задача коммивояжера .По сути, нет «легкого» решения.Но есть несколько алгоритмов, которые дают «достаточно хорошие» решения.