Как найти минимальное количество передач для метро или железнодорожной сети?
Я знаю, что алгоритм Dijkstra может найти минимальное расстояние между двумя узлами (или в случае метро - станции). Мой вопрос, хотя проблемы, находящие минимальное количество передач между двумя станциями. Кроме того, из всей минимальной передачи соединяет каналом, я хочу тот с самым коротким временем.
Теперь, чтобы найти, что минимальная передача соединяет каналом, я использую специализированный BFS, относился к линиям метро, но она не гарантирует, что найденный путь является кратчайшим среди всех других путей минимальной передачи.
Я думал, что, возможно, изменение алгоритма Dijkstra могло бы помочь - эвристическим образом добавив вес (время) для каждой передачи, такой, что это удержит алгоритм от создания передачи в другую строку. Но в этом случае я должен был бы найти веса передачи опытным путем.
Дополнение к вопросу:
Мне рекомендовали добавить "штраф" каждому разу, когда алгоритм хочет передать другой линии метро. Здесь я объясняю некоторые свои опасения по поводу этого.
Я отложил эту проблему в течение нескольких дней и возвратился к ней сегодня. После рассмотрения проблемы снова похоже на выполнение алгоритма Dijkstra на станциях и выяснении, где передача происходит, твердо, это не столь очевидно, как можно было бы думать.
Вот пример: Если здесь у меня есть частичный график (всего 4 станции) и их линии метро: (красный), B (красный, синий), C (красный), D (синий). Позвольте станции A быть источником. И соединения:
----D (синий) - B (синий, красный) - (красный) - C (красный)-----
Если я следую алгоритму Dijkstra: первоначально я помещаю в очередь, затем исключаю из очереди в 1-м повторении и смотрю на его соседей: B и C, я обновляю их расстояния согласно весам A-B и A-C. Теперь даже при том, что B соединяет две строки в этой точке, я не знаю, должен ли я сделать передачу в B, таким образом, я не добавляю "штраф" за передачу. Скажем, то, что расстояние между A-B <A-C, который вызывает на следующем повторении для B, который будет исключен из очереди. Его сосед является D, и только в этой точке я вижу, что передача должна была быть сделана в B. Но B был уже обработан (исключенный из очереди). S
Таким образом, я не уверен, как эта "задержка" определения потребности в передаче влияла бы на целостность алгоритма. Какие-либо мысли?
4 ответа
Вы можете сделать каждый из ваших весов парой: (количество перемещений, время) . Вы можете сложить эти веса очевидным образом и сравнить их в лексикографическом порядке (сначала сравните количество переводов, используйте время как средство разрешения конфликтов).
Конечно, как отмечали другие, использование K * (количество передач) + время для некоторого достаточно большого K дает тот же эффект, если вы знаете максимальное время априори и не знаете Закончились биты в вашем хранилище веса.
Вы имеете правильное представление, но на самом деле вам не нужно эмпирически находить веса переноса - вам просто нужно убедиться, что вес для одного переноса больше, чем вес для максимально долгое время в пути. Вы должны быть в полной безопасности, если дадите переносу вес, эквивалентный, скажем, году времени в пути.
Как заметил Амадан в комментарии, все дело в создании правильного графика. Я просто опишу это поподробнее.
Считайте две вершины (станции) имеющими ребро, если они находятся на одной прямой. С помощью этого графика (и веса 1) вы найдете минимальное количество переходов с помощью Дейкстры.
Теперь предположим, что максимальное время в пути всегда меньше 10000 (используйте вашу константу). Тогда вес ребра AB (A и B находятся на одной строке) равен time_to_travel_between (A, B) + 10000 .
Запуск Дейкстры на таком графе гарантирует, что будет использовано минимальное количество переходов и, во-вторых, будет достигнуто минимальное время.
обновить в комментарии
Давайте «докажем» это. Есть два решения: с 2 пересадками и временем в пути 40 минут и с 3 пересадками и временем в пути 25 минут. В первом случае вы путешествуете по 3 линиям, поэтому вес пути будет 3 * 10000 + 40. Во втором: 4 * 10000 + 25. Будет выбрано первое решение.
Я собираюсь описать свое решение, используя A * Algorithm , который я считаю расширением (и улучшением - пожалуйста, не стреляйте в меня) алгоритма Дейкстры, который проще интуитивно понять. Основы этого таковы:
- Добавьте начальный путь в очередь приоритетов, взвешенный как расстояние до конца + минимальное расстояние до цели
- На каждой итерации выбирайте путь с наименьшим весом и разбивайте его на все пути, которые находится в одном шаге от него (отбрасывая пути, которые замыкаются вокруг себя), и помещает его обратно в очередь. Остановитесь, если найдете путь, заканчивающийся у цели.
Вместо того, чтобы делать ваш вес просто «расстояние до конца + минимальное расстояние до цели», вы можете использовать два веса: остановки и расстояние / время, сравнивая таким образом:
В основном, для сравнения:
- Сначала сравните остановки и сообщите об этом сравнении, если возможно (т. Е. Если они не совпадают)
- Если остановки равны, сравните пройденное расстояние
И отсортируйте вашу очередь таким образом.
Если вы когда-либо играли в Mario Party , думайте об остановках как о звездах, а расстояние как о монетах. В середине игры человек с двумя звездами и десятью монетами будет выше кого-то с одной звездой и пятьюдесятью монетами.
Это гарантирует, что первый узел, который вы выберете из своей очереди приоритетов, будет уровнем с наименьшим возможным количеством остановок.