1.預備知識
a.數組傳遞
數組的使用，詳細知識點：
http://www.cnblogs.com/kykuaileren/archive/2011/09/04/2166646.html C++數組操作，定義和初始化，傳遞
http://www.2cto.com/kf/201307/231024.html C++一維數組和指針的關系
http://blog.csdn.net/zhangyulin54321/article/details/7843531 徹底搞清C++數組與指針
總結：
//一維數組定義
int *a1=new int[n];
//一維數組初始化
for(int i=0;i<n;i++)
a1[i]=i+1;
//一維數組傳遞
void Function(int *a1){}
//一維數組取值
*(a1+i);
//二維數組定義
int **a2=(int **)new int *[n];
for(i=0;i<n;i++)
a2[i]=(int *)new int[n];
//二維數組初始化
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>*(a2[i]+j);
//二維數組傳遞
int* Function(int **arr){
...
return arr;
}
//二維數組取值
*(a2[i]+j);
b.随機函數rand的使用
所需頭檔案：
#include<stdlib.h>#include<stdio.h>#include<time.h>#include<cmath>
求[0,n]之間的随機數：rand()%(n+1);
求（0,1）之間的随機數：(double)(rand()/(double)RAND_MAX); //RAND_MAX是C中stdlib.h中宏定義的一個字元常量:
c.旅行商問題
這篇文章對模拟退火算法的講解很詳細也很透徹：http://blog.csdn.net/lalor/article/details/7688329
旅行商問題（ Travelling Salesman Problem, 簡記TSP，亦稱貨郎擔問題)：設有n個城市和距離矩陣D=[dij]，其中dij表示城市i到城市j的距離， i， j=1， 2 … n，則問題是要找出遍訪每個城市恰好一次的一條回路并使其路徑長度為最短。
對TSP的分析：TSP的一個解可表述為一個循環排列π= (π1， π2， π3 … πn），即π1 → π2 → … → πn → π1有（ n-1）！ /2 種不同方案，若使用窮舉法，當n很大時計算量是不可接受的。旅行商問題綜合了一大類組合優化問題的典型特征，屬于NP難題，不能在多項式時間内進行檢驗。若使用動态規劃的方法時間複雜性和空間複雜性都保持為n的指數函數。
TSP中參數選取的一個例子：
控制參數初值 t0=100 停止準則：連續2個Mapkob鍊中對路徑無任何變動（優化或惡化的）時即停止算法運作。 冷卻進度表中的控制參數t的衰減函數：α(t)=0.9 *t Mapkob鍊長：定長20000 新解的産生：采用2變換法。任選序号u和v (u<v)，将u和v及其之間的順序逆轉。 (π1 … πu-1πuπu+1 … πv-1πvπv+1 … πn)變為
（π1 … πu-1πvπv-1 … πu-1πuπv+1 … πn）
用模拟退火算法解TSP僞代碼：
Procedure TSP_USE_SIMULATED_ANNEALING;
begin
INITIALIZE; { 初始化i0= π1 … πn, t0=100, L= 20000 }
randomize; { 初始化随機數種子 }
Repeat
bChange:=0;
for l:=1 to L do
begin
GENERATE; { 采用2變換法産生新的路徑 }
CALCULATE(df); { 計算 df = f(j)-f(i) 的值 }
if ACCEPT(t, df) then { 根據Metropolis準則判斷是否接受新的路徑 }
begin
f: = f + df; { 計算已接受的路徑的長度 }
bChange := 1;
end;
end;
t:=t * 0.9; { 衰減函數 α(t)=0.9 * t }
if (bChange = 0) then s:=s+1 else s:=0;
until s = 2 { 停止準則為連續兩個Mapkob鍊路徑無變化 }
End;
2.模拟退火算法解TSP問題源代碼（代碼最好自己動手）
#include<iostream>
#include<stdlib.h>
#include<stdio.h> //随機函數所需頭檔案
#include<cmath>
using namespace std;
const int T=0.9; //降溫速率
int t=100; //初始溫度
const int L=20000;
//轉置函數
void Reverse(int *node,int i,int j){
int temp=0;
while(i<j){
temp=*(node+i);
*(node+i)=*(node+j);
*(node+j)=temp;
i++;
j--;
}
}
//計算路徑長度函數
int Length(int **arr,int *node,int n){
int p=0; //路徑結點從1開始
int i=0,j=0; //兩結點間的路徑在二維數組裡的位置
int s=0; //周遊節點
int length=0; //路徑長度
for(s=0;s<n-1;s++){
i=*(node+s)-1;
j=*(node+s+1)-1;
length += *(arr[i]+j);
}
i=*(node+n-1)-1;
j=*(node)-1;
length += *(arr[i]+j);
return length;
}
int* TSP(int **arr,int* node,int n){
int *minRoad=new int[n]; //最短路徑
int *road=new int[n]; //普通路徑
int i=0,j=0,temp=0;
int s=0,bChange=0; //儲存路徑變化數
int p=0,q=0; //儲存随機數
int d=0; //路徑長短比較
double m;//儲存e的指數
double l;//儲存随機浮點數
for(i=0;i<n;i++) //儲存最短路徑
*(minRoad+i)=*(node+i);
for(i=0;i<n;i++) //初始化普通路徑
*(road+i)=*(node+i);
do{
bChange=0;
for(j=1;j<L;j++){
//1.采用2變換法産生新的路徑
p=rand()%n,q=rand()%n; //産生随機數
while(p==q)
q=rand()%n;
if(p>q){
temp=p;
p=q;
q=temp;
}
Reverse(road,p,q);
//2.路徑長短比較
d=Length(arr,road,n)-Length(arr,minRoad,n);
//3.判斷是否接受新路徑
if(d<0){
for(i=0;i<n;i++) //儲存最短路徑
*(minRoad+i)=*(road+i);
bChange=1;
}
else{
m=(double)(-d)/t;
l=(double)(rand()/(double)RAND_MAX);
if(exp(m)>l){
for(i=0;i<n;i++) //儲存最短路徑
*(minRoad+i)=*(road+i);
bChange=1;
}
}
}
t=t*T;
if(bChange==0)
s += 1;
else s=0;
}while(s!=2);
return minRoad;
}
int main(){
int n=0;
int i=0,j=0;
int *res;
cout<<"Please enter the number of the cities:";
cin>>n;
//一維數組定義
int *a1=new int[n];
for(int i=0;i<n;i++)
a1[i]=i+1;
//二維數組定義
int **a2=(int **)new int *[n];
for(i=0;i<n;i++)
a2[i]=(int *)new int[n];
cout<<"Please enter the distance of cities:"<<endl;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>*(a2[i]+j);
cout<<endl;
cout<<"the distance of cities:"<<endl;
for(i=0;i<n;i++)
cout<<a1[i]<<" ";
cout<<endl;
for(i=0;i<n;i++){
for(j=0;j<n;j++)
cout<<*(a2[i]+j)<<" ";
cout<<endl;
}
cout<<endl;
cout<<"the shortest path:";
res=TSP(a2,a1,n);
for(i=0;i<n;i++)
cout<<*(res+i)<<"->";
cout<<*(res);
cout<<endl;
cout<<"the distance of the shortest path:"<<Length(a2,res,n)<<endl;
/*
for(i=0;i<n;i++)
cout<<a1[i]<<" ";
cout<<endl;
Reverse(a1,1,2);
for(i=0;i<n;i++)
cout<<a1[i]<<" ";
cout<<endl;
for(i=0;i<n;i++){
for(j=0;j<n;j++)
cout<<*(a2[i]+j)<<" ";
cout<<endl;
}
int l=Length(a2,a1,n);
cout<<endl;
cout<<l;
cout<<endl;
i=rand()%5;
cout<<i;
cout<<endl;
i= abs(2-3);
cout<<i;
cout<<endl;
*/
return 0;
}
3.運作結果
