From: israel@math.ubc.ca (Robert Israel) Subject: Re: No crossing in TSP? Date: 20 Jan 2000 17:47:04 GMT Newsgroups: sci.math.research,sci.math Summary: [missing] In article <3886AEE2.F298D1A6@mit.edu>, Xavier Gabaix wrote: >It's probably well-known, but I was wondering if somebody could give me >a quick ref: take the traveling salesman problem, with cities in real >Euclidean space (R^2), no 3 cities are aligned, and there's a straight >road between any 2 cities. It looks like the optimal path does not have >roads that cross, i.e. the salesman does not visit any point (on any >road) twice. >Is that true? Yes, it's well-known. The point is that for any 4 cities A,B,C,D, if the line segments AC and BD intersect at P, then |AD| + |BC| <= |AP| + |PD| + |BP| + |PD| = |AC| + |BD| and similarly |AB| + |CD| <= |AC| + |BD|. So any route that includes the segments AC and BD can be improved by replacing them with either AD and BC or AB and CD (whichever keeps the route connected). Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 ============================================================================== From: Antti Huima Subject: Re: No crossing in TSP? Date: 20 Jan 2000 18:28:43 +0200 Newsgroups: sci.math Xavier Gabaix writes: > Hi > > It's probably well-known, but I was wondering if somebody could give me > a quick ref: take the traveling salesman problem, with cities in real > Euclidean space (R^2), no 3 cities are aligned, and there's a straight > road between any 2 cities. It looks like the optimal path does not have > roads that cross, i.e. the salesman does not visit any point (on any > road) twice. > > Is that true? > > Thanks > > Xavier Assume that the optimal solution has a cross: 1 2 \ / X (1) / \ 3 4 You could transform this to either 1---2 (2) 3---4 or 1 2 | | | | (3) | | 3 4 and, because of the triangle inequality, you would make the total path shorter (as you didn't have three cities on the same line). It is thus enough to show that you can transform (1) always either to (2) or to (3). The only case where (1)->(2) cannot be done is if the transformation splits the walk into two disjoint components. But then the transformation (1)->(3) must join the components together, so you can always either (1)->(2) or (1)->(3). So it seems that an optimal path does not have crossings. -- Antti Huima ============================================================================== From: "Steven Sivek" Subject: Re: source code for TSP problem Date: Tue, 26 Dec 2000 15:58:59 GMT Newsgroups: sci.math MST algorithms are fairly simple but aren't used to solve TSP - a spanning tree can't even be a circuit because it won't have any cycles at all. Here's some (untested) code for Prim's algorithm; if you need to know which edges are used, you can either modify it to remember to which node any node in the tree is closest, or you can use Kruskal's algorithm: #define min(a, b) (((a) < (b)) ? (a) : (b)) int prim() // N is the number of vertices; adj[N][N] is the adjacency matrix // if two nodes a, b are not connected by an edge, then adj[a][b] == INFINITY // For simplicity, the adjacency matrix is assumed to be symmetric // Additionally, the graph is assumed to be connected (i.e., a spanning tree exists) { int i, j, best1, best2; int dist[N], sum=0; for (i = 0; i < N; i++) dist[i] = INFINITY; // initialize distances to the tree best1 = 0, best2 = 0; for (i = 1; i < N; i++) for (j = 0; j < i; j++) if (adj[i][j] < adj[best1][best2]) best1 = i, best2 = j; dist[best1] = dist[best2] = 0; // update distances to the tree for (i = 0; i < N; i++) { dist[i] = min(dist[i], adj[i][best1]); dist[i] = min(dist[i], adj[i][best2]); } sum = adj[best1][best2]; while (1) { best = 0; for (i = 1; i < N; i++) if (dist[i] < dist[best] || (dist[i] && !dist[best])) best = i; if (!dist[best]) break; // has every node been added to the tree? sum += dist[best]; // update the tree's length dist[best] = 0; // update the distances to the tree for (i = 0; i < N; i++) dist[i] = min(dist[i], adj[i][best]); } return sum; } If you want to try Kruskal's algorithm instead, the pseudocode is fairly simple: 1. Start by selecting the shortest edge and adding it to the tree. 2. Select the shortest edge which would not complete a cycle in the tree and add it. 3. Repeat step 2 until you have a minimum spanning tree (with V-1 edges). Steven Sivek stevensivek@hotmail.com weihua sheng wrote in article <3A48030F.DCA76FA5@egr.msu.edu>... > Hi, > > Could anyone tell me where to get the free source code to solve the TSP > using approximate algorithms like Christofides's algorithm? or the > Minimum Spanning Tree algorithm? Thanks in advance. > > weihua > > >