Поиск кратчайшего пути по нескольким точкам

Требования:

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

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

  3. Вам разрешено посещать каждую цель несколько раз.

Вопрос:

1) Какой алгоритм мне следует использовать, чтобы подойти к этому?

2) Предлагаемый мной подход

Допустим, target = [A, B, C].

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

graph algorithm shortest-path
person samol    schedule 08.07.2015    source источник
comment
Если вы можете посещать каждую цель несколько раз, очевидно, что вы посещаете одну и ту же цель последовательно, потому что расстояние между целью и самой собой равно 0, и вы можете засчитать 3 посещения одной и той же точки как 1 посещение. Итак, какое еще правило отличает эту задачу от задачи коммивояжера?   -  person GolezTrol    schedule 08.07.2015
comment
@GolezTrol вы должны посетить все целевые узлы.   -  person Adam    schedule 08.07.2015
comment
@GolezTrol Не уверен, что ваш вопрос. Как только я посетил A. A удаляется из целевого списка. Хотя я мог бы пройти мимо него в будущем, он больше не является целью   -  person samol    schedule 08.07.2015
comment
Второй комментарий GolezTrol; разрешение посещать один и тот же узел несколько раз не упрощает задачу, по крайней мере, для неотрицательных весов ребер. Насколько я понимаю, обсуждаемая проблема - это как раз проблема коммивояжера (предполагается, что используются неотрицательные веса ребер).   -  person Codor    schedule 08.07.2015
comment
@codor Хорошо, плохо, я изменил проблему   -  person samol    schedule 08.07.2015
comment
@Codor мое решение ошибочно?   -  person samol    schedule 08.07.2015
comment
@Codor, хотя я считаю, что невозможность дважды посетить один и тот же узел - вот что делает проблему коммивояжера: cs.stackexchange.com / a / 1761/34665   -  person samol    schedule 08.07.2015
comment
Вы не изменили проблему.   -  person Adam    schedule 08.07.2015
comment
Ваше решение не подходит для взвешенных ориентированных графов.   -  person Adam    schedule 08.07.2015
comment
@ Адам Я имел в виду, что изменил ту часть, где заявил, что это не проблема коммивояжера   -  person samol    schedule 08.07.2015
comment
Почему мое решение не подходит для взвешенного ориентированного графа? Самое короткое между каждой целью является самым коротким в целом?   -  person samol    schedule 08.07.2015
comment
возможный дубликат нециклического пути ко всем узлам   -  person Lior Kogan    schedule 08.07.2015
comment
Вот почему ваше решение не работает для взвешенных ориентированных графов. Представьте себе график (A, B, w=1), (B, C, w=1), (S, A, w=13), (S, B, w=12), (S, C, w=11). источник - вершина S, цели A, B, C. Оптимальный - S -> A -> B -> C -> S. Ваше решение будет отправлено S -> C -> S -> A -> B -> C -> S.   -  person Adam    schedule 08.07.2015
comment
@adam Я думаю, вы неправильно поняли мое предложение. Я бы не стал рассматривать S, пока не будут исчерпаны все цели. Мое предложение даст раствор S->C->B->A->S, который имеет общий вес 26   -  person samol    schedule 10.07.2015
comment
@samol вы неправильно поняли, что такое ориентированный граф. Нет C->B без S. (Я забыл включить край (C, S), который должен существовать).   -  person Adam    schedule 10.07.2015

Ответы (2)


arrow_upward
0
arrow_downward

Вы на правильном пути, однако ваша проблема сводится к проблеме коммивояжера (TSP).

Используя Dijkstra, как вы упомянули, вы можете заменить все пути между целевыми узлами, которые не содержат никаких целевых узлов, одним ребром. Результатом является граф только с целевыми узлами ... что оставляет вам TSP.

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

person softwarenewbie7331    schedule 08.07.2015

arrow_upward
0
arrow_downward

Я думаю, это будет хорошее приближение:

Construct a Minimum Spanning Tree.

Do a pre-order traversal taking your source as the root.

Remove edges which are not necessary (removing which does not disconnect your source and targets).

скажем, это ваши узлы:

введите описание изображения здесь

построить MST:

введите описание изображения здесь

если a - ваш источник: выполните предварительный обход с правами root.

введите описание изображения здесь

удалите края, которые не разъединяют вашу цель и источники. (Это легко сделать с помощью union-find)

person Karthik    schedule 08.07.2015
comment
Не могли бы вы объяснить, почему предложенное мной решение неверно? И это правильное решение? - person samol; 08.07.2015
comment
вы правы, но MST - это приближение к TSP, которое, по сути, и решает OP .. без упоминания приближения - person softwarenewbie7331; 08.07.2015
comment
@samol ваше решение неверно, потому что если вы пытаетесь найти кратчайший путь от источника (S) до цели (T), вы можете посетить 1000 узлов, которые также являются целями, но в соответствии с вашим решением вы снова найдете кратчайшие пути для других 999 (S, T) комбинаций, которые не нужны, и построение MST с использованием unino-find решает эту проблему за вас. - person Karthik; 08.07.2015
comment
@karthik, мне нужно уточнить свое решение. То, что вы описали, не произойдет. Я пытаюсь найти кратчайший путь к любой из целей. Когда я вижу цель, я удаляю цель из списка целей и снова перезапускаю Dijstra. - person samol; 08.07.2015
comment
@samol, значит, у вас не будет в голове целевой узел, когда вы запустите свой первый Dijkstra? ваше решение хорошо работает для невзвешенных ребер, но я все еще думаю, что оно не будет работать для взвешенного графа. - person Karthik; 08.07.2015
comment
Я думал, что при запуске Dijkstra у меня будет список целевых узлов, а не только один целевой узел. (Это работает?) - person samol; 08.07.2015
comment
Кстати, ваш график выглядит как обход предварительного заказа, а не обход по порядку. Я прав? - person samol; 08.07.2015