【模拟退火】解决【TSP】问题

TSP问题求解
    n个城市之间有一定距离,现在让选择一个城市出发，然后到达所有的城市,最后回到原点每个城市只到达一次,求出一条路径并且求出最短的距离
   TSP问题是一个NP问题，但是可以求近似解，通过模拟退火算法实现，
源：https://blog.csdn.net/acdreamers/article/category/1160225/4

 

#include <iostream> #include <string.h> #include <stdlib.h> #include <algorithm> #include <stdio.h> #include <time.h> #include <math.h> //#define LOCAL #define N 30 //城市数量 #define T 3000 //初始温度(最大距离) #define EPS 1e-8 //终止平衡温度(精度) #define DELTA 0.98 //温度衰减速率 (会控制最优解) #define LIMIT 10000 //概率选择上限 (控制最优解) #define OLOOP 1000 //外循环次数 (控制时间复杂度) #define ILOOP 15000 //内循环次数 ... using namespace std;struct Path { int citys[N];double len; }; //定义路线结构体 struct Point { double x, y; }; //定义城市坐标Path path; //记录最优路径 Point p[N]; //每个城市的坐标 double dis[N][N]; //两两城市间的距离 int nCase; //测试次数double dist(Point A, Point B) { return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y)); } void GetDis(Point p[], int n) {for (int i = 0;i < n;++i)for (int j = 0;j < n;++j)dis[i][j] = dis[j][i] = dist(p[i], p[j]); }void Input(Point p[], int &n) {scanf("%d", &n);for (int i = 0; i < n; i++)cin >> p[i].x >> p[i].y;//scanf("%f %f", &p[i].x, &p[i].y); }void Init(int n) {nCase = 0; path.len = 0;for (int i = 0; i < n; i++){path.citys[i] = i;if (i != n - 1){printf("%d--->", i);path.len += dis[i][i + 1];}elseprintf("%d\n", i);}printf("Init path length is : %.4f\n", path.len); }void Print(Path t, int n) {printf("Path is : ");for (int i = 0; i < n; i++){if (i != n - 1)printf("%d-->", t.citys[i]);elseprintf("%d\n", t.citys[i]);}printf("The path length is : %.4f\n", t.len); } Path GetNext(Path p, int n) {Path ans = p;int x = (int)(n * (rand() / (RAND_MAX + 1.0)));int y = (int)(n * (rand() / (RAND_MAX + 1.0)));while (x == y) x = (int)(n * (rand() / (RAND_MAX + 1.0))), y = (int)(n * (rand() / (RAND_MAX + 1.0)));swap(ans.citys[x], ans.citys[y]);ans.len = 0;for (int i = 0; i < n - 1; i++)ans.len += dis[ans.citys[i]][ans.citys[i + 1]];cout << "nCase = " << nCase;Print(ans, n); //中间结果输出nCase++; //测试样例，可看时间复杂度return ans; } void SA(int n) {double t = T; //开始温度srand(time(NULL));Path curPath = path;Path newPath = path;int P_L = 0;int P_F = 0;while (1) //外循环，主要更新参数t，模拟退火过程{for (int i = 0; i < ILOOP; i++) //内层循环,寻找在一定温度下的最优解{newPath = GetNext(curPath, n);double dE = newPath.len - curPath.len;if (dE < 0) //降温成功，找到的 newPath 是当前更优{curPath = newPath;P_L = 0;P_F = 0;}else{double rd = rand() / (RAND_MAX + 1.0);if (exp(dE / t) > rd && exp(dE / t) < 1) //如果找到比当前更差的解，以一定概率接受该解，并且这个概率会越来越小curPath = newPath;P_L++;}if (P_L > LIMIT){P_F++;break;}}if (curPath.len < newPath.len) path = curPath;if (P_F > OLOOP || t < EPS) break;t *= DELTA;} } int main() {//freopen("TSP.data", "r", stdin); #ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout); #endif // LOCALint n;Input(p, n);GetDis(p, n);Init(n);SA(n);Print(path, n); //path 是最终的结果printf("Total test times is : %d\n", nCase);return 0; }

 

总结

以上是生活随笔为你收集整理的【模拟退火】解决【TSP】问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。