Как найти минимальное количество пересадок для метро или ж / д сети?

Question

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

Теперь, чтобы найти путь минимальной передачи, я использую специализированную BFS, применяемую к линиям метро, ​​но это не гарантирует, что найденный путь является самым коротким среди всех других путей минимальной передачи.

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

Дополнение к вопросу:

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

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

Вот пример: если у меня есть частичный график (всего 4 станции) и их линии метро: A (красный), B (красный, синий), C (красный), D (синий).Пусть станция А будет источником.И соединения:
---- D (синий) - B (синий, красный) - A (красный) - C (красный) -----

Если я буду следовать алгоритму Дейкстры: сначала я помещаю A в очередь, затем снимаю очередь с A в 1-й итерации и смотрю на ее соседей: B и C, я обновляю их расстояния в соответствии с весами AB и AC.Теперь, несмотря на то, что B соединяет две линии, на данный момент я не знаю, нужно ли мне делать перевод в B, поэтому я не добавляю «штраф» за перевод.Допустим, что расстояние между AB

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

Answer 1

Вы можете сделать каждый свой вес парой: (# of transfers, time). Вы можете добавить эти веса очевидным способом и сравнить их в лексикографическом порядке (сначала сравните количество передач, используйте время как таймбрейкер).

Конечно, как уже упоминали другие, использование K * (# of transfers) + time для некоторого достаточно большого K дает тот же эффект, если вы знаете максимальное время apriori, и вы не исчерпали бит в своей памяти веса.

Answer 2

Я собираюсь описать свое решение, используя алгоритм A * , который я считаю расширением (и улучшением - пожалуйста, не стреляйте в меня) Алгоритма Дейкстры, который легче понять интуитивно. Основы этого звучат так:

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

Вместо того, чтобы делать свой вес просто расстоянием до минимума + минимальным расстоянием до цели, вы можете использовать два веса: Остановки и Расстояние / Время по сравнению следующим образом:

В принципе, для сравнения:

• Сравнение останавливается первым и, если возможно, сообщите об этом сравнении (т. Е. Если они не совпадают)
• Если остановки равны, сравните пройденное расстояние

И сортируйте свою очередь таким образом.

Если вы когда-либо играли Mario Party , думайте о остановках как о звездах, а расстояние как о монетах. В середине игры человек с двумя звездами и десятью монетами будет выше кого-то с одной звездой и пятьдесятю монетами.

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

Answer 3

Как отметил Амадан в комментарии, все дело в создании правильного графика.Я просто опишу это более подробно.

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

Теперь давайте предположим, что максимальное время в пути всегда меньше 10000 (используйте вашу константу).Тогда вес ребра AB (A и B находятся на одной линии) равен time_to_travel_between(A, B) + 10000.

Запуск Dijkstra на таком графике гарантирует, что будет использовано минимальное количество переходов и минимальное время будет достигнуто во втором месте..

обновление в комментарии
Давайте "докажем" это.Существует два решения: с 2-мя пересадками и 40-минутным временем в пути и с 3-мя пересадками и 25-минутным временем в пути.В первом случае вы путешествуете по 3 линиям, поэтому вес пути будет 3 * 10000 + 40. Во втором: 4 * 10000 + 25. Будет выбрано первое решение.

Answer 4

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

Answer 5

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

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

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

Это помогло мне с моей проблемой перехода на Флойд-Варшалл. Надеюсь, это поможет вам. Его легче кодировать и намного проще реализовать.