目录
- 关于模拟退火的简言
- 思路
- 具体实现
- 总结
关于模拟退火的简言
模拟退火，一种著名的神奇玄学算法，因为正确性是靠随机来保证的，所以是AC纯看rp。但是因为其思路的优越性，正确率并不低。再很多题目都不失为一种优秀的算法。甚至在有的题目中可以成为正解，比如有无限种情况，且需要求近似解的话，通常其他算法无法求出无限的情况，那么模拟退火就是唯一的办法。
思路
模拟退火的思路，就像前面说的那样，玄学。每次在当前状态的情况下，根据随机数，随机生产下一个状态，再根据一定的概率接受新的解。至于为什么会接受更劣的解呢？因为很多题目的答案可能是多峰函数。如下面这张图：
假如我们不接受劣解的话，一开始如果进入了左部分，很显然就找不到右部分的正解。所以我们要以一定的概率走出当前的局部最优解，去寻找全局最优解。
接下来我们进入到模拟退火的具体实现，首先，我们引入几个参数： E m a x E_{max} Emax ,当前找到的最优解 ， E v E_{v} Ev ,当前找到的新解， E u E_u Eu 上一个选择的节点 Δ E \Delta E ΔE 表示当前找到的新节点与当前最优解的差即 E m a x − E v E_{max}-E_v Emax−Ev 。初温 T s T_{s} Ts 当前温度 T T T ,末温 T t T_{t} Tt ,温度变动量 Δ \Delta Δ 。
对于每个参数的初值，我们通常将初温设为一个较大的数(如3000~4000)， Δ \Delta Δ 设为一个略小于1的数(如0.997) ,末温设为一个非常接近于0的数(如1e-18)。我们每次从初温开始，每次将当前温度乘上温度变量求得当前温度( T = T s ∗ Δ T = T_s*\Delta T=Ts∗Δ),再根据当前的温度，随机求出一个新解。
模拟退火的精髓就在于接受劣解，那我们应该如何接受这个新解呢？这时我们就要引入一个新原则Metropolis接受准则 。关于这个原则的证明，就不给出了因为太难了，我不会。我们就只分析它的结论。假设我们当前要求的是最大值，如果新解大于全局最优解，就接受这个新解。如果这个解劣于当前的最优解，那么设 Δ E = E v − E m a x \Delta E = E_v - E_{max} ΔE=Ev−Emax ，那么接受新解的概率就是 e x p ( Δ E T ) exp(\frac{\Delta E}{T}) exp(TΔE) ,对于这个式子的理解，首先因为 Δ E \Delta E ΔE 肯定是一个负数，所以他的差距越大，说明解越劣。接受概率也越低。而又因为负数的原因，T 越大的话 Δ E \Delta E ΔE 越大，所以接受概率也是越高的。而对于这里的exp，是一种高等数学里以自然常数e为底的指数函数。其的函数图像如下:
通过这张图我们可以发现，他的函数性质是单调上升+值总是为0。而这就非常符合我们的需求，值越大接受概率越高且值不为负数。
具体实现
前面口胡完了，下面就是模拟退火的具体实现。下面我们先找一道模拟退火的经典例题，P1337 [JSOI2004] 平衡点 / 吊打XXX，它的题意就是求出一个点的坐标，使得所有点达成平衡。很明显，它的可行的状态有无限多种，所以模拟退火就是不错的解法。
模拟退火的第一步，也是影响其时间复杂度与正确率最大的一步。——设置初始参数。我们需要根据题目每次判断新解的时间与题目要求的最大时间，根据这些综合出我们的初始参数。因为模拟退火是一种玄学算法，所以跑的越多肯定越优。而这一题中，显然判断一个点是否平衡，显然需要 O ( n ) O(n) O(n) 判断计算每个点的能量。所以我们可以将调参数小一点。
然后就是模拟退火的理论实现，首先我们需要每次在当前解的情况下求得一个新解，这个新解一般亲下，既要与当前解有关联，也要与当前温度有关联。说以一般随机出一个值，在原状态下处理。然后再根据上面提到的原则一定概率接受这个新解就可以了。
#include<bits/stdc++.h>
using namespace std;
double down=0.9995;//降温系数
double ansx,ansy,ans=100000000000000;//答案所在的位置与值
const int N=100010;
int n;
struct node{int weight,x,y;
}a[N<<1];
double find(double xx,double yy){//判断新解的答案double sum=0;for(int i=1;i<=n;i++){double chax=xx-a[i].x;double chay=yy-a[i].y;sum+=(sqrt(chax*chax+chay*chay))*a[i].weight;//计算绳子的势能//物重一定，绳子越短，重物越低，势能越小 //势能又与物重成正比 }return sum;//当前点的势能，即当前新解的答案
}
void sa(){//sa 是 simulate_anneal 的简写//ex ey 表示新解 ,xx yy 表示上一轮的解 ans 表示当前的最优解double xx=0,yy=0;//设定一个初值，如果做多次模拟退火的话设为上一次的最优解double T=3070;//T是初温，设为这个数ddddwhile(T>1e-15){//设定末温double ex=xx+(rand()*2-RAND_MAX)*T;double ey=yy+(rand()*2-RAND_MAX)*T;//这里这么写是因为我们需要随机出负数，但rand并没有这个功能//而rand的范围是0~RAND_MAX 上面这样写就成了 -RAND_MAX~RAND_MAXdouble now_ans=find(ex,ey);//判断新解的答案double delans=now_ans-ans;//计算当前点的答案与最优解的差if(delans<0){//小于0说明答案更优ansx=ex;ansy=ey;ans=now_ans;xx=ex;yy=ey;}else if(exp(-delans/T)*RAND_MAX>rand()){//劣解根据一定概率接受xx=ex;yy=ey;}T*=down;//降温}
}
int main(){srand(time(NULL));//设定一个随机种子，其实有的时候用mt19937也是一个好选择cin>>n;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y>>a[i].weight;}sa();printf("%.3lf %.3lf",ansx,ansy);
}
此贴完…了一半。你会发现你兴致冲冲的打完代码后一交，成功收获了WA,这就是因为模拟退火的玄学性质，这是我们就需要使用到调参，根据当前代码的所用时间，适当的调低降温参数或是提高初温等(其实值有修改降温参数才会有明显的区别)。或是可以多跑几遍模拟退火。然后经过不断的尝试与修改，我们终于收获了AC。
总结
模拟退火的本质就是一种随机玄学算法，所以就注定了它的正确性也是玄学的，所以我们在考场上在正解另有其他的情况下尽量少用，但是如果想不出正解的话，他也不失为一种优秀的骗分方式(万一你rp爆棚，碾压表算了呢)。但是在考场上就没有评测机这种东西帮你调试参数，你只能自己造数据，自己测试调参。所以一定要预留一定的时间，不要卡的太死(除非你用的是一个超级老爷机)。
完结撒花✿✿ヽ(°▽°)ノ✿这次真的完了
