随机化算法

调整法

调整法的总思路就是，对于当前状态，设法把它转移到邻近的状态（一般调整某个元素的、细微的差距）使得权值更优（或相同，但是要随机转移）。一直重复至超时边缘。

可以见得，调整法重要的是构造转移，构造一个优秀的调整算法。

在比赛中要是碰到 NP 问题的归约又找不到适合的性质时可以使用。

爬山算法

当目前无法直接到达最优解，但是可以判断两个解哪个更优的时候，根据一些反馈信息生成一个新的可能解。通过势升高。

具体地，引入温度参数，温度参数在爬山的时候会不断减小，大概表示了对状态的不确定度。

但是在多峰时会陷入一个小峰。鸡肋，退火启动。

模拟退火

用到了牛顿冷却公式，对转移概率降温。令当前温度为 $T$ ，两个状态的能量差为 $\Delta E$ ，

$$P(\Delta E)= \begin{cases} 1, & \Delta E<0,\\ e^\frac{-\Delta E}{T}, & \text{otherwise}. \end{cases} $$

这表示了接受状态的程度。

至于如何退火，定义初始温度 $T_0$ ，降温系数 $d$ ，终止温度 $T_k$ 。其中 $T_0$ 是一个比较大的数， $d$ 是一个非常接近 $1$ 但是小于 $1$ 的数， $T_k$ 是一个接近 $0$ 的正数。让当前温度 $T=T_0$ ，然后转移，每次 $T=d\cdot T$ 。当 $T<T_k$ 时模拟退火过程结束，当前最优解即为最终的最优解。

注意：我们有时为了使得到的解更有质量，会在模拟退火结束后，以当前温度在得到的解附近多次随机状态，尝试得到更优的解。

偷张图，

参考

邓明扬的论文。

https://oi-wiki.org/misc/hill-climbing

https://oi-wiki.org/misc/simulated-annealing