tsp.cpp

人智经典算法的实现

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

const double a=0.92;

double distance(double *xx,double * yy,int num)
{
	double dis=0.0;
	for(int i=0;i<num-1;i++)
	{
		dis+=sqrt(pow(xx[i+1]-xx[i],2)+pow(yy[i+1]-yy[i],2));
	}
	dis+=sqrt(pow(xx[num-1]-xx[0],2)+pow(yy[num-1]-yy[0],2));
	return dis;
}
template <typename T>
void copy(T *& w1,T * w2, int num)
{
	for(int i=0;i<num;i++)
	{
		w1[i]=w2[i];
	}
}
template <typename T>
void change(T  *&Array,int index1,int index2,int num)
{
	//if(index2-index1>2)
//	{
		while(index1<=index2)
		{
			T temp=Array[index1];
			Array[index1]=Array[index2];
			Array[index2]=temp;
			index1++;
			index2--;
		}
//	}
}
int min(int a,int b)
{
	if(a>b)
		return b;
	else return a;
}
int max(int a,int b)
{
	if(a>b)
		return a;
	else return b;
}

int main()                                                                  //主函数
{
	char FileName[50];
	cin>>FileName;
	cout<<"做十次模拟退火算法的结果如下:"<<endl;
/*###################实现模拟退火过程##########################*/
	srand((unsigned int) time(NULL));
for(int m=0;m<10;m++){
	ifstream in= ifstream(FileName);
	if(!in)
	{
		cout<<"文件打开失败"<<endl;
		return 0;
	}
/****************************实现文件读写,保存读入内容**********************/
	int cityNum=0;
	in>>cityNum;
	double  * x=new double[cityNum];					  //存放每个城市y坐标的数组
    double  * y=new double[cityNum];					  //存放每个城市xy坐标的数组
    char  * city=new char[cityNum];				  //存放城市名称的数组中
    double  * newX=new double[cityNum];					  
    double  * newY=new double[cityNum];
    int index=0;
	  while(in>>city[index]){
	   double dis;
		in>>dis;
		x[index]=dis;
		in>>dis;
		y[index]=dis;
		index++;
   }
	//srand((unsigned int) time(NULL));
/****************************文件读写完毕*****************************************/
	int  *theWay=new int[cityNum];
	double  *t=new double[350];                                 //存放降温过程中产生的温度
	for(int i=0;i<cityNum;i++)                               //随机选择一个解
		theWay[i]=i;
	int k=0;
	t[k]=280.0;
	double targetF=distance(x,y,cityNum);
	 double lastF;
	// srand((unsigned int) time(NULL));
	 do{
		    lastF=targetF;
			double newTar;
			int  * newWay=new int[cityNum];
			//srand((unsigned int) time(NULL));
							for(int l=0;l<100*cityNum;l++)                    //每一个温度下迭代100*cityNum次
							{
								/***********产生一组新解*/
								copy(newX,x,cityNum);   
								copy(newY,y,cityNum);
								copy(newWay,theWay,cityNum); 
									int  u=rand()%cityNum;
									int  v=rand()%cityNum;
									 u=min(u,v);
									 v=max(u,v);
									 if(v==0||u==v)continue;
								change(newWay,u,v,cityNum);            
								change(newX,u,v,cityNum);
								change(newY,u,v,cityNum);
								/***********产生新解结束*********/

								newTar=distance(newX,newY,cityNum);
								if(newTar<targetF){
									targetF=newTar;
									copy(theWay,newWay,cityNum);
									copy(x,newX,cityNum);
									copy(y,newY,cityNum);
									//change(theWay,u,v,cityNum);    
									continue;
								}
								else{
									//cout<<targetF<<"   "<<newTar<<endl;
										double p=exp(((targetF-newTar))/t[k]);
										//cout<<p<<endl;
										if(p>(double)rand()/RAND_MAX)
										{
											targetF=newTar;
											copy(theWay,newWay,cityNum);
											copy(x,newX,cityNum);
											copy(y,newY,cityNum);
											//change(theWay,u,v,cityNum);    
											continue;
										}
								}
							}
		k++;
		t[k]=a*t[k-1];
	}while(targetF!=lastF);                                                            //外层循环结束条件是相邻两温度下的解无变化

/*###################模拟退火过程结束##########################*/
		cout<<"城市序列:";
								for(int i=0;i<cityNum;i++)
									cout<<city[theWay[i]];
								    cout<<endl;
									cout<<"路径距离:";
									cout<<targetF<<endl;
}
	//cout<<"   "<<targetF<<endl;
	return 0;
}