模拟退火算法
模拟退火
首先看一下度娘的定义
模拟退火算法（Simulate Anneal，SA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解
模拟退火是一种非常好用的随机化算法，它是爬山算法的改进版
爬山算法的思想就是一个劲的找最优解，如果接下来的任何状态都比当前状态差，那么就停止
但是这样显然是错误的，比如下面这种情况
爬山找到A点之后就GG了，但是模拟退火算法会以一定的概率走向F，进而走向B，找到更优的解
至于这里为什么叫做“退火”，还要从物理学说起
在热力学上，退火（annealing）现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温（亦称「淬炼」，quenching）时，会导致不是最低能态的非晶形。
这里的最低能量状态，也就是我们题目中的最优解
实现
因为要模拟退火的过程，因此我们先定义一些变量
$T$：当前温度，由高温到低温，代表算法进行到了什么程度，一般为double类型
$\Delta T$：每次温度的变化率，一般取$0.95 - 0.99$，模拟缓慢降温的过程(上一次的温度乘温度变换率即为这一次的温度)
$f(x)$ 当前状态对应的值
上面我们提到，模拟退火会以一定的概率转移到比当前差的解，那么这个概率是多少呢？科学家经过分析，当这个概率为$e^{\frac{\Delta f}{T}}$时最优
那么根据退火的过程，我们不难得到模拟退火的算法流程
- 枚举温度$T$
- 计算出下一步的状态
- 若下一步的状态比当前状态优或者满足进行转移的条件，进行转移
- 降温
因为模拟退火算法具有偶然性，因此我们一般需要对一个问题进行多次模拟退火算法
至于温度的设定，以及执行算法次数的确定，这个需要看rp依题目而定
听说模拟退火在计算几何中有非常重要的应用，但是本蒟蒻现在连叉积都不会，所以这一块等以后再补吧
题目
两道很水不错的题目