基于回溯法的TSP问题解决方案

基于回溯法的TSP问题解决方案，附有TSP问题相关的c++和matlab解法资料，及工程文件（西电02105143）

#include 
#include 
#include 
#include 
#include 
#define PI 3.141592
#define RRR 6378.388
using namespace std;
int n;
double longitude[10001];   //输入的GEO坐标或者XY坐标
double latitude[10001];
int cstep[10001];			//保存当前接受的状态
int nstep[10001];			//保存新扩展的状态
double minvalue;			//当前所接受的最短长度
double dis（int iint j）		//用于计算两个城市之间的距离
{
	//double q1q2q3;								//方法一为GEO坐标的距离算法，注释掉的为XY坐标的计算距离算法
//	q1 = cos（ longitude[i] - longitude[j] ）; 
	// q2 = cos（ latitude[i] - latitude[j] ）; 
	 //q3 = cos（ latitude[i] + latitude[j] ）; 
	 //return （int） （ RRR * acos（ 0.5*（（1.0+q1）*q2 - （1.0-q1）*q3） ） + 1.0）; 
	return sqrt（（longitude[i]-longitude[j]）*（longitude[i]-longitude[j]）+（latitude[i]-latitude[j]）*（latitude[i]-latitude[j]））;
}
void randomplace（）								//将初始状态任意交换两个位置得到一个起始状态
{
	int changenum;
	int xy;
	int i;
	int temp;
	changenum=rand（）;
	while（changenum>n ||changenum<1） changenum=rand（）;
	for（i=1;i<=changenum;i++）
	{
		x=rand（）;
		while（x>n ||x<1） x=rand（）;
		y=rand（）;
		while（y>n ||y<1 ||x==y） y=rand（）;
		temp=cstep[x];								//按随机数xy交换这两个位置的城市
		cstep[x]=cstep[y];
		cstep[y]=temp;
	}
}
void change（int state[]）							//随机将状态中从x到y步的城市逆序
{
	int xy;
	int temp;
	x=rand（）;
		while（x>n ||x<1） x=rand（）;
		y=rand（）;
		while（y>n ||y<1 ||x==y） y=rand（）;
		reverse（state+xstate+y）;
}
double compute（int state[]）							//计算当前状态的距离的和
{	
	int i;
	double value;
	value=0;
	for（i=2;i<=n;i++）
	{
		value+=dis（state[i]state[i-1]）;
	}
	value+=dis（state[1]state[n]）;
	return value;
}
int main（）
{
	ifstream input;
	ofstream output;
	int ij;
	int count;
	clock_t startfinish;
	double temperature;					//模拟退火的温度
	double templtempg;
	double mindeg;						//中间值的保存
	int receive;						//用于保存在每个温度下所接受状态的数目
	double newvalue;					//保存新扩展出的距离和
	double prevalue;					
	srand（（unsigned）time（NULL））;
	input.open（“tsp2.in“ios::in）;
	input >>n;
	for（i=1;i<=n;i++）					//读入距离
	{
		input >>j;
		input >>templ;
		input >>tempg;
		//deg=（int）templ;
		//min=templ-deg;
		//longitude[i]=PI * （deg + 5.0 * min/ 3.0） / 180.0; 
		//deg=（int）tempg;
		//min=tempg-deg;
	//	latitude[i]=PI * （deg + 5.0 * min/ 3.0） / 180.0;
		cstep[i]=i;
		longitude[i]=templ;
		latitude[i]=tempg;
	}

	input.close（）;
	for（int t=1;t<=10;t++）
	{
		start=clock（）;
	temperature=280;				//将初始温度设为280度
	randomplace（）;
	minvalue=compute（cstep）;		//计算初始状态的距离和
	prevalue=0;			
	while（1）
	{
		count=0;
		if（temperature<0.01 ） break;			//若温度小于0.01度随即结束搜索
		receive=0;	
		while（1）
		{
			if（count>100*n） break;				//每个温度下只扩展100*n次
			count++;
		
			for（i=1;i<=n;i++）
			{
				nstep[i]=cstep[i];
			}
			change（nstep）;
			newvalue=compute（nstep）;
			if（newvalue			{
				for（i=1;i<=n;i++）
				{
					cstep[i]=nstep[i];
				}
				minvalue=newvalue;
				receive++;
			}
			else 
			{
				double com;							//否则按一定的概率接受该解
				com=rand（）;
				whil

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     149079  2012-12-13 23:46  算法大作业TSP\02105143周萌（TSP问题）.pdf

     文件     305085  2006-05-08 21:13  算法大作业TSP\c++\TSP--传统算法.rar

     文件       3802  2009-12-14 17:47  算法大作业TSP\c++\tsp.cpp

     文件      88064  2010-12-01 21:45  算法大作业TSP\c++\TSPkeep\TSP.doc

     文件      10404  2012-12-09 20:32  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\BuildLog.htm

     文件         67  2012-12-09 20:32  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\mt.dep

     文件     357376  2012-12-09 20:32  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\TSP.exe

     文件        406  2012-12-09 17:51  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\TSP.exe.embed.manifest

     文件        472  2012-12-09 17:51  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\TSP.exe.embed.manifest.res

     文件        381  2012-12-09 20:32  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\TSP.exe.intermediate.manifest

     文件     173384  2012-12-09 20:32  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\TSP.ilk

     文件      15977  2012-12-09 20:32  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\TSP.obj

     文件    1780736  2012-12-09 20:32  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\TSP.pdb

     文件      33792  2010-12-01 21:50  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\vc60.idb

     文件      45056  2010-12-01 21:48  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\vc60.pdb

     文件      44032  2012-12-09 20:32  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\vc90.idb

     文件      61440  2012-12-09 20:32  算法大作业TSP\c++\TSPkeep\TSP工程\Debug\vc90.pdb

     文件       5574  2012-12-09 20:32  算法大作业TSP\c++\TSPkeep\TSP工程\TSP.C

     文件       3363  2010-12-01 21:49  算法大作业TSP\c++\TSPkeep\TSP工程\TSP.DSP

     文件        531  2010-12-01 21:50  算法大作业TSP\c++\TSPkeep\TSP工程\TSP.DSW

     文件     584704  2012-12-09 21:05  算法大作业TSP\c++\TSPkeep\TSP工程\TSP.ncb

     文件      53760  2010-12-01 21:52  算法大作业TSP\c++\TSPkeep\TSP工程\TSP.OPT

     文件        240  2010-12-01 21:49  算法大作业TSP\c++\TSPkeep\TSP工程\TSP.PLG

     文件        876  2012-12-09 20:32  算法大作业TSP\c++\TSPkeep\TSP工程\TSP.sln

    ..A..H.      8704  2012-12-09 21:05  算法大作业TSP\c++\TSPkeep\TSP工程\TSP.suo

     文件       4803  2012-12-09 20:32  算法大作业TSP\c++\TSPkeep\TSP工程\TSP.vcproj

     文件       1405  2012-12-09 21:05  算法大作业TSP\c++\TSPkeep\TSP工程\TSP.vcproj.c-PC.c.user

     文件      33543  2012-12-09 18:04  算法大作业TSP\c++\TSPkeep\图片1.png

     文件       6114  2012-12-09 20:21  算法大作业TSP\c++\TSPkeep\新建文件夹\TSP工程\Debug\BuildLog.htm

     文件         67  2012-12-09 20:21  算法大作业TSP\c++\TSPkeep\新建文件夹\TSP工程\Debug\mt.dep

............此处省略119个文件信息