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.运行结果
