模拟退火学习笔记

用模拟退火写神题好妙啊。。

为了能骗更多分我就学习一个吧qwq。、

退火算法是一个比较玄学妙的搜索算法。

比较适合有明确状态估价的题,当然你自己yy一个估价函数来选最优解也不是不可以,有些容易死在次优解上的题可以多退火几次(逃

初始解的选取可以选择xjb贪心可以较好的优化你退火的准确性。

我们先考虑爬山。每次贪心判断当前是否最优,然后选取较优解。然鹅这个算法容易陷入局部最优。

我们引入一个概念叫做温度,根据热力学第二定律温度越高越容易发生一些更大的偏差(等等第二定律不是熵增么,我们在温度较大的情况下允许一些小范围的偏差就可以了。

温度我们可以设置指数递减?大概就是每做一次t*=0.99之类的

不要问我为什么反正看起来就很优美(逃

然后多退火几次我们就有很大概率获得最优解辣!

其实随机开始状态多爬山几次也是一样的

丢一个求费马点的退火自行感受(这个好像直接爬山也可以?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define eps 1e-15
#define sqr(x) ((x)*(x))
inline ll read(){
char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
ll k=0,kk=1;if (c=='-')c=getchar(),kk=-1;
while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;
}using namespace std;
void write(ll x){if (x<0)x=-x,putchar('-');if (x/10)write(x/10);putchar(x%10+'0');}
void writeln(ll x){write(x);puts("");}
int n,fx[1010],fy[1010],w[1010];
ld del,ans,xx,yy,x,y;
ld check(ld x,ld y){
ld ans=0;
for (int i=1;i<=n;i++)ans+=sqrt(sqr(x-fx[i])+sqr(y-fy[i]))*w[i];
return ans;
}
ld cmp(ld x){return x>=0?1:exp(x/del)*RAND_MAX>rand();}
signed main(){
n=read();for (int i=1;i<=n;i++)fx[i]=read(),fy[i]=read(),w[i]=read();
del=0.1;ans=check(0,0);while (del>eps){
xx=x+(rand()*2-RAND_MAX)*del,yy=y+(rand()*2-RAND_MAX)*del;
ld dd=check(xx,yy);if (cmp(ans-dd)){
x=xx;y=yy;ans=dd;
}del*=0.995;
}printf("%.3Lf %.3Lf",x,y);
}

詹神的随机搜索好像很妙

码一下

1
2
3
4
5
6
7
8
9
10
11
for (i=1;i<=500000000/m;i++)
{
u=rand()%n+1,v=rand()%n+1;
swap(p[u],p[v]);
r=calc();
if (w>r-o)
o=0,w=r;
else
o=o+n/60,swap(p[u],p[v]);
s=min(s,r);
}
分享到