Does there exist an instance of the travelling salesman problem where the optimal solution has edges that cross?
5
-
9$\begingroup$ No. Any pair of crossing edges can be replaced with a pair of noncrossing edges, which strictly decreases the total length of the path by the triangle inequality. $\endgroup$– Qiaochu YuanCommented Mar 14, 2010 at 22:51
-
3$\begingroup$ It depends on if one is working with sites drawn in the plane and if the edges are weighted with Euclidean distances. If one has arbitrary weights and the weights do not obey the triangle inequality then in a drawing of a shortest weight tour, edges may cross. $\endgroup$– Joseph MalkevitchCommented Mar 14, 2010 at 23:07
-
$\begingroup$ There is a diagram of the argument Qiaochu gave here: ams.org/featurecolumn/archive/tsp.html $\endgroup$– Douglas ZareCommented Mar 14, 2010 at 23:10
-
$\begingroup$ But what does it mean to say that the solution has edges that cross? $\endgroup$– Harald Hanche-OlsenCommented Mar 14, 2010 at 23:22
-
$\begingroup$ The natural interpretation is that bob is talking about the Euclidean TSP. $\endgroup$– Douglas ZareCommented Mar 14, 2010 at 23:40
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I've answered this in https://stackoverflow.com/questions/2444125/crossing-edges-in-the-travelling-salesman-problem/2444288#2444288.
$\begingroup$
$\endgroup$
1
Yes, as long as your distance does not satisfy the triangle inequality. Here is a series of points which form a shortest route under the Hamming distance. If you plot them on the plane, you will notice that they cross over.
(1,1) (1,2) (4,2) (3,2) (0,2) (0,1)
-
2$\begingroup$ But the hamming distance satisfies the triangle inequality. $\endgroup$ Commented Dec 7, 2011 at 5:52