《模拟退火算法求解TSP问题 C++》由会员分享，可在线阅读，更多相关《模拟退火算法求解TSP问题 C++（12页珍藏版）》请在金锄头文库上搜索。
1、模拟退火算法的应用一Travelling Salesman Problem作为模拟退火算法应用，讨论货郎担问题(Travelling Salesman Problem, 简记为TSP):设有n个城市，用数码1,n代表。城市i和城市j之间的距离 为d(i，j) i, j=1,n. TSP问题是要找遍访每个域市恰好一次的一条回路， 且其路径总长度为最短.。将城市编号及其对应的坐标信息放入TSP. txt文件 中，由程序读出，进行模拟退火算法的计算，找到最优解并且保存在.txt文本 中，涉及到的TSP .txt文本信息格式如下：主要程序变量定义及其功能函数如下：/#include viostream
2、.h#include vfstream.h#include #include #include vstdlib.h#include vtime.h/ /模板输出函数template void Print(const T *pData, int nsize)for (int i=0; ivnsize; i+)cout *(pData+) 9cout endl;/#defineTSPN60/ TSP中的城帀数目#defineT_CONST10/初始化温度时给定的常数温度#defineT_INIT500/初始化温度时给定的初始温度#defineR_CONST0.9/初始化温度时给定的常数#defin
3、eR_MIN0.05/初始化温度时的终止条件#defineSTEPN400/初始化温度时退火的迭代步数#defineK_T0.9/降温时的降温参数#defineR_ACCEPT0.3/内循环的接受比率指标#defineT_ZERO0.5/零度法中的最小温度/解状态,根据不同问题设定struct ANSWER;/ Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx
4、 Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx*int *pAnswer; double *pData;函数名称：TSPRead() 输入参数：*pfile -文件名TSPN返回值：double* -指向坐标文件的一维数组说明：读取TSP坐标文件Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx
5、 Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx /double* TSPRead(char *pfile)double *pBuf, dData, *pData;pBuf = new doubleTSPN*2;if (pBuf = NULL)cout dData; /读出城市序号 for (int j=0; j dData) break; *(pData+) = dData;infile.close();return pBuf;/函数名称：TSPDistance()输入参数：x y -
6、城市序号0开始，*pData -城市坐标数组返回值：double -两城市间的距离 说明：计算两个城市间的距离/ Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx*Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx
7、Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx /double TSPDistance(int x, int y, const double *pData)double distance;distance = sqrt(*(pData+x*2) - *(pData+y*2) * (*(p
8、Data+x*2) - *(pData+y*2) + (*(pData+x*2+1) - *(pData+y*2+1) * (*(pData+x*2+1) - *(pData+y*2+1);return distance;/函数名称：TSPDeta()输入参数：*pfile -文件名 返回值：double -最大距离与最小距离的估计值 说明：计算TSP中的最大距离与最小距离的估计值/ Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx T
9、x Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx*Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx T
10、x Tx Tx Tx Tx Tx /double TSPDeta(char *pfile)double *pFile = TSPRead(pfile);Print(pFile, 2*TSPN);double dTmp, dMax, dMin, dSum;dSum = 0.0;for (int i=0; i dMax) dMax = dTmp;if (dTmp dMin) dMin = dTmp;dSum += dMax - dMin;delete pFile;pFile = NULL; return dSum;/i*函数名称：Equal()*输入参数：s0 -源目标解s1 -目的解*返回值：*
11、说明：两个解之间的复制/Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx /void Equal(ANSWER s1, ANSWER s0)memcpy(s1.pAnswer, sO.pAnswer, TSPN * sizeof(int); memcpy(s1.pData, sO.pData, TSPN * 2 * sizeof(double);/ Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx
