47

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.

Nakilon
  • 34,866
  • 14
  • 107
  • 142
A-letubby
  • 8,474
  • 8
  • 38
  • 48
  • 1
    A minimum spanning path perhaps? :) – carlpett Jul 18 '11 at 13:57
  • 3
    Shortest Hamiltonian Path? I just made it up, too. – Szocske Jul 18 '11 at 14:00
  • 49
    The divorced salesman – Chris Eberle Jul 18 '11 at 14:13
  • I'm sorry for unclear question. I would like to know the name because I want some keyword to find some solution. – A-letubby Jul 19 '11 at 15:16
  • For easy understanding(I think), let's imagine I am the traveler and I want to travel to all the countries in this world starting from my country (each only once include my country), longer distance between 2 countries is, more expensive the cost is. If I reach the last country I will live there and spend all of my life there. What is the least expense? If I use TSP, I think some good solution might be cut out since there is the condition that at last I have to be home. – A-letubby Jul 19 '11 at 15:28

4 Answers4

44

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.

A-letubby
  • 8,474
  • 8
  • 38
  • 48
  • 2
    Just to get a clarification: When we get the solution by TSP and remove the dummy node, the starting point of the Hamiltonian path becomes the node after the dummy node and end point becomes the node before the dummy point? Is this correct? Also, if we wish to fix the starting point, how can we do that using this technique or any other? – Vivek Payasi Jan 18 '23 at 09:30
  • @Vivek Payasi. You can fix start and end point by creating a dummy point with 0 distance to both start and end points and infinite distance to all others. That will require n iterations to solve the whole problem. Source: https://stackoverflow.com/questions/14527815/how-to-fix-the-start-and-end-points-in-travelling-salesmen-problem/59354134#59354134 Though I have a better solution in next comment – CrafterKolyan May 07 '23 at 23:37
  • @VivekPayasi actually I just added an answer as it's too large for a coment: https://stackoverflow.com/a/76196763/9632774 – CrafterKolyan May 07 '23 at 23:55
3

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.

Guy
  • 14,178
  • 27
  • 67
  • 88
  • 1
    If you have an algorithm to test whether a path shorter than X exists, it can usually be turned into an algorithm to find the length of the shortest path using binary search at no increase of complexity. Then again the question of the length of the shortest path can be turned into an algorithm to find the shortest path by dropping edges. This has to do with the decision problem being NP-Complete, thus allowing for reduction of seemingly more complex problems. – LiKao Jul 18 '11 at 14:28
  • You're not contradicting my answer right? You agree that the problem proposed probably doesn't have a polynomial algorithm that solves it - right? – Guy Jul 18 '11 at 14:38
  • @Guy He's not contradicting you, he's just commenting on you remark about decision problems. This is definately NP-complete, but your proof lacks something: Hamiltion path does not have a fixed starting point, afaik. Also, your remark "easier" is sloppy in a proof. You could say "If you could solve the decision of Divorced-TSP with a bounds large enough (sum of all edges), then you can solve Hamiltonian Path" (which btw imho hasn't been proven here yet). – Albert Hendriks Jul 18 '11 at 19:03
  • @Guy: No I am not contradicting on your point that this problem does not have a simple solution. As far as I can tell the problem seems NP-complete (I do not have a proof though). All I wanted to point out was that the decision problem cannot have a lower complexity than the calculation problem, because of the polynomial reduction. So if Divorced-TSP is NP-Complete the corresponding decision problem will be NP-Complete as well. – LiKao Jul 19 '11 at 09:10
  • P.s. it should be obvious that the other way of reduction is trivial so this just prooves that the classes of the calculation-problem and the decision problem have to be equal. This does not say in which class they are in though. – LiKao Jul 19 '11 at 09:12
0

Using Asymmetric TSP Solver (if any)

If a start node has to be specified, as mentioned by @Vivek Payasi, you can build a typical TSP problem with weights otherwise normal except for the arcs that flow into the start node. Set their weights to 0.
This will produce an asymmetric travelling salesman problem(ATSP).

Now if you have an exact ATSP solver, this will look for the shortest cycle.
When it's done, remove the arc with weight 0 from the solution. This will look like a path you're looking for.

*All this relies on an efficient ATSP solver.

Using a plain Symmetric TSP Solver Instead

If you want to avoid using ATSP solver, refer to this answer: https://stackoverflow.com/a/59354134/7470152

The bottom line is: fix start node & an end node, add a dummy node whose arcs are connected to both node with weight 0 and then treat it like a normal TSP problem.
Repeat this for all (n-1) end nodes, and choose the shortest one.

Jangwhan Jeong
  • 23
  • 6
  • Probably there is no one good-fit solution to a TSP problem with only fixed start point (and any arbitary end point). If there is any, please do share. – Jangwhan Jeong Jan 27 '23 at 01:12
  • I added extra answer how to do that without using symmetric TSP solver n - 1 times: https://stackoverflow.com/a/76196763/9632774 – CrafterKolyan May 07 '23 at 23:56
0

Using Symmetric TSP Solver with dummy point

Create a dummy point that has 0 distance to start point and large number for distance for other points (this "number" should be greater than "diameter of graph") that way it should be always optimal for this dummy point to connect to your start point. Then use symmetric TSP solver to get solution and remove the dummy point from the answer.

Proof: Imagine optimal solution has dummy point not connected to your start point. Then let's build another solution: we take the same path but remove dummy point and put it between start point and any of its neighbours. Then length of the path will be changed by

-2 * "number" -
- "path between neighbour of starting point and starting point" -
+ "path between first neighbours of dummy point"
+ "number" =
= -"number" + "path between first neighbours of dummy point" - "path between neighbour of starting point and starting point"

but

"number" > "diameter of graph" >= "path between first neighbours of dummy point"

which gives us

-"number" + "path between first neighbours of dummy point" - "path between neighbour of starting point and starting point" < 0

that means that we got more optimal solution. Contradiction. That means that dummy point is always connected to the starting point.

CrafterKolyan
  • 1,042
  • 5
  • 13