模拟退火算法解决TSP问题-代码

模拟退火算法解决TSP问题一、算法说明：模拟退火算法求解TSP问题的流程框图如图所示二、结果分析蓝色字表示输出结果运行时间表示算法复杂度1)数据集一:模式城市数量为5时输入模式城市数量5为了方便查看，数据和结果保存在文件中邻接矩阵保存在文件模拟退火算法-随机产生数据.txt中访问顺序保存在文件模拟退火算法-结果数据.txt中模拟节点个数5运行时间:10ms邻接矩阵0157208110594936575909082204990075813682750访问节点顺序352412)数据集二:模式城市数量为10时输入模式城市数量10为了方便查看，数据和结果保存在文件中邻接矩阵保存在文件模拟退火算法-随机产生数据.txt中访问顺序保存在文件模拟退火算法-结果数据.txt中模拟节点个数10运行时间:15ms邻接矩阵015720815949369082107518867152312105775037161799451312018370238545861618186162017674636759711738170617980524952995467610318873363145584679310969390213613680889605482101617527393540访问节点顺序176108294533)数据集三:模式城市数量为20时输入模式城市数量20为了方便查看，数据和结果保存在文件中邻接矩阵保存在文件模拟退火算法-随机产生数据.txt中访问顺序保存在文件模拟退火算法-结果数据.txt中模拟节点个数20运行时间:17ms邻接矩阵01572081594936908275188671523121037161017994513123854586161176746367617957170805231887396935415472486227885100100209980062402730843381068729228285969814552620847349217547469575126039746158591331408403716234380529975351866507704918827733705116951591703143897691688362733049165108259201982481651734129579038968421231682069767248133784452674382549337543955969011959255354838853246755854384780152076110289830745720768440186115104652911972952805189499586542086614768959970824892985108463662184131271172477575314813553089840753294293415526786212354316373574463750748471607531462292601885184485799663274026151723678283966977343820582194842608185221078528745069415285766842971158101256376110059617162967328454133460185120216791006958708857434640201215757225620访问节点顺序1912206175181521339101684141117代码：#includeiostream#includectime#includecstdio#includecstdlib#includecmath#includetime.h#includestdlib.h#includestdio.h#includewindows.h#defineMAX10000#defineINF10000000#defineE0.000000001//迭代误差#defineL20000//迭代次数#defineAT0.999//降温系数#defineT1//初始温度usingnamespacestd;structelement{//用来排序的数据结构intdata;//数据intindex;//序号};inttsp(intd[][MAX],intn,doublee,intl,doubleat,doublet,ints0[]);//利用模拟退火算法求解最短路径intcmp(constvoid*a,constvoid*b);//升序排列voidrand_of_n(inta[],intn);//产生1-n的随机排列并存到a[]中intrandom(intm,intn);intdis[MAX][MAX];//d[i][j]表示客户i到客户j的距离，0表示起始点voidrand_of_n(inta[],intn){inti;structelementele[MAX];srand((int)time(0));//初始化随机数种子for(i=0;in;i++){ele[i].data=rand();//随机生成一个数ele[i].index=i+1;}qsort(ele,n,sizeof(ele[0]),cmp);//排序for(i=0;in;i++){a[i]=ele[i].index;}}intrandom(intm,intn){//产生m-n的随机数inta;doublex=(double)rand()/RAND_MAX;a=(int)(x*(n-m)+0.5)+m;returna;}intcmp(constvoid*a,constvoid*b){//升序排序return((structelement*)a)-data-((structelement*)b)-data;}inttsp(intd[][MAX],intn,doublee,intl,doubleat,doublet,ints0[]){inti,j,s[MAX],sum,temp;sum=INF;for(i=0;i1000;i++){//利用蒙特卡洛方法产生初始解rand_of_n(&s[1],n);s[0]=0;s[n+1]=0;//第一个和最后一个点为起始点temp=0;for(j=0;j=n;j++)temp=temp+d[s[j]][s[j+1]];if(tempsum){for(j=0;j=n+1;j++)s0[j]=s[j];sum=temp;}}for(i=0;il;i++){//退火过程intc1,c2;c1=random(1,n);c2=random(1,n);if(c1c2){inttemp=c2;c2=c1;c1=temp;}if(c1==c2)continue;intdf=d[s0[c1-1]][s0[c2]]+d[s0[c1]][s0[c2+1]]-d[s0[c1-1]][s0[c1]]-d[s0[c2]][s0[c2+1]];//计算代价函数if(df0){//接受准则while(c1c2){inttemp=s0[c2];s0[c2]=s0[c1];s0[c1]=temp;c1++;c2--;}sum=sum+df;}elseif(exp(-df/t)((double)rand()/RAND_MAX)){while(c1c2){inttemp=s0[c2];s0[c2]=s0[c1];s0[c1]=temp;c1++;c2--;}sum=sum+df;}t=t*at;if(te)break;}returnsum;}intmain(){DWORDstart,stop;inti,j;intn;cout输入模式城市数量然后输入回车,例如10回车endl;cinn;start=GetTickCount();//程序开始时间for(i=0;in;i++)//随机产生距离1-100for(j=i;jn;j++)if(i==j)dis[i][j]=0;elsedis[i][j]=dis[j][i]=random(1,100);FILE*fp=fopen(模拟退火算法-随机产生数据.txt,w);//将距离存入文件中for(i=0;in;i++){for(j=0;jn;j++)fprintf(fp,%d,dis[i][j]);fprintf(fp,\n);}fclose(fp);intsum,sum0,s0[MAX];sum0=0;//顺序遍历时的路程for(i=0;in;i++)sum0=sum0+dis[i][i+1];sum0=sum0+dis[n][0];sum=tsp(dis,n,E,L,AT,T,s0);fp=fopen(模拟退火算法-结果数据.txt,w);//将结果存入文件中for(i=1;i=n;i++)fprintf(fp,%d,s0[i]);fclose(fp);coutendl;cout为了方便查看，数据和结果保存在文件中endl;cout邻接矩阵保存在文件模拟退火算法-随机产生数据.txt中endl访问顺序保存在文件模拟退火算法-结果数据.txt中endl;coutendl;printf(模拟节点个数%d\n,n);stop=GetTickCount();//程序结束时间printf(运行时间:%lldms\n,stop-start);system(pause);return0;}