模擬退火求解tsp問題實驗報告

《模擬退火求解tsp問題實驗報告》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在工程資料-天天文庫。

1、模擬退火求解TSP問題實驗報告一、實驗要求：旅行商問題（TravellingSalesmanProblem,簡記TSP，亦稱貨郎擔問題)：設有n個城市和距離矩陣D=[dij]，其中dij表示城市i到城市j的距離，i，j=1，2…n，則問題是要找出遍訪每個城市恰好一次的一條回路并使其路徑長度為最短。二、實驗思路：1）指標函數(shù)：訪問所有城市的路徑的長度2）新解的產(chǎn)生:選擇兩個城市間的位置交換方式得到一個可能解的鄰域，在隨機選擇一個解3）新解的接受準則：exp(-(fj-fi)/t)4）初始溫度的確定：產(chǎn)生一組解，使其平均接受概率為0.95）內(nèi)循環(huán)次數(shù)：n6）溫度的衰減系數(shù)：0.957）算法的停止

2、準則：溫度低于.01獲沒有新解產(chǎn)生三、實驗代碼：/*指標函數(shù)：訪問所有城市的路徑的長度新解的產(chǎn)生:選擇兩個城市間的位置交換方式得到一個可能解的鄰域，在隨機選擇一個解新解的接受準則：exp(-(fj-fi)/t)初始溫度的確定：產(chǎn)生一組解，使其平均接受概率為.9內(nèi)循環(huán)次數(shù)：n溫度的衰減系數(shù)：.95算法的停止準則：溫度低于.01獲沒有新解產(chǎn)生*/#include#include#include#includeconstlongMAX=100;structCity{doublex,y;}city[MAX];//函數(shù)：讀入數(shù)據(jù)--

3、返回城市數(shù)目longinitial(){longi,n;//讀入城市的數(shù)目、ｘ坐標、ｙ坐標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);//函數(shù)：計算初始溫度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;}//函數(shù)：生成一個序列作為解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];//輸入部分：讀入數(shù)據(jù)（表示城市間的距離）num=initial();fclose(stdin);srand(time(NULL));//freopen("res