[链接登录后可见]
前言
模拟退火 是一个玄学的算法,数据一般很弱,调试中中有各种调参的过程,在 OI 赛制中很少用到。
模拟退火
什么是“退火”?
退火是一种金属热处理工艺,指的是将金属缓慢加热到一定温度,保持足够时间,然后以适宜速度冷却。目的是降低硬度,改善切削加工性;消除残余应力,稳定尺寸,减少变形与裂纹倾向;细化晶粒,调整组织,消除组织缺陷。准确的说,退火是一种对材料的热处理工艺,包括金属材料、非金属材料。而且新材料的退火目的也与传统金属退火存在异同。
看起来很高大上?(其实就是个屑
算法实现
模拟退火 与 爬山 不一样之处在于:爬山是一味贪心,模拟退火是循序渐进。(这是名字由来)
Metropolis 准则
更优:$\Delta E<0$,一定接受。
更劣:
扔一张图:

模拟退火 函数
const int delta=XXX;
const double eps=XXX;
void SA(){
double T_0=XXX;
while(T_0>eps){
XXX;
double rw=energy(rx,ry);
double ans=rw-vw;
if(ans<0) XXX;
else if(exp(-ans/T_0)*RAND_MAX>rand()) XXX;
T_0*=delta;
}
}
小技巧/调参技巧
模拟退火运行多次更有效,可以使用如下方法:
const double Time_Limit=;//题目时限低一点点
while((double)clock()/CLOCKS_PER_SEC<Time_Limit) SA();
调参考虑调一下参数:
T_0
,delta
,eps
,srand()
,Time_Limit
。
例题
[链接登录后可见]
模板题。
#include<bits/stdc++.h>
using namespace std;
const int _=2001;
const double downer=0.996, eps=1e-15;
int n, x[_], y[_], w[_];
double vx, vy, vw;
double energy(double xx, double yy){
double ans=0;
for(int i=1;i<=n;i++){
double dx=xx-x[i], dy=yy-y[i];
ans+=sqrt(dx*dx+dy*dy)*w[i];
}
return ans;
}
void fire(){
double t=3000;
while(t>eps){
double rx=vx+(rand()*2-RAND_MAX)*t;
double ry=vy+(rand()*2-RAND_MAX)*t;
double rw=energy(rx,ry);
double ans=rw-vw;
if(ans<0){
vx=rx;
vy=ry;
vw=rw;
}
else if(exp(-ans/t)*RAND_MAX>rand()){
vx=rx;
vy=ry;
}
t*=downer;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i]>>w[i];
vx+=x[i], vy+=y[i];
}
vx/=n,vy/=n,vw=energy(vx,vy);
fire();fire();fire();fire();
printf("%.3lf %.3lf",vx,vy);
return 0;
}
```