version1.cpp

本程序用模拟退火算法实现了旅行商问题（tsp问题）

/*
指标函数：访问所有城市的路径的长度
新解的产生: 选择两个城市间的位置交换方式得到一个可能解的邻域， 在随机选择一个解
新解的接受准则：exp(-(fj-fi)/t)
初始温度的确定：产生一组解，使其平均接受概率为0.9
内循环次数：10n
温度的衰减系数：0.95
算法的停止准则：温度低于0.01获没有新解产生
*/

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

const long MAX=100;
struct City{
	double x,y;
} city[MAX];

//函数：读入数据--返回城市数目
long initial()
{
	long i,n;

	//读入城市的数目、ｘ坐标、ｙ坐标
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%lf%lf",&city[i].x,&city[i].y);
	return n;
}

//函数：计算指标函数f(i)的值
double cal_f(long *path,long n)
{
	long pre,i;
	double len;
	len=0.0;
	pre=path[0];
	for(i=1;i<n;i++){
		len+=sqrt((city[path[i]].x-city[pre].x)*(city[path[i]].x-city[pre].x)
			+(city[path[i]].y-city[pre].y)*(city[path[i]].y-city[pre].y));
		pre=path[i];
	}
    len+=sqrt((city[path[0]].x-city[pre].x)*(city[path[0]].x-city[pre].x)
			+(city[path[0]].y-city[pre].y)*(city[path[0]].y-city[pre].y));
	return len;
}

void generate_path(long *path,long n);
//函数：计算初始温度
double cal_temperature(long num)
{
	long j,n;
	double t,sum,fi,fj;
	long path[MAX];

	t=1.0;
	n=20*num;
	while(1){
		sum=0.0;
		generate_path(path,num);
		fi=cal_f(path,num);
		for(j=0;j<n;j++){
			generate_path(path,num);
			fj=cal_f(path,num);
			sum+=fi-fj;
			fi=fj;
		}
		if(exp(-(sum/n)/t)>=0.9)
			break;

		t*=1.05;
	};
	return t;
}

//函数：生成一个序列作为解
void generate_path(long *path,long n)
{
	long i,cnt,temp;
	long mark[MAX];

	for(i=0;i<n;i++)
		mark[i]=0;
	cnt=0;
	//srand(time(NULL)); //pay attention to随机数的生成？？
	while(cnt<n){
		temp=rand()%n;
		if(mark[temp]==0){
			mark[temp]=1;
			path[cnt]=temp;
			cnt++;
		}
	}
}

long main()
{
	freopen("text10.txt","r",stdin);

	clock_t start,finish;
	struct Neighbour{
		long path[MAX];
		bool flag;//true--未选择；false--已选择
	} neighbour[500]; //ok????
	bool flag,first;
	long i,j,k,t,temp;
	long num,pt,cnt_flag;
	double p;
	double fi,fj,temperature;
	long path[MAX],record[MAX];

	//输入部分：读入数据（表示城市间的距离）
	num=initial();
	fclose(stdin);

	srand(time(NULL));
	freopen("result.txt","w",stdout);
	//设定一个初始温度
	long h;
	for(h=0;h<20;h++){
	start=clock();
	temperature=cal_temperature(num);

	//随机选择一个初始解--生成一序列：0--n-1,并求f(i)
	generate_path(path,num);
	fi=cal_f(path,num);

	////////////////////////////////////////////////////////////////
	//外循环：模拟温度的下降过程（停止：t<0.01）
	first=true;
	while(1){

		if(first==false){
			for(t=0;t<num;t++)
				record[t]=path[t];
		}

		//内循环：采用固定迭代次数
		flag=true;
		for(k=0;k<10*num;k++){//k<100*num
			if(flag){
				//求邻域
				pt=0;
				for(i=1;i<num-1;i++){
					for(j=i+1;j<num;j++){
						for(t=0;t<num;t++)
							neighbour[pt].path[t]=path[t];
						neighbour[pt].flag=true;
						temp=neighbour[pt].path[i];
						neighbour[pt].path[i]=neighbour[pt].path[j];
						neighbour[pt].path[j]=temp;
						pt++;
					}
				}
				cnt_flag=pt;
			}
			
			if(cnt_flag==0)
				flag=true;
			else{
				flag=false;
				//从邻域中随机选择一个解j
				do{
					temp=rand()%pt;
				}while(neighbour[temp].flag==false);

				//计算f(j),并作选择
				neighbour[temp].flag=false;
				cnt_flag--;
				fj=cal_f(neighbour[temp].path,num);
				if(fi>fj){
					for(t=0;t<num;t++)
						path[t]=neighbour[temp].path[t];
					fi=fj;
					flag=true;
				}else{
					p=exp(-(fj-fi)/temperature);
					//srand(time(NULL));
					if(p>double(rand()%1000)/1000){ //ok????????
						for(t=0;t<num;t++)
							path[t]=neighbour[temp].path[t];
						fi=fj;
						flag=true;
					}
				}
			}
		}

		//降温
		temperature*=0.95;
		if(first==false){
			for(t=0;t<num;t++){
				if(record[t]!=path[t])
					break;
			}
			if(t==num&&temperature<1) break;
		}
		if(temperature<0.01) break;
		first=false;
	}
 
	//输出
	printf("\nNo.%d :\n",h+1);
	//printf(" The answer is ");
	for(t=0;t<num;t++)
		printf("%d ",path[t]);
	printf("\n%lf\n",cal_f(path,num));
	printf("%lf\n",temperature);
	finish=clock();
	printf("%8.5lf s\n\n",(double)(finish-start)/CLOCKS_PER_SEC);
	}

	return 0;
}



//求随机数!!!!