TSP--模拟退火算法（c++實作+詳細解釋）

利用模拟退火算法解決TSP問題，能看到這篇文章的應該知道TSP是什麼，在此就不贅述了，模拟退火算法思想網絡上優質結束很多，是以直接講講如何用C++實作它

算法步驟

1.初始化：起始溫度，終止溫度，溫度變化率，最優路徑頂點集 ，最短長度S

2.利用蒙特卡洛法得到一個比較好的初始解

3.目前溫度大于終止溫度時，利用兩點交換法在目前最優路徑基礎上構造一條新路徑，計算新路徑的長度S1，內插補點dE= S1 - S

4.若 dE < 0，目前最優路徑更新為新路徑，最短長度更新為S1

否則，任意産生一個介于0~1的機率rt,并計算exp(-dE/T),T為目前溫度；若exp(-dE/T) > rt, 目前最優路徑更新為新路徑，最短長度更新為S1，更新溫度

C++代碼（内附詳細注釋）

#include<iostream>
using namespace std;
#include<cstdlib>
#include<ctime>
#include<vector>
#include<cmath>

//思路：
//1.初始化：起始溫度，終止溫度，溫度變化率，最優路徑頂點集 ，最短長度S 
//2.利用蒙特卡洛法得到一個比較好的初始解
//3.目前溫度大于終止溫度時，利用兩點交換法在目前最優路徑基礎上構造一條新路徑，計算新路徑的長度S1，內插補點dE= S1 - S 
//4.若 dE < 0，目前最優路徑更新為新路徑，最短長度更新為S1
//否則，任意産生一個介于0~1的機率rt,并計算exp(-dE/T),T為目前溫度；若exp(-dE/T) > rt, 目前最優路徑更新為新路徑，最短長度更新為S1
//更新溫度 
void TSP(vector<vector<int> > W)
{
	int n = W.size();//頂點數量
	
	//----------------------初始化參數------------------- 
	 
	int startT = 3000;//初始溫度
	
	double endT = 1e-8;//結束溫度;科學計數法不需要頭檔案，字元間不允許有空格 
	
	double delta = 0.999;//溫度變化率
	
	int limit =  10000;//機率選擇上限,表示已經接近最優解 
	 
	//vector<vector<int> > w = W;
	
	vector<int> path;//最優路徑（頂點集）
	
	int length_sum = 0;//最優路徑長度和 
	
	//初始化最優路徑 
	for(int i = 0; i < n; i++)
	{
		path.push_back(i);//必須使用入棧	
	} 
	//swap(path[3],path[1]);//修改可用重載 [] 
	
	
	
	//計算初始最優路徑和 
	for(int i = 0; i < n - 1; i++)
	{
//		cout<<path[i]<<" ";
		
		length_sum += W[path[i]][path[i + 1]];
	}
	
	length_sum += W[path[n - 1]][path[0]];
	
//----------------使用蒙特卡洛得到一個較好的初始解---------------------- 
	vector<int> cur = path;
	
	int cur_sum = 0;
	
	for(int i = 0; i < 8000; i++)
	{
		for(int k = 0; k < n; k++)
		{
			int j = rand() % n;
			
			swap(cur[k],cur[j]);
		}
		//計算初始最優路徑和 
		for(int i = 0; i < n - 1; i++)
		{
			cur_sum += W[cur[i]][cur[i + 1]];
		}
		
		cur_sum += W[cur[n - 1]][cur[0]];
		
		if(cur_sum < length_sum)
		{
			path = cur;
			
			length_sum = cur_sum;
			
		}
		
	}
//	cout<<endl<<length_sum<<endl;
	
	
	//-------------------模拟退火具體過程--------------------------------	
	
	//1.若是沒有此函數，每次執行該代碼産生結果都相同，預設1是種子 
	//2.有此函數，若是放在循環内部，則每次循環都設定同一個種子 
	srand((int)(time(NULL)));//确定一個随機種子
	
	//退火模拟過程 
	while(startT > endT)//控制循環次數 
	{
	//	cout<<endl<<count++<<endl;
	
//----------------構造新路徑----------------------------------------
	 
		vector<int> path_new = path;//為構造一條新路徑準備
		
		int length_sum_new = 0;//新的路徑總和
		
		int P_L = 0;//以一定機率接受次數 
		
		//随機産生兩個點，交換，得到一條新的路徑 
		int x = rand() % n;
		
		int y = rand() % n;
		
		while(x == y)//直到随機産生兩個互異頂點才繼續向下執行 
		{
			x = rand() % n;
		
			y = rand() % n;
			
		} 
		
	//	cout<<" x:"<<x<<"  y: "<<y<<endl; 
		
		swap(path_new[x], path_new[y]);//等價于在原最優路徑上随機交換兩個互異頂點得到新路徑
		
		//計算新路徑和 
		for(int i = 0; i < n - 1; i++)
		{
	//		cout<<path_new[i]<<" ";
			
			length_sum_new += W[path_new[i]][path_new[i + 1]];
		}
		
		length_sum_new += W[path_new[n - 1]][path_new[0]];
		
	//	cout<<endl<<length_sum_new<<endl;
	
	
	
	//--------------------------比較新舊路徑，取優-------------------------- 
		double dE = length_sum_new - length_sum;
		
		
		if(dE < 0)//新路徑更短，直接取用 
		{
			path = path_new;
			
			length_sum = length_sum_new;
		}
		else //新路徑不會更優，按一定機率接受 
		{
			double rd = rand() / (RAND_MAX + 1.0);//随機産生機率：0~1
			
			if(exp(- dE / startT) > rd )
			{
				path  = path_new;
				
				length_sum = length_sum_new;
				
				P_L++; //一定機率接受次數 
			} 
		}
		
		if(P_L == limit)break;//達到限制，直接退出 
		
		startT *= delta;//溫度變化，降低 
	} 
		
//--------------------輸出---------------------------------- 
	
	cout<<endl<<endl<<"--------說明：鄰接矩陣頂點從 0 開始存儲，而輸出時頂點從 1 開始--------"<<endl<<endl;
	
	for(int i = 0; i < n - 1; i++)
	{
		cout<<"目前點序号為： "<<path[i]+1<<"   下個點序号為： "<<path[i + 1]+1<<"    權值為： "<<W[path[i]][path[i+1]]<<endl; 
	}
	cout<<"目前點序号為： "<<path[n -1]+1<<"   下個點序号為： "<<path[0]+1<< "    權值為： "<<W[path[n - 1]][path[0]]<<endl;
	cout<<endl<<"最優解："<<length_sum<<endl;
}

int main()
{
	int n;
	vector<vector<int> > w;
	vector<int> v;
	cout<<"please input the number of vertex n:"<<endl;
	cin>>n; 
	
	//輸入方法，先分解為一維向量 
	for(int i=0;i<n;i++)
	{
		w.push_back(v);
	}
	int temp;

	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>temp;
		
			w[j].push_back(temp);
		}
	}
	
	TSP(w);	
	return 0;
	
 }