main.cpp

人工智能中

/*初始温度t0固定为280
 *降温方法为t=t*0.92
 *在同一温度内循环计算100*N次(城市数)
 *以总路径长作为指标函数f，
 *新状态j，如果f(j)-f(i)<=0,则接受新状态
 *若f(j)-f(i)>0，则以概率e^(-(f(j)-f(i))/t)接受新状态
 *当相邻两个温度得到的状态路径长没有变化时，认为算法结束
 */
#include<iostream>
#include<fstream>
#include<cmath>
#include<ctime>
using namespace std;

double const e=2.718281828;
double **nodes;	 //结点坐标
char **nodenames;//结点名字
double **dis;	//结点之间的距离
int N;			//结点数
void solution(double t0,double k,int L)		//初始温度t0，温度下降系数k，同温下状态交换次数
{
	int i;
	int *rst=new int[N+1];
	double length=0;
	int r1,r2;
	double t=t0;
	int l=0;
	double ff=0;
	int temp=0;
	double lentemp;
	srand((unsigned int)time(NULL));
	while(true)						//无限循环
	{
		t=t0;
		ff=0;
		length=0;
		for(i=0;i<N;++i)				//初始解，就按照输入次序
		{
			rst[i]=i;
			if(i<N-1)	length+=dis[i][i+1];
		}
		rst[N]=0;
		length+=dis[rst[N-1]][rst[N]];
		lentemp=length;
		do
		{
			l=0;
			length=lentemp;
			while(l<L)					//同温下状态交换
			{
				do
				{
					r1=rand()%(N-1)+1;
					r2=rand()%(N-1)+1;
				}while(r1==r2);
				if(r2<r1)
				{
					temp=r2;
					r2=r1;
					r1=temp;
				}
				ff=dis[rst[r1-1]][rst[r2]]-dis[rst[r1-1]][rst[r1]]		//计算指标函数的变化
					+dis[rst[r1]][rst[r2+1]]-dis[rst[r2]][rst[r2+1]];
				if(ff<=0||((double)rand()/RAND_MAX)<=pow(e,-ff/t))		//满足交换条件
				{
					lentemp=lentemp+ff;
					while(r1<r2)
					{
						temp=rst[r1];
						rst[r1]=rst[r2];
						rst[r2]=temp;
						r1++;
						r2--;
					}
				}
				l++;
			}
			t=t*k;
		}while(length!=lentemp);  //相邻两个温度得到的最终状态长度相同时结束
		for(i=0;i<N+1;++i)	
			printf("%s ",nodenames[rst[i]]);
		printf("length:%f\n",lentemp);
	}
	delete [] rst ;
}
int main()
{
	char file[20];
	cout<<"Input the name of test file:";
	cin>>file;
	ifstream fin(file);
	if(!fin)
	{
		cerr<<"Open file error."<<endl;
		return 1;
	}
	fin>>N;
	nodes=new double* [N];
	nodenames=new char *[N];
	int i=0;
	while(i<N)
	{
		nodes[i]=new double[2];
		nodenames[i]=new char[10];
		fin>>nodenames[i];
		fin>>nodes[i][0]>>nodes[i][1];
		i++;
	}
	fin.close();
	dis=new double* [N];
	for(i=0;i<N;++i)		//计算任意两点之间的距离
	{
		dis[i]=new double [N];
		for(int j=0;j<N;++j)
		{
			if(i==j) dis[i][j]=0;
			else
			{
				if(i>j) dis[i][j]=dis[j][i];
				else
				{
					double x=nodes[i][0]-nodes[j][0];
					double y=nodes[i][1]-nodes[j][1];
					dis[i][j]=sqrt(x*x+y*y);
				}
			}
		}
	}
	solution(280,0.92,100*N);
	return 0;
}