题解P2759（新）

· · 题解

你们没看错，我又双叒叕来写这道题的题解了！

昨天刚学习了模拟退火，发现好像可以用来搞很多二分和牛顿迭代的题？

关于数学处理的部分可以参见我前一篇题解或者各位大佬的题解，这篇题解主要讲用模拟退火算法来逼近正确答案。

首先，一段摘自百度百科的话 

    模拟退火算法（Simulate Anneal，SA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火是由S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所发明的。V.Černý在1985年也独立发明此演算法。模拟退火算法是解决TSP问题的有效方法之一。

简单地说，就是用随机数在那瞎搞，搞出什么是什么（逃

还是先来看看模拟退火的流程吧！

1.对所有可能的解，定义一个内能函数E(x)，能量越小则解越优;

2.设定初温T_0;

3.设定初始解x_0;

4.设定一个略小于1降温系数（我称之为\alpha）;//似乎别人都叫\Delta?别喷我QAQ

5.当温度T高于指定末温T*，重复以下步骤:

6.根据T在x_0附近产生一个随机解x;

7.计算能量差\Delta E=E(x)-E(x_0);

8.若\Delta E<=0，则用x替换x_0;

9.否则，令x_0有e^{-\Delta E/T}的概率被x替换;

10.将温度T乘上\alpha进行降温;

11.回到第五步;//没有缩进真难受QAQ

写成伪代码：

SA Algorithm
{
    define const α;
    define E(x);
    define x0;
    define ans=x0;//ans用于记录最优解
    define T=T0;
    while(T>T*)
    {
        define x=x0+random(-T,T)//指生成在[-T,T)范围内的随机数
        define ΔE=E(x)-E(x0);
        if(ΔE<0)ans=x0,x0=x;
        else if(random(0,1)<exp(-∆E/T))x0=x;//以exp(-ΔE/T)的概率替换当前解
        T*=α;
    }
    return ans;
}
//第一次写伪代码，因此有点鬼畜

其中，较差的解也有一定概率替换较优解，是为了防止答案过早在次优解上收敛。将\alpha、T_0增大能以时间换正确性，否则以正确性换时间。

这是本蒟蒻对模拟退火算法的理解，若有不当之处还请各位大佬指正QAQ

有了算法框架，写出具体代码就相对比较简单了。代码注释还是很详细的！

#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
const double alpha=0.99995;//降温系数，要慢慢调整，大了会TLE，小了会WA
int n;
double Rand()//生成[0,1)中的随机数
{
    return (double)rand()/RAND_MAX;//利用RAND_MAX宏来控制随机数范围
}
double Rand(double l,double r)//生成[l,r)中的随机数
{
    return (r-l)*Rand()+l;
}
double Energy(double x)//内能函数，显然xlgx越靠近n越优
{
    return abs(x*log10(x)-n);
}
double ans=500000;//用于记录全局最优解，防止在随机替换当前解时丢失最优解
double ansE=Energy(ans);
void SA()//算法主体
{
    double t=5e8;//初温，设得大一些以尽可能搜遍整个解空间，但太大会TLE //感觉设在整个解空间大小的一半差不多
    double now=ans;//初始解随便挑一个正常一点的数
    double nowE=Energy(ans);//计算当前解的能量
    while(t>1e-10)//控制末温，太高会爆精度，太低会TLE
    {
        double temp=now+Rand(-t,t);//生成随机解
        double E=Energy(temp);//计算随机解的能量
        double delta=E-nowE;//计算ΔE
        if(delta<=0)//随机解更优则直接替换当前解
        {
            if(E<ansE)ans=now,ansE=E;//更新全局最优解
            now=temp;
            nowE=E;
        }
        else
        {
            if(Rand()<exp(-delta/t))//否则有一定概率替换当前解
            {
                now=temp;
                nowE=E;
            }
        }
        t*=alpha;//降温
    }
}
int main()
{
    srand(time_t(0));//将命运交到时间的手中
    scanf("%d",&n);
    --n;//这里同前一篇题解
    SA();//用随机与暴力冲破一切阻碍
    int res=ans;//得到最终解的方法同前一篇题解
    if(int(res*log10(res)+0.5)<n)++res;
    printf("%d",res);//接受命运的裁决
}

模拟退火复杂度目测\Theta(clog_\alpha \frac{T*}{T_0})(c是内能函数的复杂度)？是解决难解问题的利器，思想与代码也不算太难（尽管很玄学）。

与其他常见的近似算法相比，模拟退火不需要二分的单调性，不需要三分的单峰函数，也不需要求导，还能拓展到除了方程求解以外的大量问题当中。  

虽然模拟退火有概率出错，但通过对其参数的反复调整，可以在正确性和速度之间找到最佳平衡。  

最后，该算法适合欧洲的同学使用。像我这种非酋还是少写吧QAQ