tsp.cpp

TSP算法

// Tsp.cpp : Defines the entry point for the console application.
//

#include <fstream.h>
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#include <mmsystem.h>

#define CircleNum 1000

//30个城市选择下面的语句
//#define CityNum 30

//29个城市选择下面的语句
#define CityNum 29

//45个城市选择下面的语句
//#define CityNum 45

//此处设置初始最大路径长度
#define MaxDistance 1000000

int distance[CityNum][CityNum];
int city[CityNum],bestway[CityNum];
int cost,bestcost;
float runtime;

//30个城市选择下面的语句
//char cityname[CityNum][16]={"哈尔滨","长春","乌鲁木齐","沈阳","呼和浩特","北京","天津","银川","太原","济南","西宁","青岛","兰州","郑州","西安","南京","合肥","上海","成都","武汉","杭州","拉萨","重庆","长沙","贵阳","福州","桂林","昆明","广州","南宁"};

//29个城市选择下面的语句
char cityname[CityNum][16]={"哈尔滨","长春","乌鲁木齐","沈阳","呼和浩特","北京","天津","银川","太原","济南","西宁","青岛","兰州","郑州","西安","南京","合肥","上海","成都","武汉","杭州","拉萨","重庆","长沙","贵阳","福州","昆明","广州","南宁"};

//45个城市选择下面的语句
//char cityname[CityNum][16]={"哈尔滨","长春","乌鲁木齐","沈阳","呼和浩特","北京","天津","大连","银川","石家庄","太原","烟台","威海","济南","西宁","青岛","兰州","郑州","连云港","西安","南京","南通","合肥","上海","成都","武汉","杭州","拉萨","宁波","重庆","南昌","长沙","温州","贵阳","福州","桂林","昆明","厦门","广州","南宁","深圳","珠海","北海","湛江","海口"};


void readfile()
{ 
	//此函数已经完成！！！！！！！！！！！！！！！

	int i,j;

	char linebuffer[1024];

	i=0;
	j=0;

	FILE * fin;

	//30个城市选择下面的语句
//	fin = fopen ( "TSP30.txt", "r");

	//29个城市选择下面的语句
	fin = fopen ( "TSP29.txt", "r");

	//45个城市选择下面的语句
//	fin = fopen ( "TSP45.txt", "r");


	if  ( fin == NULL )
	{
		cout << "file open wrong!" << endl;
		return;
	}


	while( !feof(fin )  )
	{
		fscanf (fin, "%s", linebuffer);
		distance[i][j] = atoi (linebuffer);
		if ( i == CityNum-1 && j == CityNum-1 ) 
			break;
		j++;
		if(j>=CityNum)
		{
			i++;
			j=0;
		}			
	}

	//此函数的检验代码

	//for(i=0;i<CityNum;i++)
	//{	for(j=0;j<CityNum;j++)
	//	{
	//		cout<<distance[i][j]<<"  ";
	//	}
	//cout<<endl;
	//}

}


void randomway()
{
	//此函数已经通过！！！！！！！！！！！！！
	int i,m,n,mid;

//	for(i=0;i<CityNum;i++)
//		city[i]=i;

	//在此种下随机种子
	srand((unsigned int)time(NULL));

	for(i=1;i<=CityNum;i++)
	{
	
		m=rand()%CityNum;
		n=rand()%CityNum;


		if(m==n)
			i=i-1;
		else
		{
			mid=city[m];
			city[m]=city[n];
			city[n]=mid;
		}

	}
	//此函数的检验代码
//	for(i=0;i<CityNum;i++)
//	{
//		if(i%10==0)
//			cout<<endl;
//		cout<<city[i]<<"   ";
//	}
//	cout<<endl;

}


int dis()
{
	//此函数通过验证！！！！！！！！！！

	int i,j,num;
	num=0;
	for(i=0;i<CityNum-1;i++)
	{
		j=i+1;
		num=num+distance[city[i]][city[j]];
	}
	num=num+distance[city[CityNum-1]][city[0]];

	return num;
}

