Как спроектировать примерное решение пути?

Question

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

Чтобы обеспечить реалистичное применение этого, скажем, мне нужно перебраться из Брамптона, Онтарио, в Гамильтон, Онтарио. Я знаю, что мои возможные варианты в моей начальной точке: местный транспорт, GO bus или Walking. Я знаю, что ходьба - наименее желательный способ добраться до места назначения, поэтому я сначала смотрю на автобус GO. Я знаю, что могу подвести GO к точке, близкой к Гамильтону, но в этот момент шина GO поворачивается и движется в другом направлении в той самой точке, где у меня нет вариантов (кроме как ходить, но алгоритм будет учитывать только ходьбу). на короткие расстояния, в противном случае маршрут будет считаться невозможным)

Используя этот же пример, если бы алгоритм нашел, что я могу найти путь, который длиннее, но приближает меня к узлу назначения (или, возможно, к узлу назначения), который был бы с более взвешенным путем (Веса) не имеет большого значения при поиске, только когда результаты будут доставлены, в нем будет указан список, по которому путь был ближайшим к месту назначения в порядке возрастания). Например, один автобус GO может доставить меня в 3 км от узла назначения, в то время как 3 общественных автобуса доставят меня на расстояние 500 м

Итак, мой вопрос состоит из двух частей: 1) С какого алгоритма мне начинать что-то похожее 2) Как бы я программно объяснил, что это нормально, если узлы не соединяются, чтобы он не просто перепрыгивал с узла A на узел R. Начал бы с конца и работал в обратном направлении, чтобы достичь этого

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

Спасибо, Майкл

Answer 1

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

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

Answer 2

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

В этом случае вы можете просто изменить свою модель следующим образом: у вас есть один график для каждого метода транспортировки. Узлы, которые находятся в одном и том же месте, связаны с ребрами с весом 0 (т. Е. Если вас отвезли на машине в аэропорт или на вокзал).

Затем пометьте каждую вершину и ребро типом транспортировки, и вы можете просто использовать существующие алгоритмы маршрутизации. О, кстати: A * не будет хорошо масштабироваться для действительно больших сетей. Чтобы получить что-то, что фактически использовало бы программное обеспечение, такое как Yahoo / Google / Microsoft Maps, посмотрите здесь . Работа этой исследовательской группы включает победителя конкурса DIMACS по кратчайшему пути .

Answer 3

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