Нахождение кратчайшего пути по нескольким точкам

Требования:Нахождение кратчайшего пути по нескольким точкам

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

Вопрос:

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

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

Скажем цели = [A, B, C]

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

источник

2015-07-08 samol

Если вы можете посещать каждую цель несколько раз, очевидно, что она будет посещать одну и ту же цель подпоследовательно, потому что расстояние между мишенью и собой равно 0, и вы можете посчитать 3 посещения в одну точку с 1 посещением. Итак, какое еще дополнительное правило делает эту проблему отличной от проблемы коммивояжера? – GolezTrol

@ GolezTrol вы должны посетить все целевые узлы. – Adam

@GolezTrol Не уверен, что ваш вопрос. Как только я посетил A. A будет удален из целевого списка. Хотя я все еще могу пройти мимо этого в будущем, он больше не является целью – samol

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

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).

говорят, это ваши узлы:

enter image description here

построить MST:

enter image description here

Если a является вашим источником: выполните предварительный обход, взяв его как корень.

enter image description here

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

источник

2015-07-08 06:52:42 Karthik

Не могли бы вы объяснить, почему мое предложенное решение неверно? И это правильное решение? – samol

Вы правы, но MST - это приближение TSP, по существу, то, что OP решает. Не упоминание о приближении – softwarenewbie7331

@samol ваше решение неверно, потому что если вы пытаетесь найти кратчайший путь от Source (S) до (T), вы можете посетить 1000 узлов, которые также являются объектами, но в соответствии с вашим решением вы снова найдете кратчайшие пути для других комбинаций 999 (S, T), которые не нужны, и построение MST с помощью unino-find разрешает эта проблема для вас. – Karthik

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

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

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

источник

2015-07-08 07:00:08 softwarenewbie7331

Нахождение кратчайшего пути по нескольким точкам

ответ

Смежные вопросы