[模拟退火-优雅的暴力]

前言：本片适用于模拟退火入门-进阶

模拟退火（SA） 是一种 随机化算法。当一个问题的方案数量极大（甚至是无穷的）而且不是一个单峰函数时，我们常使用模拟退火求解。

一般的，很多题都可以用模拟退火水过，在OI界称之 [优雅的暴力]

先用一句话概括(再借OIWIKI)：模拟退火=如果新状态的解更优则修改答案，否则以一定概率接受新状态

就是先随机出一个答案，如果这个答案是当前最优的就更新最优答案，反之则以一定概率认为这个答案可能更接近最优答案，而接受这个答案

下面是重点：如何 随机出一个答案 和 确定接受新状态的概率（并且要使随机出的答案尽可能接近最优解）

这就要引入一个新概念退火

退火=固体退火原理，指固体在高温下徐徐冷却的事情

模拟退火的实现也近似固体退火原理，先有三个参数表示初始温度 T_0 ，降温系数 d ，终止温度 T_k 。其中 T_0 是一个比较大的数，d 是一个非常接近 1 但是小 1 的数， T_k 是一个接近0的正数。

先将温度T初始成 T_0 ，每一次将 T*=d ,直到 T 到达T_k

现在我们开始解决如何 随机出一个答案 和 确定接受新状态的概率

随机出一个答案：根据题目而变，但一般是随机出的，但是和简单的随机不同，这个答案一般是根据先有的解（注意，不一定是最优解，因为有一定概率我们接受了一个可能更接近最优答案的答案），在此基础随机出的
确定接受新状态的概率：一般比较固定,常见写法是 if (exp(-delta（随机出一个答案-当前最优解） / t（当前温度）) > (double)rand() / RAND_MAX;)接受新状态

模拟退火的参数基本上决定了代码的准确性，一般的， T_0 越高， T_k 越低（ T_k >0 ），d 越接近 1 ，模拟退火越准确， 但时间越长，建议在写模拟退火是要卡卡参数

模拟退火的精髓就在随机数上，随机数的随机性，循环周期基本上决定了准确度，随机性差，循环周期短的很可能将模拟退火卡掉，建议参考这来优化随机数

模拟退火是一个不太稳定的算法 ~~（谁叫他随机）~~，单次可能找不到最优解，一般的要多次运行，有一个 clock() 函数，返回程序运行时间，建议在不超时的情况下尽可能多跑

一般的，可以这样while ((double)clock()/CLOCKS_PER_SEC < MAX_TIME（一个小于时限的参数）) SA()（进行模拟退火）;

广告2：如果你没有学习过模拟退火，看这里

2021：08：05 更正 P4360 数据过水，且正解非退火