Friday 18 October 2013

A solution to Exercise 35.2-5 in the book "Introduction to algorithms" by Cormen, Leiserson and Rivest.

Suppose that the vertices for an instance of the traveling-salesman problem are
points in the plane and that the cost c(u,v) is the euclidean distance between
points u and v. Show that an optimal tour never crosses itself.


 
If the optimal tour crosses itself then it can be in a manner shown in the attached picture. Thus, there are edges AC and DB (a tour with crossing) instead of AB and DC (optimal tour). The edge AC can be represented as a sequence of edges: AX and XC. The same can be done for edge DB, which can be represented as a sequence of edges: DX and XB. By the triangle inequality, AB < AX + XB (red) and DC < DX + XC (green). In this case, we can show that the optimal tour cannot cross itself, because: AB + DC < AX + XB + DX + XC = (AX + XC) + (DX + XB) = AC + DB. Now, we can generalize the case, and have a cross between more than two consecutive vertices, for example, A'C' and AC, but then we can see from the picture, that we will have to turn back at some point, for example from A to C (instead of going forward), which lengthen the path even more.

No comments:

Post a Comment