模拟退火详解&P1433题解
前排提示：LZ是个菜比，有可能有讲的不对的地方，请在评论区指出qwq
0.基本思想
模拟退火其实没有那么高大上。说白了就是初始化一个“温度”。每次随机乱选一个方案，如果比以前的方案优那么就要，否则就以一定的概率要或者不要。当前方案越狗屎就越不想要，“温度”越低越不想要。然后把温度降低一些，反复循环，直到温度为0为止。
1.照本宣科 实现
呃，就以 臭名昭著 著名的TSP问题举例子吧。
什么？你不知道TSP？这个就是->点我。
其实正解是搜索，但是\(O(n!)\)的时间复杂度实在伤不起（除了像本题一样\(n\le15\)），所以考虑模拟退火。
首先，初始化一个初始”温度“。越高越好，但是过高会让程序变慢，至于为什么以后再说。
const double T0=1e5/*初始温度*/,T_end=1e-4/*结束温度（由于非常接近0可以看作0）*/;
void SA(){
double T=T0;//当前温度
while(T>T_end){//对应”反复循环，直到温度为0为止。“这句话
}
}
然后胡乱生成一个解：
double calc(){//意思是查询当前解的代价，具体到问题里就是按照当前顺序访问要走多远
double ret=0.0;
for(int i=1;i<=n;i++){
ret+=g[ans[i-1]][ans[i]];//g数组的意思是从一个点到另一个点要走多少
}
return ret;
}
int random_disp(int l,int r){//意思是在区间[l,r]内随机生成一个数
srand(time(NULL));
static std::mt19937 random_engine(rand());
if(l>r)swap(l,r);
uniform_int_distribution u(l,r);
return u(random_engine);
}
const double T0=1e5/*初始温度*/,T_end=1e-4/*结束温度（由于非常接近0可以看作0）*/;
void SA(){
double T=T0;//当前温度
while(T>T_end){//对应”反复循环，直到温度为0为止。“这句话
int u=random_disp(1,n),v=random_disp(1,n);
swap(ans[u],ans[v]);
double new_sol=calc();//随机交换两个数，就相当于乱生成一个
//ans数组的意义是访问的顺序
}
}
判断是否要这个解：
inline bool CBP(double x){//Choose by probability.
//以概率x返回 true或者false
if(x>=1.0)return true;
if(x<=0.0)return false;
srand(time(NULL));
static std::mt19937 random_engine(rand());
uniform_real_distribution u(0.0,1.0);
return u(random_engine)<=x;
}
double calc(){//意思是查询当前解的代价，具体到问题里就是按照当前顺序访问要走多远
double ret=0.0;
for(int i=1;i<=n;i++){
ret+=g[ans[i-1]][ans[i]];//g数组的意思是从一个点到另一个点要走多少
}
return ret;
}
int random_disp(int l,int r){//意思是在区间[l,r]内随机生成一个数
srand(time(NULL));
static std::mt19937 random_engine(rand());
if(l>r)swap(l,r);
uniform_int_distribution u(l,r);
return u(random_engine);
}
const double T0=1e5/*初始温度*/,T_end=1e-4/*结束温度（由于非常接近0可以看作0）*/;
void SA(){
double T=T0;//当前温度
while(T>T_end){//对应”反复循环，直到温度为0为止。“这句话
int u=random_disp(1,n),v=random_disp(1,n);
swap(ans[u],ans[v]);
double new_sol=calc();//随机交换两个数，就相当于乱生成一个
//ans数组的意义是访问的顺序
if(new_sol 等等，exp(double(old_sol-new_sol)/T)是什么意思？
这个我当初也蒙了半天（我太蔡了），尽量讲的明白一点
先把它翻译成数学语言：
\[e^{\frac{\Delta f}{T}} \]再翻译成人话：
\(e\) (是个常数，大约是2.7) 的 (以前解 - 当前解 )除以当前温度次方
(以前解 - 当前解 )，也就是\(\Delta f\)，一定是个负数，为什么看看代码就知道了。
那么，\(\Delta f\)越小（也就是绝对值越大），也就是当前解越狗屎，\(\frac{\Delta f}{T}\)就越小。当\(T\)越小，也就是温度越小，\(\frac{\Delta f}{T}\)的绝对值也就越大，\(\frac{\Delta f}{T}\)也就越小。\(\frac{\Delta f}{T}\)越小，\(e^{\frac{\Delta f}{T}}\)也就越小（但一定大于0），正好对应了”当前方案越狗屎就越不想要，“温度”越低越不想要。“这句话。
降低温度并记录遇到的最优解：
inline bool CBP(double x){//Choose by probability.
//以概率x返回 true或者false
if(x>=1.0)return true;
if(x<=0.0)return false;
srand(time(NULL));
static std::mt19937 random_engine(rand());
uniform_real_distribution u(0.0,1.0);
return u(random_engine)<=x;
}
double calc(){//意思是查询当前解的代价，具体到问题里就是按照当前顺序访问要走多远
double ret=0.0;
for(int i=1;i<=n;i++){
ret+=g[ans[i-1]][ans[i]];//g数组的意思是从一个点到另一个点要走多少
}
return ret;
}
int random_disp(int l,int r){//意思是在区间[l,r]内随机生成一个数
srand(time(NULL));
static std::mt19937 random_engine(rand());
if(l>r)swap(l,r);
uniform_int_distribution u(l,r);
return u(random_engine);
}
const double T0=1e5/*初始温度*/,T_end=1e-4/*结束温度（由于非常接近0可以看作0）*/;
void SA(){
double T=T0;//当前温度
while(T>T_end){//对应”反复循环，直到温度为0为止。“这句话
int u=random_disp(1,n),v=random_disp(1,n);
swap(ans[u],ans[v]);
double new_sol=calc();//随机交换两个数，就相当于乱生成一个
//ans数组的意义是访问的顺序
if(new_sol 然后，不停循环，直到温度为0为止。
Code：
#include
using namespace std;
#define MAXN 20
int n,ans[MAXN],st=clock();
double g[MAXN][MAXN],x[MAXN],y[MAXN],ans_val=1e10;
double euc_dis(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
inline bool CBP(double x){//Choose by probability
if(x>=1.0)return true;
if(x<=0.0)return false;
srand(time(NULL));
static std::mt19937 random_engine(rand());
uniform_real_distribution u(0.0,1.0);
return u(random_engine)<=x;
}
int random_disp(int l,int r){
srand(time(NULL));
static std::mt19937 random_engine(rand());
if(l>r)swap(l,r);
uniform_int_distribution u(l,r);
return u(random_engine);
}
double calc(){
double ret=0.0;
for(int i=1;i<=n;i++){
ret+=g[ans[i-1]][ans[i]];
}
return ret;
}
const double T0=1e5,T_end=1e-4,DT=0.997;
void SA(){
double T=T0,old_sol=calc();
while(T>T_end){
int u=random_disp(1,n),v=random_disp(1,n);
swap(ans[u],ans[v]);
double new_sol=calc();
if(new_sol 以上代码能够ACP1433，也就是例题。
3.一些注意事项
- 由于模拟退火是个概率算法，所以除非你想不出正解最好不要用。
- 由于模拟退火是个概率算法，所以最好多跑几遍。
- 由于模拟退火是个概率算法，所以要仔细调整几个参数——初始温度、结束温度、变化率。
- 由于模拟退火是个概率算法，所以时间复杂度是 \(O(玄学)\)。初始温度越高，温度变化率越接近1，跑得越慢，也越精确。