В чем проблема, связанная с проблемой Traveling salesman (TSP), не учитывая возврат к отправной точке?

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

Я рассмотрел проблему Shortest path, но это не то, что я ищу, проблема заключается в поиске кратчайшего пути из 2 назначенных точек. Но то, что я ищу, - это проблема, которую мы даем n точками и вводим только одну начальную точку. Затем найдите самый короткий путь, перемещающий все точки ровно один раз. (конечной точкой может быть любая точка.)

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

Пожалуйста, предложите мне, спасибо!

Ответ 1

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

В книге предлагается создать фиктивную точку, расстояния которой до всех остальных точек равны 0. Поэтому задача становится (n + 1) -симметричной TSP. После решения просто удалите фиктивную точку, а затем гамильтонов путь пути минимальной длины решается, и мы можем получить путь TSP, не возвращая исходную точку.

Ответ 2

Если я правильно понял, вы хотите найти кратчайший путь (который начинается с некоторых вершин s) и проходит через все узлы в графе, не посещая один и тот же node дважды. Более простая проблема - проблема гамильтонова пути. Он спрашивает, как вы сказали, погода существует такой путь или нет. Поскольку эта проблема NP-жесткая, и это проще, чем ваша проблема, решение вашей проблемы - это, по крайней мере, NP-Hard. Ну, это не так, потому что ваша проблема не проблема. Но то, что он говорит, заключается в том, что мы можем почти быть уверены, что для вашей проблемы нет полиномиального алгоритма.

Вы можете прибегнуть к аппроксимации. Для метрического TSP существует довольно крутое приближение: http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP.