-1
$\begingroup$

Does there exist an instance of the travelling salesman problem where the optimal solution has edges that cross?

$\endgroup$
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$ 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$ Mar 14, 2010 at 23:07
  • $\begingroup$ There is a diagram of the argument Qiaochu gave here: ams.org/featurecolumn/archive/tsp.html $\endgroup$ Mar 14, 2010 at 23:10
  • $\begingroup$ But what does it mean to say that the solution has edges that cross? $\endgroup$ Mar 14, 2010 at 23:22
  • $\begingroup$ The natural interpretation is that bob is talking about the Euclidean TSP. $\endgroup$ Mar 14, 2010 at 23:40

2 Answers 2

6
$\begingroup$

I've answered this in https://stackoverflow.com/questions/2444125/crossing-edges-in-the-travelling-salesman-problem/2444288#2444288.

$\endgroup$
0
$\begingroup$

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)

$\endgroup$
1
  • 2
    $\begingroup$ But the hamming distance satisfies the triangle inequality. $\endgroup$ Dec 7, 2011 at 5:52

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