算法导论——模拟退火
Victory_Defeat
2019-08-14 10:30:05
今天来说一个**玄学**算法：模拟退火！（真·玄学）
先说一说它的名称来源：[$Link$](https://baike.baidu.com/item/%E9%80%80%E7%81%AB/1039313)
>退火是一种金属热处理工艺，指的是将金属缓慢加热到一定温度，保持足够时间，然后以适宜速度冷却。……
这貌似和$OI$毫无关系啊……，再看看模拟退火？[$Link$](https://baike.baidu.com/item/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB)
>模拟退火（$Simulate\ Anneal$，$SA$）的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是一种通用的优化算法，其物理退火过程由加温过程、等温过程、冷却过程这三部分组成。
这……还真有关系，而且就是**思路**
下面解释一下模拟退火的几个**特点**：
1. ~~非酋不建议使用，看脸~~ 选一个好的**随机种子**很重要，当然`srand(time(NULL))`也可以（本人使用）
2. 日常**调参**（降温系数，初温，末温，次数）
3. 如果当前值更优，则**无条件**将当前值作为最优解，并接受，否则**以一定概率**接受当前值（概率与温度有关）
4. 一次难以出正解 ~~欧皇除外~~
下面附图，便于理解：
看得出，高温时答案会不断跳动
但随着温度降低，逐渐在最优解附近稳定
（当然，正常情况下，常会误入歧途，跑到次优解去了）
步骤：
1. 随机选一个
2. 如果当前值更优，则**无条件**将当前值作为最优解，并接受，否则**以一定概率**接受当前值（概率与温度有关）
3. 降温，如果温度低于末温，结束
附常用参数：
降温系数 $0.993$ ~ $0.998$
初温 $2000$ ~ $5000$
末温 $1e-13$ ~ $1e-17$
次数 $3$ ~ $20$
对于调参：
如果您~~脸黑~~没有$AC$，可以调大初温或调小末温
如果您时间充裕，也可以多跑几次或者调大降温系数
附上本人[P1337\[JSOI2004\]平衡点/吊打XXX](https://www.luogu.org/problem/P1337)AC代码：
```cpp
#include<bits/stdc++.h>
#define cold 0.997
#define temperature 3000
#define lastemp 1e-15
#define times 3
#define INF 1<<30
using namespace std;
struct node
{
int x,y,w;
}a[1001];
int n;
double t,tx,ty,tw,ansx,ansy,anse;
double energy(double x,double y)
{
double e=0;
for(int i=1;i<=n;++i)
{
tx=x-a[i].x;
ty=y-a[i].y;
tw=a[i].w;
e+=sqrt(tx*tx+ty*ty)*tw ;
}
return e;
}
void SA()
{
t=temperature;
while(t>lastemp)
{
double nx=ansx+((rand()*2)-RAND_MAX)*t;
double ny=ansy+((rand()*2)-RAND_MAX)*t;
double ne=energy(nx,ny);
if(ne<anse)ansx=nx,ansy=ny,anse=ne;
else if(exp((anse-ne)/t)*RAND_MAX>rand())ansx=nx,ansy=ny;
t*=cold;
}
}
int main()
{
srand(time(NULL));
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>a[i].x>>a[i].y>>a[i].w;
ansx+=a[i].x;
ansy+=a[i].y;
}
ansx/=n;
ansy/=n;
anse=energy(ansx,ansy);
for(int i=1;i<=times;++i)SA();
printf("%.3lf %.3lf",ansx,ansy);
return 0;
}
```
跑得稍微有点慢，共计$1200ms$多，但都每个点不超过$400ms$，如果有巨佬有更优参数可以在评论里告诉我（该题某篇题解参数亲测不行）
一些问题与回答
$Q$：如果调参调到极限还是不能$AC$怎么办？
$A$：~~您太非了~~ 试试多交几次或者换个随机种子
（随机种子例子：$19****17$，$233333$，$114**\ *$）
$Q$：怎么调参？
$A$：~~看心情~~ 在保证$AC$的情况下，尽量调小一些
$Q$：如果无论如何都$AC$不了呢？
$A$：~~您可以去非洲了~~ （叹气）您还是去打正解吧
习题：[P2503\[HAOI2006\]均分数据](https://www.luogu.org/problem/P2503)
（闲话：模拟退火英文名$SA$，即$Simulate\ Anneal$，就是模拟+退火）