What is the problem name for Traveling salesman pr

问题:

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!

回答1:

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.

回答2:

If I understand correctly, you want to find the shortest path (that starts from some vertex s) and goes through all the nodes in the graph without visiting the same node twice. A simpler problem, is the hamiltonian path problem. It asks, like you said, weather there exists such a path or not. Since that problem is NP-hard, and it's easier than your problem, solving your problem is at least NP-Hard. Well, that isn't true because your problem is not a decision problem. But what it does say is that we can almost be sure that there is no polynomial algorithm for your problem.

You can resort to approximation. There is a pretty cool approximation for the metric TSP here: http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP.