Warm tip: This article is reproduced from stackoverflow.com, please click
algorithm graph-algorithm traveling-salesman np-hard

What is the problem name for Traveling salesman problem(TSP) without considering going back to start

发布于 2020-05-27 15:47:33

I would like to know what is the problem name for TSP w/o considering the way of going back to starting point and what is the algorithm to solve this.

I looked into Shortest path problem but that is not what I am looking for, the problem only find the shortest path from 2 assigned points. But what I am looking for is the problem which we give n points and inputting only 1 starting point. Then, find the shortest path traveling all points exactly once. (end point can be any point.)

I also looked into Hamiltonian path problem but it seems not to solve my defined problem but rather find whether there is Hamiltonian path or not.

Please suggest me, Thank you!

Questioner
A-letubby
Viewed
31
A-letubby 2011-08-23 17:16

I've found the answer to my question in this book. It is the same with Computer wiring problem which occurs repeatedly in the design of computers and other digital systems. The purpose is to minimize the total wire length. So, it is indeed a minimum length Hamiltonian path.

What the book suggests is to create a dummy point whose distances to every other points is 0. Therefore, the problem becomes an (n+1)-city symmetric TSP. After solving, just delete dummy point and then the minimum length Hamiltonian path is solved and we can get the TSP path without returning back the start point.