//采用模擬退火算法求解TSP問題
//作者：馬少平
//時間：2007年5月

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define	T0		200			//初始溫度
#define	ALPHA	0.95		//溫度衰減系數
#define	LK		100			//每個溫度下的迭代次數為城市數的倍數，即迭代n*LK次，其中n為城市數
#define MAXN	100			//最大城市數
#define MINT    0.01		//溫度小于該值時，結束

int		n;
char	name[MAXN];
double	pos[MAXN][2];
double	dis[MAXN][MAXN];

int Init(FILE *pFile)		//讀取數據文件，計算兩兩城市間的距離
{
	int i, j;

	fscanf(pFile, "%d", &n);

	for (i = 0; i < n; i++)
	{
		fscanf(pFile, " %c %lf %lf", &name[i], &pos[i][0], &pos[i][1]);
	}

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			dis[i][j] = sqrt((pos[i][0] - pos[j][0])*(pos[i][0] - pos[j][0]) + 
				             (pos[i][1] - pos[j][1])*(pos[i][1] - pos[j][1]));
		}
	}

	return n;
}

int InitPath(int n, int path[])		//隨機生成一條路徑，n為城市數，在path中得到一條路徑
{
	int i, p, m;

	for(i = 0; i < n; i++) path[i] = i;

	for (i = 0; i < n; i++)
	{
		p = rand()%n;
		m = path[i];
		path[i] = path[p];
		path[p] = m;
	}

	return n;
}

double Len(int n, int path[])		//計算給定路徑的長度
{
	double len = 0.0;
	int i;

	for (i = 0; i < n; i++)
	{
		len += dis[path[i]][path[(i+1)%n]];
	}
	return len;
}

void PrintPath(int n, int path[])
{
	int i;
	for (i = 0; i < n; i++)
	{
		printf ("%c", name[path[i]]);
	}
	printf("\n");
}

double Gen(int n, int path[], int u, int v, double t)		
//u、v（u<v）表示在u、v之間交換。
//t是當前溫度
//以path為基礎通過逆序交換的方法新生成一個路徑，如果該路徑被接受，則在path中得到該路徑，
//為了顧及到兩端的情況，交換前對path1進行一次循環位移
//返回該路徑的長度
{
	int i, j, p;
	double d;
	int path2[MAXN];
	
	p = rand()%n;

	for (i = p; i < n; i++)
	{
		path2[i-p] = path[i];
	}
	for (i = 0; i < p; i++)
	{
		path2[n-p+i] = path[i];
	}

	d = (dis[path2[u]][path2[v-1]] + dis[path2[u+1]][path2[v]]) 
		- (dis[path2[u]][path2[u+1]] + dis[path2[v-1]][path2[v]]);

	if (d < 0 || (1.0*rand()/RAND_MAX < exp(-d/t)))
	{
		i = u+1;
		j = v-1;
		while (i < j)
		{
			p = path2[i];
			path2[i] = path2[j];
			path2[j] = p;
			i++;
			j--;
		}

		for (i = 0; i < n; i++)
		{
			path[i] = path2[i];
		}
	}

	return Len(n, path);
}

double SA(int n, int path[])  //n為城市數，path得到路徑，返回值為路徑的長度
{
	int i, j;
	int u, v;
    double last, len = 1.0E20;
	double t = T0;
	double minlen = 1.0E20;
	int bestpath[MAXN];

	InitPath(n, path);

	do {
		last = len;
		for (i = 0; i < LK*n; i++)
		{
			do {
				u = rand()%n;
				v = rand()%n;
			} while ((v-u) <= 2);

			len = Gen(n, path, u, v, t);

			if (minlen > len) 
			{
				minlen = len;
				for (j = 0; j < n; j++)
				{
					bestpath[j] = path[j];
				}
			}
		}

		t = ALPHA*t;
	} while (t > MINT);

	for (i = 0; i < n; i++)
	{
		path[i] = bestpath[i];
	}

	return minlen;
}

int main()
{
	int path[MAXN];
	int i;
	double len;
	FILE *pFile = NULL;
	
	srand(time(NULL));

	pFile = fopen("TSP20.txt", "r");
	Init(pFile);
	fclose(pFile);

	for (i = 0; i < 10; i++)
	{
		len = SA(n, path);
	
		PrintPath(n, path);
	
		printf("len = %f\n", len);
	}

	return 0;
}