Как называется проблема «Задача коммивояжера» (TSP) без учета возврата к исходной точке?

Question

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

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

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

Answer 1

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

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

Answer 2

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

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