原模拟退火算法解决TSP问题c++源程序.doc

模拟退火算法解决TSP问题源程序（C+）/* 模拟退火算法解决TSP问题*/ /* 输入格式(城市坐标.in)： 第行:1个整数N，表示城市的数量 第.N+1行：每行有个空格分开的整数x,y，第i+1行的x,y表示城市i的坐标 */ #include #include #include using namespace std; const int MAXN = 501; /最大城市数 const double INIT_T =2000; /初始温度 const double RATE = 0.95; /温度衰减率 const double FINAL_T = 1E-10; /终止温度 const int IN_LOOP = 13000; /内层循环次数 const int OUT_LOOP = 2000; /外层循环次数 const int P_LIMIT = 10000; /概率选择次数 struct path /定义路径结构类型 int CityMAXN; /依次遍历的城市的序号 double Length; /所有城市的路径总长度 ; int N; /城市数量 double DMAXNMAXN; /任意两个城市之间的距离 path bestpath; /最优的遍历路径 inline double dist(int x1, int y1, int x2, int y2) /计算两点之间的距离 return sqrt(double(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1); inline double totaldist(path p) /计算遍历路径P的总长度 int i; double cost = 0; for (i=1; iN; i+) cost += Dp.Cityip.Cityi+1; cost += Dp.City1p.CityN; return cost;void init() /读入数据，并初始化 int CMAXN2; /城市的坐标 int i, j; freopen(城市坐标.in, r, stdin); /freopen(结果输出.out, w, stdout); scanf(%d, &N); for (i=1; i=N; i+) scanf(%d%d, &Ci0, &Ci1); for (i=1; iN; i+) /计算任意两个城市之间的路径长度 for (j=i+1; j=N; j+) Dij = Dji = dist(Ci0, Ci1, Cj0, Cj1); for (i=1; i=N; i+) /最优解的初始状态 bestpath.Cityi = i; bestpath.Length = totaldist(bestpath); srand(unsigned)time(NULL); /* 产生新路径方法 */path getnext(path p) /新解产生函数 int x, y; path ret; ret = p; do x = rand() % N + 1; y = rand() % N + 1; while(x = y); swap(ret.Cityx, ret.Cityy); /交换两城市之间位置顺序 ret.Length = totaldist(ret); return ret; /* 退火和降温过程 */ void sa() double T; /温度 path newpath, curpath; /当前路径和新路径 int i, P_t=0, A_t=0; double delta; T = INIT_T; /赋值初始温度 curpath = bestpath; while(true) for (i=1; i=IN_LOOP; i+) newpath = getnext(curpath); /获取新路径 delta = newpath.Length - curpath.Length; if (delta rnd) curpath = newpath; P_t+; if (P_t =P_LIMIT) A_t+; break; if (curpath.Length= OUT_LOOP | T FINAL_T) break; T = T * RATE; /降温 /* 程序主函数 */int main() init(); printf(初始路径长度: %.4fn, bestpath.Length);for(int i=0;i, bestpath.City+i);printf( %d, bestpath.City1); printf(n); sa(); printf(最优路径长度: %.4fn, bestpath.