tsp_sa.cpp

该程序是模拟退火算法应用中旅行商问题的c++程序

/*
   CopyRight by 黄丽福 @2009/4/18 23020081153237 [e-mail]
*/
#include<vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include "memory.h"
#include "CStdlib"
#include "CStdio"
#include "math.h"
#include "Ctime"
using namespace std;
double MatrixForUse[60][60];//城市距离矩阵
typedef struct _XYCoordinate{//城市的位置信息
	int px;
	int py;
	_XYCoordinate(){
		px=py=0;
	}
}XYCoordinate;
typedef struct _City//城市信息结构体
{
	_City()
	{
		index = 0;
	}
	int index;				//城市编号
 	XYCoordinate pxy;		//城市坐标
}City;
typedef struct _City2Distance//求得两个城市之间的距离
{
	_City2Distance()
	{
		FromIdx = 0;
		ToIdx = 0;
		Distance = 0.0;
	}
	double getDistance(int f,int t,vector<City>  &citys){
		setFromTO(f,t);
		setDistance(citys);
		return Distance;
	}
	void setFromTO(int f,int t){
		FromIdx=f;
		ToIdx=t;
	}
	void setDistance(vector<City>  &citys){//求得两个城市的距离
		City fromCity=citys[FromIdx];
		City toCity=citys[ToIdx];
		double x=fromCity.pxy.px-toCity.pxy.px;
		double y=fromCity.pxy.py-toCity.pxy.py;
		x=x*x;
		y=y*y;
		Distance=sqrt(x+y);  		
	}
	int FromIdx;				//源城市
	int ToIdx;					//目标城市
	double Distance;			//城市之间的距离
}City2Distance;

vector<City> citys;//城市的集合
typedef struct _CityRouterCal {//求解tsp_SA用到的数据结构
    int RouterTrace[60];
    double Temp;
    double TotalLength;
	_CityRouterCal(){
         Temp=TotalLength=0;
	}

   _CityRouterCal(double T){
       initRouterTrace();
       Temp=T;
	   TotalLength=CalTotalLength();
   }

   _CityRouterCal(int NewRouter[60] ,double T){
	  memcpy(RouterTrace,NewRouter,sizeof(int)*citys.size());
       K_2_Change();
       TotalLength=CalTotalLength();
   }
   void print(){//打印路径
    	int in=0;
    	while (in<citys.size()) {
		  printf("%d ",RouterTrace[in]);
		  in++;
		}
	printf("\n");
   }
   void K_2_Change(){//k＝2变换
	 int swapA, swapB;
     int N=citys.size();
//	 srand( (unsigned)time( NULL ) );
	 while(1)
	 {
		 swapA = (rand()%N);
		 if( swapA >= 0 )
			 	break;
	 }
	 while(1)
	 {
    	swapB = (rand()%N);
		 if( swapA != swapB && swapB >= 0 )
		 {
			 	break;
		 }
	 }
 		int min=swapA<swapB?swapA:swapB;			
	 	int max=swapA>swapB?swapA:swapB;			
 		int Len=(max-min)/2;
 	  	for(int  i=0;i<Len;i++){
			  int tmp=RouterTrace[min+i];
	 		  RouterTrace[min+i]=RouterTrace[max-i];
	 		  RouterTrace[max-i]=tmp;
		}
								
}
 
   
 double CalTotalLength(){
    int i,N=citys.size()-1;
    double totoal=0.0;
 	for(i=0;i<N;i++){
	   totoal+=MatrixForUse[RouterTrace[i]][RouterTrace[i+1]];
	}
	totoal+=MatrixForUse[RouterTrace[0]][RouterTrace[N]];
	return totoal;
}
 

void initRouterTrace(){//初始的一个解
   for(int i=0;i<citys.size();i++)
	  RouterTrace[i]=i;
}
 

void operator=(const struct _CityRouterCal& srcRouter)//赋值运算
{
    memcpy(RouterTrace,srcRouter.RouterTrace,sizeof(int)*citys.size());
 	TotalLength = srcRouter.TotalLength;
}
}CityRouterCal;

 
 void readFileData(char  filename[]){//导入文件数据
  FILE *fp; 
  fp=fopen(filename,"r+");
  if (fp==NULL) {
	  printf("open %s file error\n",filename);
	  exit(0);
  }
  int index;
  int x,y;
  memset(MatrixForUse,0.0,sizeof(double)*60*60);
  while(fscanf(fp,"%d %d %d",&index,&x,&y)==3){
 	   City temCity;
	   temCity.index=index-1;
	   temCity.pxy.px=x;
	   temCity.pxy.py=y;
	   citys.push_back(temCity);
  }
 }

