/*-------------------------------------------------------------------------- Approximate TSP solvers. See p.363, "Discrete Optimization Algorithms," Maciej Syslo, Prentice-Hall --------------------------------------------------------------------------*/ static char SCCSID[] = "@(#)tsp.c 1.1 5/20/92"; #include #include #include #include #include #ifdef ARRAYTEST /* see pg. 367, Syslo */ #define DIST(a,b) DISTa[a][b] #define BIG 0 /* book is wrong */ static int DISTa[6][6] = { {BIG, 3, 93, 13, 33, 9}, {4, BIG, 77, 42, 21, 16}, {45, 17, BIG, 36, 16, 28}, {39, 90, 80, BIG, 56, 7}, {28, 46, 88, 33, BIG, 25}, {3, 88, 18, 46, 92, BIG}}; #else /* warning: this macro cannot be called twice in the same arithmetic * expression */ static int dx, dy; #define DIST(a,b) \ (dx=(x[a]-x[b]),dy=(y[a]-y[b]),(int)(0.5+sqrt((double)(dx*dx+dy*dy)))) #endif /*-------------------------------------------------------------------------- Approximate solver using the Farthest Insertion heuristic. Returns total distance of one-way trip generated by deleting longest edge of cycle. If nih is TRUE, uses Nearest Insertion heuristic instead. --------------------------------------------------------------------------*/ int tsp_fi( /* Inputs: */ int n, /* number of nodes */ int s, /* starting node */ int *x, /* X coordinate of each node */ int *y, /* Y coordinate of each node */ int nih, /* if TRUE, use nearest insertion heuristic */ /* Output: */ int *route) /* route[i=0..n-1]= index of ith node in tour */ { int end1, end2; int i, j, argmaxcost; int index, nextindex; int inscost, newcost, total_cost, maxcost; int *cycle; /* cycle[i]=next node after node i in tour; -1 if not yet in */ int *dist; /* dist[i] =dist from any node in tour to node i not in tour */ assert(n > 0); /* Allocate variable-sized arrays */ cycle = (int *)malloc(n * sizeof(cycle[0])); assert(cycle != NULL); dist = (int *)malloc(n * sizeof(dist[0])); assert(dist != NULL); /* No nodes in tour yet */ for (i=0; i maxcost)) || (nih&&(dist[j]= 0 && argmaxcost < n); /* Farthest node is argmaxcost, distance is maxcost. */ /* Now find cheapest place to insert it into the tour. */ inscost = MAXINT; index = s; for (j=0; j<=i; j++) { nextindex = cycle[index]; assert(nextindex >= 0 && nextindex < n); newcost = DIST(index, argmaxcost); newcost += DIST(argmaxcost, nextindex); newcost -= DIST(index, nextindex); if (newcost < inscost) { inscost = newcost; end1 = index; end2 = nextindex; } index = nextindex; } /* Cheapest place is after end1 and before end2. Insert it there. */ assert(cycle[end1] == end2); cycle[end1] = argmaxcost; cycle[argmaxcost] = end2; total_cost += inscost; #if 0 printf("Inserting node %d between %d and %d\n", argmaxcost, end1, end2); printf("Total_cost %d += (%d+%d-%d) = %d\n", total_cost-inscost, DIST(end1,argmaxcost), DIST(argmaxcost,end2),DIST(end1,end2),total_cost); #endif /* Now that there's a new node in the tour, update the array of * distances from other nodes to the tour. */ for (j=0; j maxcost) { maxcost = newcost; argmaxcost = index; } index = cycle[index]; } #if 0 printf("Longest move in tour is %d,%d, cost %d\n", argmaxcost, cycle[argmaxcost], maxcost); #endif /* Return the tour to the caller as an array of nodes to visit * rather than a map {current node, next node} as it is in dist[]. * Start tour such that longest move in tour is (route[n-1],route[0]). */ #ifdef ARRAYTEST maxcost = 0; index = s; #else index = cycle[argmaxcost]; #endif for (i=0; i