sa.c

清华大学《人工智能导论》课程电子教案,给大家看看

//采用模拟退火算法求解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;
}