//void initoutput()
//{
//	int i;
//	cout<<endl;
//	cout<<"***初始环游路线为：***";
//	for(i=0;i<CityNum;i++)
//	{
//		if(i%8==0)
//			cout<<endl;
//		cout<<cityname[city[i]]<<"<-->";
//	}
//	cout<<cityname[city[0]];
//	cout<<endl;

//}

void lastoutput()
{
	int i;
	cout<<endl;
	cout<<"***优化后的环游路线为：***";
	for(i=0;i<CityNum;i++)
	{
		if(i%8==0)
			cout<<endl;
		cout<<cityname[city[i]]<<"<-->";
	}
	cout<<cityname[city[0]];
	cout<<endl;
}


void initprocess()
{
	int i;

	for(i=0;i<CityNum;i++)
		city[i]=i;
	randomway();
	cost=dis();
//	initoutput();
//	cout<<"***初始环游长度为：***"<<cost;
//	cout<<endl;

}

void optimize()
{
	int count,i,k,j,new_edge,old_edge,a;
	int pcity[CityNum],ls;

L:	for(count=0;count<CityNum;count++)
	{
		for(k=1;k<CityNum-3;k++)
		{
			for(j=k+1;j<CityNum-1;j++)
			{
				if(distance[city[k]][city[j+1]]+distance[city[0]][city[j+1]]<=distance[city[0]][city[j+1]]+distance[city[k]][city[j]])
				{	//正向查入〈tj,tj+1〉边之内					

					//新生成的边之和
					new_edge=distance[city[k]][city[j+1]]+distance[city[0]][city[j]]+distance[city[k+1]][city[CityNum-1]]	;
					//被替代的边之和
					old_edge=distance[city[0]][city[CityNum-1]]+distance[city[k]][city[k+1]]+distance[city[j]][city[j+1]];
					if(new_edge<old_edge)
					{
						//<t1,...tn> <-- <tj+2,...,tn,tk+1,...tj,t0,..,yk,tj+1>	
						for(i=0;i<CityNum;i++)
						{
							pcity[i]=city[i];
						}

						i=0;			
						for(a=j+2;a<CityNum;a++)
						{
							city[i]=pcity[a];
							i++;
						}
						for(a=k+1;a<=j;a++)
						{
							city[i]=pcity[a];
							i++;
						}
						for(a=0;a<=k;a++)
						{
							city[i]=pcity[a];
							i++;
						}
						city[CityNum-1]=pcity[j+1];
//						initoutput();
						cost=cost + new_edge - old_edge;
//						cout<<"则此路径的环游长度为："<<cost<<endl;
						goto L;
					}
				}
				else
				{	//反向查入〈tj,tj+1〉边之内

					new_edge=distance[city[0]][city[j+1]]+distance[city[k]][city[j]]+distance[city[k+1]][city[CityNum-1]]	;
					old_edge=distance[city[0]][city[CityNum-1]]+distance[city[k]][city[k+1]]+distance[city[j]][city[j+1]];
					if(new_edge<old_edge)
					{
						//<t1,..,tn> <-- <tj+2,...,tn,tk+1,...,tj,tk,...,t0,...tj+1>	
						for(i=0;i<CityNum;i++)
						{
							pcity[i]=city[i];
						}

						i=0;			
						for(a=j+2;a<CityNum;a++)
						{
							city[i]=pcity[a];
							i++;
						}
						for(a=k+1;a<=j;a++)
						{
							city[i]=pcity[a];
							i++;
						}
						for(a=k;a>=0;a--)
						{
							city[i]=pcity[a];
							i++;
						}
						city[CityNum-1]=pcity[j+1];

//						initoutput();
						cost=cost + new_edge - old_edge;
//						cout<<"则此路径的环游长度为："<<cost<<endl;
						goto L;
					}
				}
			}
		}
		//<t1,...tn><--<tn,t1,...,tn-1>
		ls=city[CityNum-1];
		for(i=CityNum-2;i>=0;i--)
			city[i+1]=city[i];
		city[0]=ls;


	}
	
}

