Путешествие на автобусе

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

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

Медленный и наивный метод будет следующим:

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

Это кажется очень неэффективным, и это действительно не нормальная проблема графа. Проблема в том, что в нормальном направленном графе, если вы можете получить от A до B и от B до C, вы можете получить от A до C. Это не так.

Чем быстрее вы можете решить эту проблему?

Ответ 1

Я думаю, что ваш оригинальный алгоритм довольно хорош.

Вы можете думать о своем подходе как о версии Dijkstra algorithm, пытаясь найти кратчайший путь к каждому node.

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

Реализации Dijkstra могут использовать кучу для извлечения следующего node для изучения в O (logn), и я думаю, что это будет хорошим дополнением к вашему подходу. Если вы всегда выбираете node, с которым вы можете связаться раньше всего, вам не нужно будет повторять вычисления для этого node.

В целом подход:

Для каждой начальной точки
Используйте модифицированный Dijkstra для вычисления всех узлов, доступных в течение 1 дня.
Найдите самый дальний в пространстве всех этих узлов.

Итак, для n начальных точек и маршрутов e bus сложность - это O (n (n + e) log (n)), чтобы получить оптимальный ответ.

Вы должны иметь возможность повысить производительность, используя соответствующую эвристику в A * search. Эвристика должна недооценивать максимально возможное расстояние от точки, поэтому вы можете использовать максимальную скорость шины, умноженную на оставшееся время.

Ответ 2

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

Создайте node для каждого места за время вылета.
Создайте node для каждого места за время прибытия.
Создание ребер для подключения отправлений к прибывающим.
Создайте ребра для соединения данного node с node, принадлежащим к тому же самому местоположению в ближайшее время.

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

Ответ 3

Простейшее представление графа не будет работать. I. e. каждый город является node, а ребра представляют время. Это потому, что "край" не всегда активен - он активен только в определенное время суток.

Вторая вещь, которая приходит на ум, - это расписание поездов в Париже Эдварда Туфте , которое является другим видом графика. Но это тоже не совсем подходит. С расписанием поездов станции имеют последовательную связь между станциями, но это не в общем случае с графиками городов и автобусов.

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

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

Решение линейного времени: Обратите внимание, что график будет направленным, ациклическим графом. Поиск самого длинного пути в таком графике linear. "Самый длинный путь между двумя заданными вершинами s и t в взвешенном графе G - это то же самое, что и кратчайший путь в графе -G, полученный из G, путем изменения каждого веса на его отрицание, поэтому, если кратчайшие пути могут быть найдены в - G, то самые длинные пути также можно найти в G."

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

Ответ 4

Извините, но, как описано, эта проблема имеет довольно высокую сложность. Неправильно возникла проблема и подумал, что это np-hard, но это не так. Тем не менее, он имеет довольно высокую сложность, с которой я лично не хотел бы иметь дело. Этот алгоритм - довольно хорошее приближение, которое дает значительную сложность, что я лично считаю, что это того стоит.

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

Лично я бы предложил использовать простой жадный алгоритм здесь.

Я сделал это на нескольких (предоставленных, небольших и надуманных) примерах, и он работал очень хорошо и имеет эффективность nlog(n).

Свяжите a velocity с каждым node, скорость которого будет самой быстрой, вы можете отойти от заданного node. В моих примерах эта скорость была distance_travelled/(wait_time + travel_time). Я использовал максимальную скорость всех поездок, оставляя node как показатель скорости для этого node.
Из вашего node/time вычислите скорости всех соседних узлов и перейдите к "самому быстрому" node.

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

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

Ответ 5

Наивное лучшее, что вы получите - http://en.wikipedia.org/wiki/Longest_path_problem

EDIT:

Таким образом, проблема в два раза.

Создайте список графиков, где его можно перемещаться из точки А в точку Б. Возможно, это касается времени, доступного для шины А для перемещения от точки А к точке В.
Найдите самый длинный путь из всего возможного сгенерированного пути выше.

Другим подходом было бы переоценить график на каждом обходе node и найти самый длинный путь. Он по-прежнему сводится к поиску максимально возможного пути, который является NP-Hard.