1、模拟退火求解 TSP 问题实验报告一、实验要求：旅行商问题（Travelling Salesman Problem, 简记 TSP，亦称货郎担问题)：设有 n 个城市和距离矩阵 D=dij，其中 dij 表示城市 i 到城市 j 的距离，i，j=1，2 n，则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。二、实验思路：1）指标函数：访问所有城市的路径的长度2）新解的产生: 选择两个城市间的位置交换方式得到一个可能解的邻域，在随机选择一个解3）新解的接受准则：exp(-(fj-fi)/t)4）初始温度的确定：产生一组解，使其平均接受概率为0.95）内循环次数：n6）温度的衰减系
2、数：0.957）算法的停止准则：温度低于.01 获没有新解产生三、实验代码：/*指标函数：访问所有城市的路径的长度新解的产生: 选择两个城市间的位置交换方式得到一个可能解的邻域，在随机选择一个解新解的接受准则：exp(-(fj-fi)/t)初始温度的确定：产生一组解，使其平均接受概率为.9内循环次数：n温度的衰减系数：.95算法的停止准则：温度低于.01获没有新解产生*/#include#include#include#includeconst long MAX=100;struct Citydouble x,y; cityMAX;/函数：读入数据-返回城市数目long initial()lo
3、ng i,n;/读入城市的数目、坐标、坐标scanf(“%d“,for(i=0;i=0.9)break;t*=1.05;return t;/函数：生成一个序列作为解void generate_path(long *path,long n)long i,cnt,temp;long markMAX;for(i=0;ifj)for(t=0;tdouble(rand()%1000)/1000) /ok?for(t=0;tnum;t+)patht=neighbourtemp.patht;fi=fj;flag=true;/降温temperature*=0.95;if(first=false)for(t=0
4、;tnum;t+)if(recordt!=patht)break;if(t=numif(temperature0.01) break;first=false;/输出printf(“nNo.%d :n“,h+1);/printf(“ The answer is “);for(t=0;tnum;t+)printf(“%d “,patht);printf(“n%lfn“,cal_f(path,num);printf(“%lfn“,temperature);finish=clock();printf(“%8.5lf snn“,(double)(finish-start)/CLOCKS_PER_SEC);system(“pause“);system(“pause“);return 0;四、实验结果：