void lastprocess()
{
	int i;

	FILE *fp;
	fp=fopen("d:\\tspopt.txt","w");
//	fp=fopen("d:\\TSp29.txt","a");
//	fp=fopen("d:\\TSp45.txt","a");

//	char rlt[16];
	fprintf(fp,"NAME:ChinaCity_%d.opt.tour\nCOMMENT:Optimum solution of ChinaCity_%d\nTYPE:TOUR\nDIMENSION:%d\nTime:%f秒\nCost:%d\nTOUR_SECTION:\n",CityNum,CityNum,CityNum,runtime,bestcost);
//	cout<<endl<<"NAME:ChinaCity_"<<CityNum<<".opt.tour"<<endl<<"COMMENT:Optimum solution of ChinaCity_"<<CityNum<<endl<<"TYPE:TOUR"<<endl<<"DIMENSION:"<<CityNum<<endl<<"Time:"<<runtime<<"秒"<<endl<<"Cost:"<<bestcost<<endl<<"TOUR_SECTION:"<<endl<<"*******************************************************************************"<<endl<<"               优化的环游路线为：";

	for(i=0;i<CityNum;i++)
	{
//		if(i%6==0)
//		{
//			fprintf(fp,"\n");
//			cout<<endl;
//		}
//		cout<<cityname[bestway[i]]<<"<-->";
		fprintf(fp,"%d\n",bestway[i]+1);
//		fprintf(fp,"%d%s%s%d%s",bestway[i],cityname[bestway[i]],"<-",distance[bestway[i]][bestway[i+1]],"->");

	}
	fprintf(fp,"-%d\nEOF\n",bestway[0]+1);
//	fprintf(fp,"%d%s%s%d%s%d%s\n环游路径长度：%d\n  ",bestway[CityNum-1],cityname[bestway[CityNum-1]],"<-",distance[bestway[CityNum-1]][bestway[0]],"->",bestway[0],cityname[bestway[0]],bestcost);
	fclose(fp);
	cout<<"程序已经运行完毕，结果请查找文件d:\\tspopt.txt!"<<endl;
//	cout<<cityname[bestway[CityNum-1]]<<"<-->"<<cityname[bestway[0]]<<endl<<"              环游路线的长度为："<<bestcost<<endl<<"*******************************************************************************"<<endl<<"EOF!"<<endl;
	
}


void check()
{
	int i,checknum;
	
	checknum=0;
	
	for(i=0;i<CityNum;i++)
	{
		if(i%5==0)
			cout<<endl;
		cout<<cityname[bestway[i]]<<"<-"<<distance[bestway[i]][bestway[i+1]]<<"->";
	}
	cout<<cityname[bestway[CityNum]]<<endl;

	for(i=0;i<CityNum-1;i++)
	{
		checknum=checknum+distance[bestway[i]][bestway[i+1]];
	}
	checknum=checknum+distance[bestway[CityNum-1]][bestway[0]];

	cout<<"checknum:"<<checknum<<endl;
	cout<<"bestcost:"<<bestcost<<endl;

	if(checknum==bestcost)
		cout<<"^_^ ^_^ ^_^"<<endl;
	else
		cout<<"-_- -_- -_-"<<endl;

}

void main()
{
//	int i;
	int time_star,time_end;
	int j,circlenum;

	bestcost=MaxDistance;

	time_star=timeGetTime();

	readfile();

	for(circlenum=1;circlenum<=CircleNum;circlenum++)
	{
//		cout<<endl;
//		cout<<"                第"<<circlenum<<"次随机选取路径进行优化处理！";
		initprocess();
		optimize();
//		cout<<"                第"<<circlenum<<"次优化处理所得结果为："<<endl;

//		cout<<"***优化后的环游路线为：***";
//		for(i=0;i<CityNum;i++)
//		{
//			if(i%8==0)
//			cout<<endl;
//			cout<<cityname[city[i]]<<"<-->";
//		}
//		cout<<cityname[city[0]];
//		cout<<endl;
//		cout<<"***优化后的环游路线长度为：***"<<cost<<endl;

		if(cost<bestcost)
		{
			bestcost=cost;
			for(j=0;j<CityNum;j++)
				bestway[j]=city[j];
		}
//		getchar();
	}

	time_end=timeGetTime();
	runtime=(float)(time_end-time_star)/1000;
	lastprocess();
//	check();

}