Has anybody here delt with the travelling salesman problem before?
Woudl anybody know an algorithm or psuedocode for trying to solve the travelling salesman problem.
If anyone else has any other advice it would be much appreciated
Printable View
Has anybody here delt with the travelling salesman problem before?
Woudl anybody know an algorithm or psuedocode for trying to solve the travelling salesman problem.
If anyone else has any other advice it would be much appreciated
?
>Has anybody here delt with the travelling salesman problem before?
Yes.
>If anyone else has any other advice it would be much appreciated
Web searches do wonders for finding algorithms and source code when you don't want to figure it out yourself.
-Prelude
Well websearches produced nothing for me and all i wanted is a bit of help to get started.
8000 hits on Google at:
http://www.google.com/search?hl=en&i...=Google+Search
I hardly found anything useful, but i did find this piece of code which i am not really understanding well...
Can anyone explian it to me?/Code:/*
* This program checks the length of a tour. Give the points data file
* name on the command line.
*/
#include <stdio.h>
#include <math.h>
typedef struct _point {
float x, y, z;
} point;
float distance (point v[], int i, int j) {
float dx, dy, dz;
dx = v[i].x - v[j].x;
dy = v[i].y - v[j].y;
dz = v[i].z - v[j].z;
return sqrt (dx*dx + dy*dy + dz*dz);
}
float tour_length (int tour[], point v[], int n) {
int i, from, to;
float sum;
/* sum up distances between cities on the tour */
sum = 0;
/* start at city 0 */
from = 0;
for (i=1; i<n; i++) {
/* find distance to next city in tour */
to = tour[i];
/* add that to the length of the tour */
sum += distance (v, from, to);
/* the next source is the current target */
from = to;
}
/* add in the distance back to the first city */
sum += distance (v, from, 0);
return sum;
}
int main (int argc, char *argv[]) {
char present[1000];
int i, j, n, tour[1000];
float length, min;
point cities[1000];
FILE *f;
if (argc != 2) {
fprintf (stderr, "Usage: %s <filename>\n", argv[0]);
exit (1);
}
f = fopen (argv[1], "r");
if (!f) {
perror (argv[1]);
exit (1);
}
fscanf (f, "%d\n", &n);
for (i=0; i<n; i++) {
fscanf (f, "%f %f %f\n", &cities[i].x, &cities[i].y, &cities
[i].z);
}
fclose (f);
bzero (present, n);
for (i=0; i<n; i++) {
scanf ("%i", &tour[i]);
if (feof (stdin)) {
fprintf (stderr, "unexpected end of file!\n");
exit (1);
}
if (tour[i] >= 0 && tour[i] < n)
present[i] = 1;
else {
fprintf (stderr, "index %d out of bounds!\n", tour
[i]);
exit (1);
}
}
for (i=0; i<n; i++) if (!present[i]) {
fprintf (stderr, "not all points in tour, missing %d!\n",
i);
exit (1);
}
length = tour_length (tour, cities, n);
printf ("length of tour is %f\n", length);
exit (0);
}