sa3.cpp

模拟退火算法解旅行商问题（须运行在VS2008平台下）

/*********************************
模拟退火算法(SA)求解旅行商(TSP)问题
06373055 陈宗泽
2008.12.18
**********************************/


#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <ctime>
using namespace std;

#define  TERMINATE   0.000001     //终结差
#define  p0          0.95         //温度下降系数
#define  MAX_COUNT   2            //路程多少没有变化时结束
#define  TEMP		 280          //初始温度
#define  MAX_CITY    200          //最大城市数
struct Point
{
	double x,y;
};

Point citys[20];				//城市的坐标,用数组记录
int n;  						//城市数目
double t0;  					//初始温度
double bestLength;				//最优解
double preLength;				//前一次的解，用来判断结束条件
double currentLength;			//当前解
int  LOOP;						//循环次数, 为100*n
int  bestPath[MAX_CITY+1];	     		//最佳城市路线
int  currentPath[MAX_CITY+1];			//当前城市路线

/*******************
计算两个城市之间的距离
*******************/
inline double calcDis(int a, int b) //返回点A和点B之间的距离
{
a--;b--;

	double dis = 
		sqrt((citys[a].x-citys[b].x)*(citys[a].x-citys[b].x)+(citys[a].y-citys[b].y)*(citys[a].y-citys[b].y));
	return dis;
}
/*******************
计算路线的长度
*******************/
double pathLength(int p[]) 
{
	double length = 0;
	for(int i = 0; i <n; i ++) 
		length += calcDis(p[i], p[i + 1]);
	return length;
}
/********************
初始化函数,读入数据,初始化温度和路线等
********************/
void initialize()
{
	FILE *infile,*outfile;
	if((infile=fopen("1.in","r"))==NULL)
	{
		cout<<"cann't open 1.in"<<endl;
		system("pause");
		exit(1);
	}
	
	fscanf(infile, "%d",&n);
	for(int i=0;i<n;i++)
		citys[i].x=citys[i].y=0;
	for(int i=0;i<n;i++)
	{
		

		int c;double x,y;
		fscanf(infile,"%d",&c);
		fscanf(infile,"%lf",&x);
		fscanf(infile,"%lf",&y);
		citys[c-1].x=x;
		citys[c-1].y=y;
		if(i==0)
		{ citys[n].x=x;citys[n].y=y;}
	}
	
	fclose(infile);
/*
    if ((outfile= fopen("1.out","w"))==NULL)
    {
		system("pause");
		exit(1);
    }
*/

	t0 = TEMP;										//初始温度
	LOOP = 100 * n;									//每一个温度的循环次数
	memset(bestPath,0,sizeof(bestPath));
	cout << "\n初始状态: " ;

	//fprintf(outfile,"初始线路:  ");

	//fprintf(galog, "\n generation  best  average  standard \n");
	
	for (int i = 0; i < n; i++)
	{
		bestPath[i]=i+1;		//初始化路线序列
		cout<<bestPath[i]<<"-";
	}
	bestPath[n]=1;
	cout << "初始温度: " << t0;
    
	
	bestLength = pathLength(bestPath);				//初始化最优解

}


/********************
交换城市rand1和rand2之间的方向
********************/
void swap(int rand1, int rand2)
{
	if(rand1 > rand2) 
	{
		int temp = rand1;
		rand1 = rand2;
		rand2 = temp;
	}

	for(int i = 1; i <= (rand2 - rand1 - 1) / 2; i ++) 
	{
		int temp = currentPath[rand1 + i];
		currentPath[rand1 + i] = currentPath[rand2 - i];
		currentPath[rand2 - i] = temp;
	}
}

/*********************
判断当前解是否满足接受的概率
*********************/
bool IsAccept(double bestLength, double currentLength, double t)
{
	double p = (double)rand() / (double)(RAND_MAX);
	double pt = exp((bestLength - currentLength) / t);
	if(pt > p) 
		return true;
	else 
		return false;
}
/*********************
模拟退火算法的具体函数
*********************/
void SA() {
	double t = t0;
	int count = 0;				
	while(1) 
	{
		for(int i = 0; i < LOOP; i ++) 
		{

			for(int i=0;i<=n;i++)
				currentPath[i]=bestPath[i];

			int rand1 = rand() % (n + 1);
			int rand2 = rand() % (n + 1);
			while(abs(rand1 - rand2) < 3)
				rand2 = rand() % (n + 1);


			swap(rand1, rand2);

			//计算新解
			double currentLength = pathLength(currentPath);		
		    
			//判断是否应该接受新解
			if(currentLength - bestLength < TERMINATE) 
			{
				bestLength = currentLength;
				
				for(int i=0;i<=n;i++)
					bestPath[i]=currentPath[i];
			} else

    		if (IsAccept(bestLength, currentLength, t))
				{
					bestLength = currentLength;	
					for(int i=0;i<=n;i++)
					{
						bestPath[i]=currentPath[i];
					}
				}
		}

		if(fabs(preLength - bestLength) < TERMINATE) 
		{
			count++;
			//满足结束条件，输出终结状态，MAX_COUNT标记结束时要求的结果不变的次数
			if(count > MAX_COUNT) 
			{
				cout << "\n终结路线: ";
				for(int i=0;i<n;i++)
					cout<<bestPath[i]<<"-";
				cout<< "  路线：" << bestLength << endl;
				return;
			}
		} 
		else 
		{
			preLength = bestLength;
			count = 0;
		}
		//每次输出当前温度下的计算结果
		cout << "\n当前温度：" << t << "   路线：-";
		for(int i=0;i<n;i++)
			cout<< bestPath[i]<<"-";
		cout<< "  路长：" << bestLength << endl;
		//温度下降
		t = t * p0;
	}
}


int main()
{
    initialize();
    SA();
system("pause");
}