sa.cpp

用经典算法--模拟退火算法求解经典问题旅行商（Travel Sales Problem）问题。

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <sys/types.h>
#include <signal.h>

#define INIT_TEMP		200.0

#define myrandom(x)		rand()%x
#define uniform(min, max)	(double)min+(double)(max-min)*((double)(rand()%10000)/10000.0)
#define sgn(x)			((x>0) ? 1 : ((x==0) ? 0 : -1))


typedef struct __node_t {
	int 	x;
	int	y;
} node_t;

double	**distant;

void inversion(int i, int j, int *path, int n);
void translation(int i, int j, int *path, int n);
void switching(int i, int j, int *path, int n);
void print_path(int *path, int n);
void fprint_path(FILE*, int *path, int n);
double path_len(int *path, int n);
void copy_path(int *path, int *path, int n);


void main(int argc, char *argv[])
{
	FILE	*infile, *outfile;
	int	node_n, i, j, k;
	node_t	*nodes;
	int	*path, *path_trial;

	

	
	if (argc<3) {
		printf("USAGE: %s infile outfile\n", argv[0]);
		exit(1);
	}
	
	if ((infile=fopen(argv[1], "r"))==NULL) {
		printf("I can not open file %s\n", argv[1]);
		exit(1);
	}

	if ((outfile=fopen(argv[2], "w"))==NULL) {
		printf("I can not open file %s\n", argv[2]);
		exit(1);
	}
	
	fscanf(infile, "%d\n", &node_n);
	
	nodes = new node_t[node_n];
	path = new int[node_n];
	path_trial = new int[node_n];

	for (i=0; i<node_n; i++) {
		fscanf(infile, "%d %d %d \n", &k, &(nodes[i].x), &(nodes[i].y));
		path[i]=i;
	}

	distant = new (double*)[node_n];

	for (i=0; i<node_n; i++) {
		distant[i] = new double[node_n];
	}
	
	for (i=0; i<node_n; i++) 
		for (j=i; j<node_n; j++) {
			distant[j][i] = distant[i][j] 
			= sqrt((double)((nodes[i].x-nodes[j].x)*(nodes[i].x-nodes[j].x)+
			(nodes[i].y-nodes[j].y)*(nodes[i].y-nodes[j].y)));
#ifdef	DEBUG
			printf("%d: %d %d, %d: %d %d -> %f\n", i, 
				nodes[i].x, nodes[i].y, j, nodes[j].x, nodes[j].y,
				distant[i][j]);
#endif
		}

	srand(time(NULL));
	
	double	temp, cost;
	double	dc, tc;

	temp = INIT_TEMP;
	cost = path_len(path, node_n);

	k = 1;

     if (node_n>2)
	while (temp>0.000001) {
		copy_path(path_trial, path, node_n);
		i = myrandom(node_n);
		j = myrandom(node_n);
		while (j==i) j = myrandom(node_n);

		inversion(i, j, path_trial, node_n);

		tc = path_len(path_trial, node_n);
		dc = tc-cost;

		if (dc<0.0) {
			copy_path(path, path_trial, node_n);
			cost = tc;
		} else if(uniform(0.0, 1.0)<exp(-dc/temp)) {
			copy_path(path, path_trial, node_n);
			cost = tc;
		}
		temp *= 0.999;
		printf("%d %d\n", k, (int)cost);
		fprintf(outfile, "%d %d\n", k, (int)cost);
		k++;
	}
	print_path(path, node_n);
	fprint_path(outfile, path, node_n);
	fclose(infile);
}
		
	
void inversion(int i, int j, int *path, int n)
{
	int p, q, tmp;

#ifdef DEBUG
	printf("Before inversion... %d %d\n", i, j);
	print_path(path, n);
#endif
	if ((p = i+1)>=n) p = 0;
	if ((q = j-1)<0) q = n-1;

	while (abs(q-p)>1&&abs(q-p)!=n-1) {
		tmp = path[p];
		path[p] = path[q];
		path[q] = tmp;
		if (++p>=n) p = 0;
		if (--q<0) q = n-1;
	}
	tmp = path[p];
	path[p] = path[q];
	path[q] = tmp;
		
#ifdef DEBUG
	printf("After inversion...\n");
	print_path(path, n);
	printf("\n");
#endif	
}

void translation(int i, int j, int *path, int n)
{
	int p, q, r, tmp;

#ifdef DEBUG
	printf("Before translation... %d %d\n", i, j);
	print_path(path, n);
#endif
	if ((r = i+1)>=n) r = 0;
	if ((q = j+1)>=n) q = 0;

	tmp = path[q];	

	while (p!=r) {
		if ((p=j-1)<0) p = n-1;
		if ((q=j+1)>=n) q = 0;
		path[q]=path[p];
		path[p]=path[j];
		if ((--j)<0) j = n-1;;
	}
	
	if ((++p)>=n) p = 0;
	path[p]=tmp;	
		
#ifdef DEBUG
	printf("After translation...\n");
	print_path(path, n);
	printf("\n");
#endif	
}

void switching(int i, int j, int *path, int n)
{
	int tmp;

#ifdef DEBUG
	printf("Before switching...%d %d\n", i, j);
	print_path(path, n);
#endif

	tmp = path[i];
	path[i] = path[j];
	path[j] = tmp;
		
#ifdef DEBUG
	printf("After switching...\n");
	print_path(path, n);
	printf("\n");
#endif	
}
		

void print_path(int *path, int n) 
{
 	int i;
	
	for (i=0; i<n; i++) {
		printf("%d \n", path[i]);
	}
	printf("\n");
}

void fprint_path(FILE* f, int *path, int n) 
{
 	int i;
	
	for (i=0; i<n; i++) {
		fprintf(f, "%d \n", path[i]);
	}
	printf("\n");
}


double path_len(int *path, int n)
{
	double total = 0.0;
	int i, j;

	for (i=0; i<n-1; i++) {
		total += distant[path[i]][path[i+1]];
	}
	total+= distant[path[0]][path[n-1]];

	return total;
}

void copy_path(int *dest, int *src, int n)
{
	int i;
	
	for (i=0; i<n; i++) 
		dest[i] = src[i];
}