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.

5
  • 1
    A minimum spanning path perhaps? :)
    – carlpett
    Jul 18, 2011 at 13:57
  • 3
    Shortest Hamiltonian Path? I just made it up, too.
    – Szocske
    Jul 18, 2011 at 14:00
  • 49
    The divorced salesman Jul 18, 2011 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, 2011 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, 2011 at 15:28

4 Answers 4

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.

3
  • 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? Jan 18 at 9: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: stackoverflow.com/questions/14527815/… Though I have a better solution in next comment May 7 at 23:37
  • @VivekPayasi actually I just added an answer as it's too large for a coment: stackoverflow.com/a/76196763/9632774 May 7 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.

5
  • 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, 2011 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, 2011 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). Jul 18, 2011 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, 2011 at 9: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, 2011 at 9: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.

2
  • 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. Jan 27 at 1:12
  • I added extra answer how to do that without using symmetric TSP solver n - 1 times: stackoverflow.com/a/76196763/9632774 May 7 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.