//获得城市间的最大最小距离
void getAndInitMatrix(double &maxDistance,double &minDistance){
	int i,j;
	maxDistance=0.0;
    minDistance=1000000000.0;
	City2Distance c2d;
	for(i=0;i<citys.size();i++){
		for(j=0;j<citys.size();j++){
			MatrixForUse[i][j]=c2d.getDistance(i,j,citys);
			if (MatrixForUse[i][j]!=0&&maxDistance<MatrixForUse[i][j]) {
				maxDistance=MatrixForUse[i][j];
			}
			if (MatrixForUse[i][j]!=0&&minDistance>MatrixForUse[i][j]) {
				minDistance=MatrixForUse[i][j];
			}
		}
	} 
}
//内层循环判断
int JudgeOverInnerLoop(int NowInnerIterNumber,int N)
{
	if( NowInnerIterNumber >= N) 
		return 1;
	else
		return 0;
}
//外层循环判断
int JudgeOverExternalLoop( int NowTemperature,double Temp )
{
	if( Temp <= 0.01 )
		return 1;
	else
		return 0;
}
//测试用到的温度下降比例因子,个数，索引
double TperDown[12]={
	0.95,0.90,0.85,0.80,0.75,0.70,0.65,0.60,0.55,0.50,0.45
};
int Tmax=11;
int Tindex=0;
//SA的实现TSP
void Tsp_SA(){
   double maxDistance,minDistance;
   getAndInitMatrix(maxDistance,minDistance);
   srand( (unsigned)time( NULL ) );
   int rate = 20;//初始温度
   double T=100;//rate*(citys.size()*(maxDistance - minDistance));

   CityRouterCal  ResultRouter(T);
   printf("初始温度为:%f\n温度降温的幅度：%f\n路径的长度: %f\n路径如下 :\n",T,TperDown[Tindex],ResultRouter.TotalLength);
   ResultRouter.print();
   int NNiner=20000;//citys.size()*citys.size()*citys.size();
   int NowInnerIterNumber=0;
   int NowExternalIterNumber=0;
   double recordBest=10000000;
   int bestPathRec[60];
    printf("开始计算:\n"); 
	while (1) {
     //  printf("\n新的内循环开始:\n");	   
		 printf(".");
	   while (1) {
	      CityRouterCal  CurRouter(ResultRouter.RouterTrace,T);
          double diffTotal=CurRouter.TotalLength-ResultRouter.TotalLength;
         if (diffTotal<0.0) {
			 ResultRouter=CurRouter;
			 if (recordBest>ResultRouter.TotalLength) {
				 recordBest=ResultRouter.TotalLength;
				 memcpy(bestPathRec,ResultRouter.RouterTrace,sizeof(int)*citys.size());
			 }
         }	else
		 {
			 
 			 double chgprobability = exp( -(diffTotal/T) );
 			 double random = ((double)( rand()%100000))*0.00001;
 			 if(chgprobability > random )
			 {	  
			    ResultRouter=CurRouter;
			 } 			 			 			 		 
		 }
		 if (JudgeOverInnerLoop(NowInnerIterNumber,NNiner)) {
	     	break;
		 }else NowInnerIterNumber++;	
	   }	
	  
	   if (JudgeOverExternalLoop(NowInnerIterNumber,T)) {
		   break;
	   }else{
		   NowInnerIterNumber=0;
		   NowExternalIterNumber++;	
		   T*=TperDown[Tindex];
		   //printf("当前温度为:%f\n路径的长度: %f\n路径如下 :\n",T,ResultRouter.TotalLength);
		   //ResultRouter.print();
	   }

	    
   }
	printf("\n计算结束：\n路径的长度: %f\n路径如下 :\n",ResultRouter.TotalLength);
	ResultRouter.print();
	printf("记录最好的路径的长度 %f\n路径如下 :\n",recordBest);
	for(int i=0;i<citys.size();i++)
		printf("%d ",bestPathRec[i]);
	printf("\n");
}

 void main(){
	char filename[10]="48.txt";
	readFileData(filename);
    while (Tindex<=Tmax) {
         Tsp_SA();
	printf("\n\n");
		 Tindex++;
		// break;
    }
	
}