В чем разница между Traveling Salesman и поиском кратчайшего пути?

Ответ 1

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

Другие отличия:

• Решение TSP требует, чтобы его ответ был циклом.
• Решение TSP обязательно повторит node в своем пути, а самый короткий путь не будет (если только он не ищет кратчайший путь от node к себе).
• TSP является NP-полной проблемой, а самый короткий путь известен многочленом времени.

Если вы ищете точное изложение разницы, я бы сказал, что вам просто нужно заменить свою идею "перестановки" на более технический и точный термин "простой цикл, посещая каждый node на графике", или лучше, "цикл Гамильтона":

TSP требует найти простой цикл, покрывающий каждый node на графике с наименьшим весом (альтернативно, цикл Гамильтона с наименьшим весом). Для задачи Shortest Path требуется найти путь между двумя заданными узлами с наименьшим весом. Самые короткие пути не обязательно должны быть гамильтоновыми, и они не должны быть циклами.

Ответ 2

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

Рассмотрим два пути между узлами A и B. Один над D другой из C. Пусть один над C является более длинным путем. В задаче кратчайшего пути этот путь можно сразу удалить. В TSP вполне возможно, что этот путь является частью всего решения, потому что вам нужно будет посетить C, а позже его можно будет еще дороже.

Поэтому вы не можете сломать TSP в аналогичных, но меньших суб-проблемах.

Ответ 3

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

Ответ 4

Самый короткий путь имеет только источник и target.we нужно найти кратчайший путь между ними, очевидно, вывод должен быть деревом в полиномиальное время.

Поиск кратчайшего пути: -

• Непересекающиеся графы: Алгоритм Дейкстры со списком O (V ^ 2)

• Направленные графики с произвольными весами без отрицательных циклов: Алгоритм Беллмана-Форда Время сложности O (VE)

• Алгоритм Флойда-Варшалла используется для поиска кратчайших путей между всеми парами

TSP (проблема с Travel-Salesman) не похожа на то, что мы покрываем каждый node из исходного кода, и, наконец, мы получаем источник с минимальной стоимостью. В любом случае должен быть цикл. TSP является NP-полной проблемой

Ref:

https://en.wikipedia.org/wiki/Shortest_path_problem

https://en.wikipedia.org/wiki/Travelling_salesman_problem

http://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/