4
$\begingroup$

For my case I have starting point and several cities.

I want the shortest route to visit all cities without returning starting point.

I have read several TSP algorithm and all include the return a full cycle.

So what TSP variation should I look for to solve my problem?

Improve this question
$\endgroup$
  • 5
    $\begingroup$ Look at Hamiltonian path. $\endgroup$ – Juho Jun 12 '15 at 22:02
  • 2
    $\begingroup$ In the worst case, you can solve this by solving ordinary TSP $n-1$ times. This is because a solution to your problem is a solution to TSP where the cost from the last city back to the start is zero. The problem is that you don't know which city is supposed to come last, but you can try each one in turn. $\endgroup$ – David Richerby Jun 13 '15 at 10:34
  • $\begingroup$ @DavidRicherby I don't see wich $n-1$ should solve. So for starting point A and cities {b,c,d} you are suggestion solve {a,b,c}-{a,c,d}-{a,b,d} and choose the smallest? Or creating dummy link for each city cost=0 to start and then running once? $\endgroup$ – Juan Carlos Oropeza Jun 13 '15 at 12:45
  • $\begingroup$ Compute TSP three times: once with the cost of Ab set to zero, once with Ac (and Ab put back to its real cost) and once with Ad (and Ab and Ac at their real costs). The smallest answer is the answer to your question. $\endgroup$ – David Richerby Jun 13 '15 at 12:56
  • $\begingroup$ @DavidRicherby I see how can that work for small number of cities, But for bigger N doesn't sound scalable. $\endgroup$ – Juan Carlos Oropeza Jun 16 '15 at 14:54
5
$\begingroup$

You can reduce to a normal TSP variant by adding a dummy city that is distance $0$ away from each of the existing cities. (See also this answer on StackOverflow.)

Edit: it seems that my suggested modification is not quite appropriate: as I understand it, your Hamiltonian path has a fixed starting point but no fixed end point. One way to solve this is to add two dummy cities $v$ and $w$ such that:

  • $v$ is only connected to the starting point and to $w$,
  • $w$ is connected to everything.
Improve this answer
$\endgroup$
0
$\begingroup$

Turn it into an instance of the Hamiltonian $s-t$ path problem, as suggested in the comments of your original post.

Take your input graph and add two new vertices $s$ and $t$. Both of them should be connected to all other cities, but not to one another. All edges incident to $s$ or $t$ should be weighted 0.

Your 'salesman' can then start at $s$, visit all cities included on the original graph, and finish up at $t$.

Improve this answer
$\endgroup$
  • $\begingroup$ Hm. The Hamiltonian path problem is unweighted, whereas OP clearly speaks of a shortest route (and you also speak of weights). That's why I'm reducing the problem to an instance of TSP. Furthermore, I see no reason why a Hamiltonian path in your extended graph should start in $s$ and finish in $t$. It can do so, yes, but there is no guarantee that an arbitrary Hamiltonian path in your graph has this property. $\endgroup$ – Josse Jul 25 '17 at 23:15
  • $\begingroup$ Oh, right, you're reducing it to the Hamiltonian $s$-$t$-path problem. Is that even a thing? Is there a special algorithm for the Hamiltonian path problem that assumes knowledge of the start and end points? $\endgroup$ – Josse Jul 25 '17 at 23:19
  • $\begingroup$ Yeah it's a thing if you want it to be I guess... mathworld.wolfram.com/HamiltonianPath.html . I may have made an incorrect assumption in thinking the input graph OP had in mind was complete. In the case that it was complete and a direct route between all cities existed, we can just add edge weights and turn it into a Hamiltonian shortest path problem. Whilst I'm struggling to find any research papers specifically addressing this variant, I'd hazard a guess that since the equivalent decision problem is known to be NP-complete, there's probably a good chance this optimisation variant is $\endgroup$ – swingballchamp42 Jul 25 '17 at 23:41
  • $\begingroup$ NP-hard. I will do some digging and see if I can find anything backing it up. Since you probably wont be able to find a polynomial time algorithm solving this, I guess an approximation algorithm (researchgate.net/publication/…) or some sort of heuristic approach are OPs best bets. $\endgroup$ – swingballchamp42 Jul 25 '17 at 23:43
  • 1
    $\begingroup$ Okay, it seems that the question is missing details. :-) In any case, most variants of the Hamiltonian shortest path problem can be proven to be NP-hard by reductions from TSP, similar to the one I describe here. (General procedure: duplicate one vertex, add seperate degree-one vertices to each of the two copies.) I deliberately left out a proof that the problem was NP-hard, because the OP only asked for a reduction from his problem to TSP, not the other way around. $\endgroup$ – Josse Jul 25 '17 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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