// monituihuo.cpp : 定義控制臺應用程序的入口點。 // #include "stdafx.h"#include <stdio.h> #include <stdlib.h> #include <math.h> #include <time.h> #include <iostream> #include <fstream> #include <Windows.h> using namespace std;const int MAXN = 27; //城市數量 const double MAX = 27.0; //城市數量 const double INIT_T = 3000; //初始溫度 const double RATE = 0.95; //溫度衰減率 const double FINNAL_T = 1E-10; //終止溫度 const int IN_LOOP = 15000; //內循環次數 const int LIMIT = 10000; //概率選擇上限 const int FINL_LOOP = 1000; //外層循環 double DD=0; double D_Length[MAXN][MAXN]={0};struct path {//定義路線結構int citys[MAXN];double length; }D_BestPath;struct point {//定義點結構double x;double y; }D_Point[MAXN];//計算點和點之間的距離 void point_dist() {int i, j;double x;for(i=0; i<MAXN; i++){for(j=i+1; j<MAXN; j++){x = (D_Point[i].x-D_Point[j].x)*(D_Point[i].x-D_Point[j].x);x += (D_Point[i].y-D_Point[j].y)*(D_Point[i].y-D_Point[j].y);D_Length[i][j] = sqrt(x);D_Length[j][i] = D_Length[i][j];} } } //初始化 void init() {int i;printf("初始狀態路徑：");D_BestPath.length = 0;for(i=0; i<MAXN; i++){//初始順序經過路徑D_BestPath.citys[i] = i;printf("%d--", i);}for(i=0; i<MAXN-1; i++){//計算路徑長度D_BestPath.length += D_Length[i][i+1];}printf("\n路徑長度為：%.3lf\n\n", D_BestPath.length);} void Dprintf(path p) {//用于顯示過程變化情況，打印int i;printf("路徑是：");for(i=0; i<MAXN; i++){printf("%d--", p.citys[i]);}printf("\n路徑長度為：%.3lf\n\n", p.length); }//輸入城市坐標信息 void input() {int i,ll = 1;ifstream f1("C:\\city.txt",ios::in);for(i=0; i<MAXN; i++){if(ll % 2 != 0)f1 >> D_Point[i].x;if(ll % 2 == 0)f1 >> D_Point[i].y;ll++;}f1.close(); }path getnext(path p) {path ret;int i, x, y;int te;ret = p;do{x = (int)(MAX*rand()/(RAND_MAX + 1.0));y = (int)(MAX*rand()/(RAND_MAX + 1.0));}while(x == y);te = ret.citys[x];ret.citys[x] = ret.citys[y];ret.citys[y] = te;ret.length = 0;for(i=0; i<MAXN-1; i++){//計算路徑長度ret.length += D_Length[ret.citys[i]][ret.citys[i+1]];}Dprintf(ret);DD++;return ret; }void sa() {int i, P_L=0, P_F=0;;path curPath, newPath;double T = INIT_T;double p, delta;srand((int)time(0));curPath = D_BestPath;while(true){for(i=0; i<IN_LOOP; i++){newPath = getnext(curPath);delta = newPath.length - curPath.length;if(delta < 0){//更新長度curPath = newPath;P_L = 0;P_F = 0;}else{p = (double)(1.0*rand()/(RAND_MAX+1.0));if(exp(delta/T) < 1 && exp(delta/T) > p){curPath = newPath;}P_L ++;}if(P_L > LIMIT){P_F ++;break;}}if(curPath.length < newPath.length){D_BestPath = curPath;}if(P_F > FINL_LOOP || T<FINNAL_T)break;T = T * RATE;}}void main() {input();point_dist();init();sa();Dprintf(D_BestPath);printf("\n共測試%.0lf次\n", DD);system("pause"); }

參考：http://blog.csdn.net/oxoxzhu/article/details/8142306

轉載于:https://www.cnblogs.com/Key-Ky/p/3452511.html

總結

以上是生活随笔為你收集整理的模拟退火解决TSP问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。