模擬退火求解TSP問題

模擬退火算法步驟

1.尋找下一個解
2.計算下一個解的能量
3.決定是否接受這個解
4.降溫

算法模板

double randfloat() {return rand()/(RAND_MAX+0.0); }double T0 = 1000000,Tk = 1,T = T0,d = 0.9999; int x = initx();//當前解(初始解) int ansE,nowE;//全局最優解的能量,當前解的能量ansE = nowE = E(x);while(T > Tk) {//1.產生新解int newx = generate(x);//2.計算新解的能量int newE = E(newx);//3.確定是否接受if(newE < nowE || randfloat() > exp((nowE-newE)/T)){nowE = newE;x = newx;}//4.降溫T *= d;//5.更新全局最優解Optimize(ansE,newE); }

TSP問題代碼

交題鏈接
http://acm.zjnu.edu.cn/CLanguage/showproblem?problem_id=1420

#include <iostream> #include <algorithm> #include <cstring> #include <ctime> #include <cmath> #include <assert.h> #define pr(x) std::cout << #x << ':' << x << std::endl #define rep(i,a,b) for(int i = a;i <= b;++i) #define int long long int G[21][21]; int n,m; int run(int x[]){int ans = 0;rep(i,1,n) {ans += G[x[i-1]][x[i%n]];}return ans; }double randfloat() {return rand()/(RAND_MAX+0.0); }int solve() {srand(time(NULL));int x[22];rep(i,0,n-1) x[i] = i+1;double T0 = 100000000,Tk = 1,T = T0,d = 0.99;int ans = run(x);int preans = ans;while(T > Tk) {//1.產生新解int a = rand()%n;int b = rand()%n;//std::swap(x[a],x[b]);std::reverse(x+a,x+b+1);//2.計算下一個解的能量int newans = run(x);Min(ans,newans);//3.確定是否接受if(newans >= preans) {if(randfloat() > exp((preans-newans)/T))//std::swap(x[a],x[b]);std::reverse(x+a,x+b+1);else preans = newans;}else preans = newans;//4.降溫T *= d;}return ans; }signed main() {std::cin >> n >> m;//setinf(G);if(n == 1) return 0*puts("0");rep(i,1,n) rep(j,1,n) {G[i][j] = 1e11;}rep(i,1,m) {int a,b,c;std::cin >> a >> b >> c;Min(G[a][b],c);Min(G[b][a],c);}std::cout << solve() << std::endl; }

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。