main.cpp

hws01:野人和传教士问题 hws02:用Romberg外推法求积分近似值 hws03:八数码问题 hws04:模拟退火算法 hws05:遗传算法解决旅行商问题

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

class City//定义城市这个类
{
public:
	char name;//城市的名称
	double x;//城市的x坐标
	double y;//城市的y坐标
};

vector<City> vec;//定义保存所有城市的容器

int main()
{
    const double T_MAX=300;
	const double T_MIN=0.001;
	const double alpha=0.95;
	
	int N;//城市的数目
	double distance =0.0; //定义路径的距离
	
	double T=T_MAX;//定义温度,并设初始值为300
	double delta;//给定温度下两个状态解的差值
	
	char filename[10]="";//定义文件名
	cout<<"Please input the filename:"<<endl;
	cin>>filename;//输入要打开的文件名
	ifstream fin(filename);//定义打开文件流

	if(!fin)//打开文件失败
	{
		cout<<"Open the file is faild!"<<endl;
		return 0;
	}
	
	fin>>N;//读入城市数目
	char word;
	double x;
	double y;
	while(fin>>word) //依次读入每个城市                          
	{
		City city;
		city.name=word;	
		fin>>x;
		city.x=x;
		fin>>y;
		city.y=y;
		vec.push_back(city);//把读入的城市放入容器vec中
		
    }
	
	int n[30];
	int i;
	for(i=0;i<N;i++)
	{
		n[i]=i;		
	}
	n[N]=0;
	
	for(i=0;i<N;i++)//随机产生一个初始解
	{		
		distance+=sqrt(pow(vec[n[i]].x-vec[n[i+1]].x,2.0) + pow(vec[n[i]].y-vec[n[i+1]].y,2.0));		
	}
	
	srand((unsigned int) time(NULL));//设置种子
    while(T>T_MIN)//温度T降低到足够小，算法最终结束的条件
	{  
		int num=0;
		while(num<=20*N)//内循环在给定的温度下达到热平衡 ，温度下降的次数num，比如10个城市时让它下降2000次，即同一温度内算法结束的条件
		{
			num++;
			int k1=rand()%(N+1);//随机产生两个城市
			int k2=rand()%(N+1);
			while((k2==k1)||(abs(k1-k2)==1))//如果两个城市不满足条件，再产生新的两个城市
			{
				k1=rand()%(N+1);
				k2=rand()%(N+1);
			}
			
			delta=0.0;
			if(k2>k1) //默认k1>k2
			{ 
			int k3=k1;
			k1=k2;
			k2=k3;
			}
			//两个城市间的逆序交换方式得到问题的一个新解,计算新旧两个解之间的差值
			delta=  sqrt(pow(vec[n[k1-1]].x-vec[n[k2]].x,2.0) + pow(vec[n[k1-1]].y-vec[n[k2]].y,2.0))
				   +sqrt(pow(vec[n[k1]].x-vec[n[k2+1]].x,2.0) + pow(vec[n[k1]].y-vec[n[k2+1]].y,2.0))
				   -sqrt(pow(vec[n[k2]].x-vec[n[k2+1]].x,2.0) + pow(vec[n[k2]].y-vec[n[k2+1]].y,2.0))
				   -sqrt(pow(vec[n[k1-1]].x-vec[n[k1]].x,2.0) + pow(vec[n[k1-1]].y-vec[n[k1]].y,2.0));
			
			if((delta<0)||(exp(-delta/T)>(double)rand()/RAND_MAX))//状态被接受的条件：新状态的值<旧状态的值或满足Metropolis准则
			{ 
				int temp;
				while(k2+1<k1-1)//当新解被接受时，交换k1和k2之间的城市
				{	
					k2++;
					k1--;
					temp=n[k2];
					n[k2]=n[k1];
					n[k1]=temp;

				}
				
                
				for(i=0;i<=N;i++)//输出城市序列
				{
					cout<<vec[n[i]].name<<" ";
				}
				distance=0.0;
				for(i=0;i<N;i++)//输出路径距离
				{
					distance+=sqrt(pow(vec[n[i]].x-vec[n[i+1]].x,2.0) + pow(vec[n[i]].y-vec[n[i+1]].y,2.0));		
				}
				cout<<distance<<endl;
				
			}
		}
		T=alpha*T;//温度下降函数
		
	}

	return 0;
}