韩城建设公司网站,山东竞价推广公司,wordpress怎么首页幻灯片,深圳网站托管公司模拟退火求解TSP问题
模拟退火算法步骤
1.寻找下一个解 2.计算下一个解的能量 3.决定是否接受这个解 4.降温
算法模板
double randfloat() {return rand()/(RAND_MAX0.0);
}double T0 1000000,Tk 1,T T0,d 0.9999;
int x initx();//当前解(初始解)
int ansE,nowE;//全…模拟退火求解TSP问题
模拟退火算法步骤
1.寻找下一个解 2.计算下一个解的能量 3.决定是否接受这个解 4.降温
算法模板
double randfloat() {return rand()/(RAND_MAX0.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_id1420
#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_MAX0.0);
}int solve() {srand(time(NULL));int x[22];rep(i,0,n-1) x[i] i1;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(xa,xb1);//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(xa,xb1);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;
}
