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

## 前言：本片适用于 模拟退火入门-进阶 **模拟退火（SA）** 是一种 **随机化**算法。当一个问题的方案数量极大（甚至是**无穷**的）而且不是一个单峰函数时，我们常使用模拟退火求解。 一般的，很多题都可以用模拟退火~~水过~~，在OI界称之 **[优雅的暴力]** ### 模拟退火算法入门 先用一句话概括(再借OIWIKI)：模拟退火=如果新状态的解更优则修改答案，否则以一定概率接受新状态 就是先随机出一个答案，如果这个答案是当前最优的就更新最优答案，反之则以一定概率认为这个答案可能更接近最优答案，而接受这个答案 下面是重点：如何 **随机出一个答案** 和 **确定接受新状态的概率**（并且要使随机出的答案尽可能接近最优解） 这就要引入一个新概念 **退火** 退火=固体退火原理，指固体在高温下徐徐冷却的事情 模拟退火的实现也近似固体退火原理，先有三个参数表示初始温度 $T_0$ ，降温系数 $d$ ，终止温度 $T_k$ 。其中 $T_0$ 是一个比较大的数，$d$ 是一个非常接近 1 但是小 1 的数， $T_k$ 是一个接近0的正数。 先将温度T初始成 $T_0$ ，每一次将 $T*=d$ ,直到 $T$ 到达$T_k$  现在我们开始解决如何 **随机出一个答案** 和 **确定接受新状态的概率** 1. 随机出一个答案：根据题目而变，但一般是随机出的，但是和简单的随机不同，这个答案一般是根据先有的解（注意，不一定是最优解，因为有一定概率我们接受了一个可能更接近最优答案的答案），在此基础随机出的 2. 确定接受新状态的概率：一般比较固定,常见写法是 ```if (exp(-delta（随机出一个答案-当前最优解） / t（当前温度）) > (double)rand() / RAND_MAX;)接受新状态``` ### 模拟退火算法进阶 1. 关于参数 模拟退火的参数基本上决定了代码的准确性，**一般的， $T_0$ 越高， $T_k$ 越低（ $T_k >0$ ），$d$ 越接近 $1$ ，模拟退火越准确，** 但时间越长，建议在写模拟退火是要卡卡参数 2. 关于随机数 模拟退火的精髓就在随机数上，随机数的随机性，循环周期基本上决定了准确度，随机性差，循环周期短的很可能将模拟退火卡掉，[建议参考这来优化随机数](https://oi-wiki.org//misc/random/) 3. 关于时间 模拟退火是一个**不太稳定**的算法 ~~（谁叫他随机）~~，单次可能找不到最优解，一般的要多次运行，有一个 ```clock()``` 函数，返回程序运行时间，建议在**不超时**的情况下尽可能多跑 一般的，可以这样```while ((double)clock()/CLOCKS_PER_SEC < MAX_TIME（一个小于时限的参数）) SA()（进行模拟退火）;``` ### 模拟退火算法例题 #### 计算几何(基本思想：在当前点上尝试) - [P1337 [JSOI2004]平衡点 / 吊打XXX](https://www.luogu.com.cn/problem/P1337) - [P5544 [JSOI2016]炸弹攻击1](https://www.luogu.com.cn/problem/P5544) - [P4035 [JSOI2008]球形空间产生器](https://www.luogu.com.cn/problem/P4035)(注意精度) - [P4703 偷上网](https://www.luogu.com.cn/problem/P4703) - [CF2C Commentator problem](https://www.luogu.com.cn/problem/CF2C) - [P4274 [NOI2004] 小H的小屋](https://www.luogu.com.cn/problem/P4274) - [SP4587 FENCE3 - Electric Fences](https://www.luogu.com.cn/problem/SP4587) #### 最优序列(基本思想：在当前序列上重新构造) - [P3936 Coloring](https://www.luogu.com.cn/problem/P3936) - [P2503 [HAOI2006]均分数据](https://www.luogu.com.cn/problem/P2503) - [P2538 [SCOI2008]城堡](https://www.luogu.com.cn/problem/P2538) - [P3878 [TJOI2010]分金币](https://www.luogu.com.cn/problem/P3878) - [P4966 基地建设](https://www.luogu.com.cn/problem/P4966) #### 其他(一般是数据太水的) - [P4360 [CEOI2004]锯木厂选址](https://www.luogu.com.cn/problem/P4360) - [P1742 最小圆覆盖](https://www.luogu.com.cn/problem/P1742) (注意精度) ### 其他（参考文献等） [广告1：如果你没有学习过模拟退火，看这里](https://oi-wiki.org//misc/simulated-annealing/) [广告2：如果你没有学习过模拟退火，看这里](https://www.luogu.com.cn/blog/Darth-Che/mu-ni-tui-huo-xue-xi-bi-ji) ### 更新日志 2021：08：05 更正 P4360 数据过水，且正解非退火