模拟退火求解tsp问题实验报告

《模拟退火求解tsp问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、模拟退火求解TSP问题实验报告一、实验要求：旅行商问题（TravellingSalesmanProblem,简记TSP，亦称货郎担问题)：设有n个城市和距离矩阵D=[dij]，其中dij表示城市i到城市j的距离，i，j=1，2…n，则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。二、实验思路：1）指标函数：访问所有城市的路径的长度2）新解的产生:选择两个城市间的位置交换方式得到一个可能解的邻域，在随机选择一个解3）新解的接受准则：exp(-(fj-fi)/t)4）初始温度的确定：产生一组解，使其平均接受概率为0.95）内循环次数：n6）温度的衰减系数：0.957）算法的停止

2、准则：温度低于.01获没有新解产生三、实验代码：/*指标函数：访问所有城市的路径的长度新解的产生:选择两个城市间的位置交换方式得到一个可能解的邻域，在随机选择一个解新解的接受准则：exp(-(fj-fi)/t)初始温度的确定：产生一组解，使其平均接受概率为.9内循环次数：n温度的衰减系数：.95算法的停止准则：温度低于.01获没有新解产生*/#include#include#include#includeconstlongMAX=100;structCity{doublex,y;}city[MAX];//函数：读入数据--

3、返回城市数目longinitial(){longi,n;//读入城市的数目、ｘ坐标、ｙ坐标scanf("%d",&n);for(i=0;i

4、ty[path[i]].y-city[pre].y)*(city[path[i]].y-city[pre].y));pre=path[i];}len+=sqrt((city[path[0]].x-city[pre].x)*(city[path[0]].x-city[pre].x)+(city[path[0]].y-city[pre].y)*(city[path[0]].y-city[pre].y));returnlen;}voidgenerate_path(long*path,longn);//函数：计算初始温度doublecal_temperature(longnum){longj,n;d

5、oublet,sum,fi,fj;longpath[MAX];t=1.0;n=20*num;while(1){sum=0.0;generate_path(path,num);fi=cal_f(path,num);for(j=0;j=0.9)break;t*=1.05;};returnt;}//函数：生成一个序列作为解voidgenerate_path(long*path,longn){longi,cnt,temp;lo

6、ngmark[MAX];for(i=0;i

7、r[500];//ok????boolflag,first;longi,j,k,t,temp;longnum,pt,cnt_flag;doublep;doublefi,fj,temperature;longpath[MAX],record[MAX];//输入部分：读入数据（表示城市间的距离）num=initial();fclose(stdin);srand(time(NULL));//freopen("res