前言&&为什么要学模拟退火
其实是为了骗到更多的分，然后证明自己的RP。
说实话模拟退火是一个集物理与IT多方面知识与一身的高级随机化算法
PS：本文大部分内容参考rvalue大佬的博客，在本蒟蒻学习的过程过程中起到了极大的帮助。
什么是模拟退火&&模拟退火可以干什么
看的很蒙蔽？
其实模拟退火是一种随机化算法,一般用于求函数的极值。
当然TSP什么的跑起来也不在话下。
一般这个函数都是毫无规律的，
一般的随机化算法——爬山算法
首先对于上面的函数求极值问题我们很容易想到可以乱搞
假设当前的最优解位置为\(x\)，设函数值为\(F(x)\)，那么我们可以在一定范围内随机一个\(y\)，若\(F(y)>F(x)\)(假如求最大值)，那么将最优解\(x\)的位置移动至\(y\)。
这样的肯定会越来越接近最优解，不过可能会陷入一个局部最优解而无法出来。
注意爬山算法得出的最优解与初始解的位置以及搜寻的附近解的区域大小有关。
当然如果你寻找新方案的区间很大的话有概率跳出去, 但是太大的话又可能跳来跳去跳乱了从而找不到最优解
所以我们应该怎么办呢，
关于退火的核心理论
搞事情，那我们具体怎么实现呢？
根据热力学规律并结合计算机对离散数据的处理, 我们定义: 如果当前温度为\(T\), 当前状态与新状态之间的能量差为\(\Delta E\), 则发生状态转移的概率为：
\[P(\Delta E)=e^{\frac{\Delta E}{kT}}\]
显然如果\(\Delta E\)为正的话转移是一定会成功的, 但是对于\(\Delta E<0\)我们则以上式中计算得到的概率接受这个新解。
然后我们只要维护当前温度\(T\)即可。这里有三个比较重要的参数：初始温度\(T_0\)(视题目要求而定)，降温系数\(dlt\)(一般取\([0.9,0.998]\)之间的数)，终止温度\(EPS\)(视题目精度而定)
退火过程中我们先让\(T=T_0\)，然后进行一次转移，之后令\(T=dltT\)
当\(T<EPS\)时结束退火，并将当前解作为最优解。
看一个维基百科上的图理解一下吧：
模拟退火的实践核心——参数
要写得一手好模拟退火，强大的调参能力是必不可少的。以下简述几个常用的技巧：
- 关于\(EPS\)，这个主要视题目要求而定，一般比要求的精度多取两位小数就够了，主意取得太大可能会T。
- 关于\(dlt\)，一般情况下\(dlt\)的取值一旦减少一个数量级，时间复杂度就会增大\(10\)倍。因此谨慎调节\(dlt\)，如果发现总是找不到最优解那么可以考虑更慢的降温，即适当减小\(dlt\)。
- 关于\(T_0\)，这个和时间复杂度关系不大，不过一般情况下\(T_0\)越大越容易跳出局部最优解。
大致框架
- 根据当前解以及温度随机出下一个解
- 计算下一个解的能量
- 决定是否要接受这个新的解
- 进行降温
总结&&趣谈随机化算法
模拟退火在OI中是一种在最优化问题中骗分的好方法
对于一些奇奇怪怪的多元函数也可以用这个方法来求解
同时，其它的一些随机化算法也是有着很大的应用的，网上有一个比较有趣且形象的方法来理解它们：
- 兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。
- 兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。
- 兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。
- 兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。