main.cpp

用模拟退火算法来解旅行商问题

//采用课件中康立山等人的改进方法：
//			初始温度t0=28000；
//			在每个温度下采用固定的迭代次数，Lk=400n，n为城市数；
//			温度的衰减系数＝0.96，即tk+1=0.96*tk；
//			算法的停止准则为：当相邻10个温度得到的解无任何变化时算法停止。 
//初始城市序列为: 1, 2, 3, ..., n
#include<iostream>
#include<cmath>
#include<string>
#include<fstream>
#include<ctime>
#include<cstdlib>
using namespace std;
#define e 2.718281828459
#define max	100
int n;						//城市总数
double t = 28000;				//温度
int k;					//每个温度下的迭代次数
double d = 0.97;				//衰减系数
struct City
{
	double x;
	double y;
	string name;
};

City cityArray[max];
City tempArray[max];			//用于城市互换时
double getDis();				//得到当前序列的总距离
double getDis(int, int);		//得到两个城市间的距离
void print();					//输出当前城市序列和路径距离
int main()
{
	//infile
	string fileName;
	cin>>fileName;
	ifstream infile;
	infile.open(fileName.c_str());
	if (!infile) {
		cerr<<"infile error!"<<endl;
		return -1;
	}
	infile>>n;
	k = 400*n;
	for (int i=0; i<n; i++) {
		City newCity;
		infile>>newCity.name>>newCity.x>>newCity.y;
		cityArray[i] = newCity;
	}
	infile.close();

	//开始模拟退火
	double formerDis[10] = {0};
	formerDis[9] = getDis();
	double currentDis = 0;
	double delta = 0.0;
	bool flag;			//是否终止标志
	srand(19871019);
	while(true)
	{
		flag = true;
		for (int i=0; i<10; i++) {
			if (formerDis[i] != currentDis) {
				flag = false;
				break;
			}
		}
		if (flag)					//连续10个值都相同，退出
			break;
		for (int i=0; i<9; i++)
			formerDis[i] = formerDis[i+1];
		formerDis[9] = currentDis;
		int count = 0;
		while(count < k)
		{
			//从领域中随机取一个解
			int first = (int)(((float)rand()/RAND_MAX)*n);
			int second = (int)(((float)rand()/RAND_MAX)*n);
			if (first > second) {
				int temp = first;
				first = second;
				second = temp;
			}
			delta = getDis(first, second - 1) + getDis(first + 1, second)
					- getDis(first, first + 1) - getDis(second - 1, second);
			if (delta < 0 || pow(e, -delta/t) > rand()/RAND_MAX) {			//进行交换
				for (int i = first+1; i<=second-1; i++)
					tempArray[i] = cityArray[i];
				for (int i = first+1; i<=second-1; i++)
					cityArray[i] = tempArray[first+second-i];
				currentDis = getDis();
				//print();
			}
			count++;
		}
		t *= d;
		currentDis = getDis();
		cout<<"-----------------------------------"<<endl;
		cout<<"当前温度: "<<t<<endl;
		print();
	}
	cout<<"结果为："<<endl;
	print();
	return 0;
}
double getDis()
{
	double dis = 0.0;
	for (int i=0; i<n; i++)
	{
		dis += getDis(i, i+1);
	}
	return dis;
}
double getDis(int i, int j)
{
	if (i > n-1)
		i -= n;
	if (j > n-1)
		j -= n;
	return sqrt(pow((cityArray[i].x - cityArray[j].x),2.0)
			+ pow((cityArray[i].y - cityArray[j].y), 2.0));
}
void print()
{
	cout<<"城市序列: (";
	for (int i=0; i<n-1; i++)
		cout<<cityArray[i].name<<",";
	cout<<cityArray[n-1].name<<")";
	cout<<"路径距离:"<<getDis()<<endl;
}