模拟退火算法解决TSP问题-代码7页

1、 模拟退火算法解决TSP问题1、 算法说明：模拟退火算法求解TSP问题的流程框图如图所示二、结果分析 蓝色字表示 输出结果 运行时间表示 算法复杂度1)数据集一:模式城市数量为5时输入模式城市数量5为了方便查看，数据和结果保存在文件中<<<<邻接矩阵保存在文件 模拟退火算法-随机产生数据.txt 中<<<<访问顺序保存在文件 模拟退火算法-结果数据.txt 中模拟节点个数 5运行时间: 10 ms邻接矩阵0 1 57 20 81 1 0 59 49 36 57 59 0 90 82 20 49 90 0 75 81 36 82 75 0 访问节点

2、顺序3 5 2 4 1 2)数据集二:模式城市数量为10时输入模式城市数量10为了方便查看，数据和结果保存在文件中<<<<邻接矩阵保存在文件 模拟退火算法-随机产生数据.txt 中<<<<访问顺序保存在文件 模拟退火算法-结果数据.txt 中模拟节点个数 10运行时间: 15 ms邻接矩阵0 1 57 20 81 59 49 36 90 82 1 0 75 18 86 71 52 31 2 10 57 75 0 37 16 17 99 45 13 1 20 18 37 0 2 38 54 58 61 61 81 86 16 2 0 17 67 4

3、6 36 7 59 71 17 38 17 0 61 79 80 52 49 52 99 54 67 61 0 31 88 73 36 31 45 58 46 79 31 0 96 93 90 2 13 61 36 80 88 96 0 54 82 10 1 61 7 52 73 93 54 0 访问节点顺序1 7 6 10 8 2 9 4 5 3 3)数据集三:模式城市数量为20时输入模式城市数量20为了方便查看，数据和结果保存在文件中<<<<邻接矩阵保存在文件 模拟退火算法-随机产生数据.txt 中<<<<访问顺序保存在文件 模拟退火算法-结

4、果数据.txt 中模拟节点个数 20运行时间: 17ms邻接矩阵0 1 57 20 81 59 49 36 90 82 75 18 86 71 52 31 2 10 37 16 1 0 17 99 45 13 1 2 38 54 58 61 61 17 67 46 36 7 61 79 57 17 0 80 52 31 88 73 96 93 54 15 47 24 86 22 78 85 100 100 20 99 80 0 62 40 27 30 84 3 38 10 68 7 2 92 28 28 59 69 81 45 52 62 0 84 73 49 21 75 47 46 95 7

5、5 12 60 39 74 61 58 59 13 31 40 84 0 37 16 23 43 80 52 99 75 35 18 66 50 7 70 49 1 88 27 73 37 0 51 16 95 15 91 70 31 43 8 97 69 16 88 36 2 73 30 49 16 51 0 82 59 20 19 82 48 16 51 73 41 29 57 90 38 96 84 21 23 16 82 0 69 76 72 48 13 37 84 4 52 67 43 82 54 93 3 75 43 95 59 69 0 11 95 92 55 35 48 38

6、85 32 46 75 58 54 38 47 80 15 20 76 11 0 28 98 30 74 57 20 76 84 40 18 61 15 10 46 52 91 19 72 95 28 0 51 89 4 99 58 6 54 20 86 61 47 68 95 99 70 82 48 92 98 51 0 84 63 66 21 84 13 12 71 17 24 7 75 75 31 48 13 55 30 89 84 0 75 32 94 29 34 15 52 67 86 2 12 35 43 16 37 35 74 4 63 75 0 74 84 71 60 75 3

7、1 46 22 92 60 18 8 51 84 48 57 99 66 32 74 0 26 15 1 7 2 36 78 28 39 66 97 73 4 38 20 58 21 94 84 26 0 81 85 22 10 7 85 28 74 50 69 41 52 85 76 6 84 29 71 15 81 0 12 56 37 61 100 59 61 7 16 29 67 32 84 54 13 34 60 1 85 12 0 2 16 79 100 69 58 70 88 57 43 46 40 20 12 15 75 7 22 56 2 0 访问节点顺序19 12 20 6

