If I had a list of 4 or more cities, then does the path between the two closest cities always appear in the final shortest route of a TSP Solution? Bill
5
-
$\begingroup$ No. Consider a cycle with edge lengths longer than the length of an interior chord. No cycle contains that chord. For paths, you can similarly construct other examples. Gerhard "Say, Using Maybe Three Chords" Paseman, 2016.07.02. $\endgroup$– Gerhard PasemanCommented Jul 3, 2016 at 1:02
-
$\begingroup$ Gerhard, your example is not right. Consider a square, with distance 2 on the sides, but distance 1 on the diagonals. The shortest path costs 4, two diagonals and a side, using the chords, but the outside would cost 6. $\endgroup$– Joel David HamkinsCommented Jul 3, 2016 at 1:12
-
$\begingroup$ Ah, you said "cycle", but I understand the TSP solution to merely visit every city, not necessarily a cycle. But I guess people often want a cycle, since the salesman wants to get home again at the end. $\endgroup$– Joel David HamkinsCommented Jul 3, 2016 at 1:23
-
$\begingroup$ But even so, in a pentagram, if the outside cost $2$ and the chords cost $1$, one could make a cycle by following the chords with a cost of $5$, whereas the outside would cost 10. But I suppose it would work if there were just one cheap interior chord, and the others high cost. $\endgroup$– Joel David HamkinsCommented Jul 3, 2016 at 1:32
-
$\begingroup$ If this were true, it would give you a fast algorithm to solve the TSP: include the shortest path, treat the now connected two cities as one vertex, pick the shortest path from the remaining graph etc. $\endgroup$– Christian RemlingCommented Jul 3, 2016 at 16:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The answer is no.
Consider five cities, with $(a,b), (b,c), (c,d), (d,e)$ each having cost $2$, and $(b,d)$ cost $1$, but all other edges much more expensive. The shortest path visiting every city is a,b,c,d,e, with total cost $8$, but you cannot use the cheapest edge $(b,d)$ without double-tracking and higher cost.
c
/ \
a -- b -- d -- e
answered Jul 3, 2016 at 1:16