模拟退火

模拟退火（Simulate Anneal，SA）用于寻找一个方案量极大且不为单峰函数的问题的全局最优解的随机化算法。

由于模拟退火是随机化算法，因此调参是十分痛苦的。但是它可以高效暴力地过题。

模拟退火主要的过程是这样的：

在模拟退火的过程中，程序首先会一直尝试不同的解，随着时间的进行，这个解会逐渐稳定下来，并在理想情况下逐渐停留在最优解（也可能不是最优解，因此我们需要多跑几次，毕竟这是随机化算法）。

总体来说大概是这样的一个过程（加载可能有点慢）：



（图片引自Wikipeida/Simulated_annealing）

对于多次的模拟退火，我们一般通过

while ((double)clock() / CLOCKS_PER_SEC <= MAX_TIME) SA();

来尽量多的进行模拟退火以保证得到最优解（MAX_TIME是个略小于题目时限且保证可以跑完一遍SA的值）。

而模拟退火的模板如下：

void SA()
{
    //每次退火前，将当前解置为答案（如是第一次就贪心设置）
    for (double T = 2000; T >= 1e-14; T *= 0.99) //这里的参数根据不同的题目凭感觉调（没错就是凭感觉）
    {
        //在当前解的基础上生成新解（如果可以的话，尽量将生成的新解变化的幅度与温度相关联）。
        if (ans - tmp < 0) //生成的新解更优
            //接受新解并更新答案
        else
            if (exp((tmp - ans) / T) > (double)rand() / RAND_MAX) //如果当前的解不够优，一定概率接受新解（下面会解释）
                //接受新解，不更新答案
    }
    return;
}

对于上面的一定概率接受新解的概率计算，其原理大概是这样的：

(double)rand() / RAND_MAX可以生成一个(0,1)的随机数。

exp为cmath中自带的函数，exp(x)的意思是$latex e^x$，对于这个函数，它在$latex (- \infty ,0)$上的值域为(0,1)且是单调递增的。因此，当前解与最优解的差越小，这个函数的值就越大，接受新解的概率就越大。温度越小，这个函数的值也就越小，接受新解的概率就越小，这样就可以符合模拟退火逐渐稳定的原则了。

以上就是模拟退火了，例题：洛谷P3936【Coloring】、洛谷P1337【[JSOI2004]平衡点 / 吊打XXX】