patternMinor
What TSP variant doesn't return to start point?
Viewed 0 times
tspvariantwhatpointreturndoesnstart
Problem
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?
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?
Solution
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:
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.
Context
StackExchange Computer Science Q#43549, answer score: 6
Revisions (0)
No revisions yet.