爬山算法 & 模拟退火

爬山算法

简介

爬山算法就是求类似「单峰函数极值」题目的算法。

• 单峰函数极值？三分！
  

想法很美好，但是你觉得出题人会老老实实的让你用三分吗？
一个二维空间让你求一个极值还算好说，那三位，四维呢？反正我不会三分。
以是我们就只能返来学一下这个诡异的爬山算法。
为什么说它诡异？如果你看了一下标签就知道这是一个随机算法！后面的就本身悟吧。
过程

假设这里有一个「山」(单峰函数)，你打算去山顶(函数最大值)，但你不知道要往哪走，于是你开始乱扔末影珍珠(取随机值)，要是落点比当前更优就传送上去。
你一开始比力急(因为再不快就TLE了)，于是你扔的范围比力大，后面越来越岑寂你扔的范围越来越小，末了找到极值。
在具体实现上我们会定义三个变量，以及一个函数：

• \(T\) (初始温度)
  
• \(K\) (降温速度)
  
• \(T_0\) (结束温度)
  
• \(E(x)\) (能量函数)
  

就是先rand一个值，然后检查一下这个值是不是比当前答案更优，如果是，就将当前答案赋成这个rand值，否则就不管。
在每一次rand之后，都要让 \(T\) 降温，就是让 \(T\) 乘上 \(K\)，这样可以使温度越降越慢，提拔准确度。
另外，温度越低，rand的范围越小。
再取值上，既要包管答案足够精确，又要包管不会TLE。
再不会T的情况下，\(T\) 越大越好，\(K\) 通常取 \([0.985,0.995]\) 之间的实数，\(T_0\) 包管了精度，再精度要求较高的情况下可以取 \([1e-9,1e-15]\)，固然就是在不会T的情况下越小越好(千万不能等于零)
模拟退火

简介

固然出题人肯定不会让你好受，搞出来个多峰函数求最值，就可以使用模拟退火：

摘自OI Wiki

可以看它会跳到比当前答案不优的地方，这也就是模拟退火可以求多峰函数极值的原因。
过程

模拟退火的实现过程与爬山基本一样，区别就是当当前rand值不比当前答案优时，依然有概率跳已往，但是为包管答案的准确性，答案依旧时记录最有项。
这样说可能不太明白，下面说几道例题。
例题

平衡点 / 吊打XXX\(^{luoguP1337}\)

根据物理知识，能量函数可以定义为：

\[E(x,y)=\sum_{i=1}^{n}w_i\sqrt{(x-x_i)^2+(y-y_i)^2}\]
细节方面请看代码：

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int NUM=1e4+10;
4. const int inf=0x3f3f3f3f;
6. int n;
7. struct node{
8.         double x,y,w;
9. }A[NUM];
10. double K=0.999;
11. double ansx,ansy,ans;
13. double E(double x,double y){
14.         double sum=0;
15.         for(int i=1;i<=n;++i){
16.                 sum+=sqrt((A[i].x-x)*(A[i].x-x)+(A[i].y-y)*(A[i].y-y))*A[i].w;
17.         }
18.         return sum;
19. }
21. void work(){
22.         double T=10000;
23.         while(T>1e-15){
24.                 double x=ansx+(rand()*2-RAND_MAX)*T;//T越小范围越小
25.                 double y=ansy+(rand()*2-RAND_MAX)*T;
26.                 double tmp=E(x,y),d=tmp-ans;
27.                 if(d<0){
28.                         ansx=x,ansy=y,ans=tmp;
29.                 }else if(exp(-d/T)*RAND_MAX>rand()){
30.                         //不优时也有概率跳过去，但ans不更新
31.                         //这个 exp(-d/T)*RAND_MAX>rand() 就是 T 越小概率越大
32.                         ansx=x,ansy=y;
33.                 }
34.                 T*=K;
35.         }
36. }
38. signed main(){
39.         srand(23751146);//玄学种子
40.         cin>>n;
41.         for(int i=1;i<=n;++i){
42.                 cin>>A[i].x>>A[i].y>>A[i].w;
43.                 ansx+=A[i].x,ansy+=A[i].y;
44.         }
45.         ansx/=n,ansy/=n;ans=E(ansx,ansy);
46.         work();work();//多跑两遍
47.         printf("%.3lf %.3lf\n",ansx,ansy);
48.         return 0;
49. }

复制代码