TSP問題求解
? ? n個城市之間有一定距離,現(xiàn)在讓選擇一個城市出發(fā)，然后到達(dá)所有的城市,最后回到原點每個城市只到達(dá)一次,求出一條路徑并且求出最短的距離
? ?TSP問題是一個NP問題，但是可以求近似解，通過模擬退火算法實現(xiàn)，
源：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 //城市數(shù)量 #define T 3000 //初始溫度(最大距離) #define EPS 1e-8 //終止平衡溫度(精度) #define DELTA 0.98 //溫度衰減速率 (會控制最優(yōu)解) #define LIMIT 10000 //概率選擇上限 (控制最優(yōu)解) #define OLOOP 1000 //外循環(huán)次數(shù) (控制時間復(fù)雜度) #define ILOOP 15000 //內(nèi)循環(huán)次數(shù) ... using namespace std;struct Path { int citys[N];double len; }; //定義路線結(jié)構(gòu)體 struct Point { double x, y; }; //定義城市坐標(biāo)Path path; //記錄最優(yōu)路徑 Point p[N]; //每個城市的坐標(biāo) double dis[N][N]; //兩兩城市間的距離 int nCase; //測試次數(shù)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); //中間結(jié)果輸出nCase++; //測試樣例，可看時間復(fù)雜度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) //外循環(huán)，主要更新參數(shù)t，模擬退火過程{for (int i = 0; i < ILOOP; i++) //內(nèi)層循環(huán),尋找在一定溫度下的最優(yōu)解{newPath = GetNext(curPath, n);double dE = newPath.len - curPath.len;if (dE < 0) //降溫成功，找到的 newPath 是當(dāng)前更優(yōu){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) //如果找到比當(dāng)前更差的解，以一定概率接受該解，并且這個概率會越來越小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 是最終的結(jié)果printf("Total test times is : %d\n", nCase);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【模拟退火】解决【TSP】问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。