8、 1 7 5 18 15 2 13 3 9 10 16 8 4 14 11 17 代码：#include<iostream>#include<ctime>#include<cstdio>#include<cstdlib>#include<cmath>#include<time.h>#include<stdlib.h>#include<stdio.h> #include <windows.h>#define MAX 10000#define INF 10000000 #define E 0

9、.000000001 / 迭代误差 #define L 20000 / 迭代次数 #define AT 0.999 / 降温系数 #define T 1 / 初始温度 using namespace std; struct element /用来排序的数据结构 int data; / 数据 int index; / 序号 ;int tsp(int dMAX, int n, double e,int l,double at,double t,int s0); /利用模拟退火算法求解最短路径 int cmp(const void *a,const void *b); /升序排列 void rand

10、_of_n(int a,int n); /产生 1-n 的随机排列并存到 a 中int random(int m,int n);int disMAXMAX; / dij 表示客户i到客户j的距离，0 表示起始点 void rand_of_n(int a,int n)int i;struct element eleMAX;srand(int)time(0); / 初始化随机数种子 for(i=0;i<n;i+)elei.data=rand(); / 随机生成一个数 elei.index=i+1;qsort(ele,n,sizeof(ele0),cmp); /排序 for(i=0;i<

11、n;i+)ai=elei.index;int random(int m,int n) /产生m-n的随机数int a;double x=(double)rand()/RAND_MAX;a=(int)(x*(n-m)+0.5)+m;return a;int cmp(const void *a,const void *b) / 升序排序return(struct element*)a)->data - (struct element*)b)->data;int tsp(int dMAX, int n, double e,int l,double at,double t,int s0)i

12、nt i,j,sMAX,sum,temp;sum=INF; for(i=0;i<1000;i+) /利用蒙特卡洛方法产生初始解rand_of_n(&s1,n);s0=0; sn+1=0; /第一个和最后一个点为起始点 temp=0;for(j=0;j<=n;j+)temp=temp+dsjsj+1;if(temp<sum)for(j=0;j<=n+1;j+)s0j=sj;sum=temp; for(i=0;i<l;i+) /退火过程 int c1,c2;c1=random(1,n);c2=random(1,n);if(c1>c2)int temp=c

13、2; c2=c1; c1=temp; if(c1=c2)continue;int df=ds0c1-1s0c2 + ds0c1s0c2+1 - ds0c1-1s0c1 - ds0c2s0c2+1; /计算代价函数if(df<0) /接受准则while(c1<c2) int temp=s0c2; s0c2=s0c1; s0c1=temp;c1+;c2-;sum=sum+df; else if(exp(-df/t)>(double)rand()/RAND_MAX)while(c1<c2)int temp=s0c2; s0c2=s0c1; s0c1=temp;c1+;c2-;

14、sum=sum+df;t=t*at;if(t<e)break;return sum;int main() DWORD start, stop; int i,j;int n; cout<<"输入模式城市数量 然后输入回车,例如 10 回车"<<endl; cin>>n;start = GetTickCount();/程序开始时间 for(i=0;i<n;i+) / 随机产生距离 1-100for(j=i;j<n;j+)if(i=j)disij=0;elsedisij=disji=random(1,100); FILE*fp

15、 = fopen("模拟退火算法-随机产生数据.txt","w"); / 将距离存入文件中 for(i=0;i<n;i+) for(j=0;j<n;j+)fprintf(fp,"%d ",disij);fprintf(fp,"n");fclose(fp); int sum,sum0,s0MAX; sum0=0; /顺序遍历时的路程 for(i=0;i<n;i+)sum0=sum0+disii+1;sum0=sum0+disn0;sum=tsp(dis,n, E,L,AT,T,s0);fp = fopen("模拟退火算法-结果数据.txt","w"); /将结果存入文件中for(i=1;i<=n;i+)fprintf(fp,"%d ",s0i);fclose(fp); cout<<endl; cout<<"为了方便查看，数据和结果保存在文件中"<<endl; cout<<"<<<<邻接矩阵保存在文件 模拟退火算法-随机产生数据.txt 中"<&l