前置知识
自然对数、分数次幂、概率。
前言
模拟退火可以在我们想不到题目正解的时候试一试
其实就是骗分方法。
因为纯随机得出正确答案的概率非常低，所以我们就可以加一定的优化，使找到答案概率增大。
算法思想
温度（步长）：每次选择一个范围进行搜索，在搜索过程中范围不断缩小，最后到很小的时候就可以确定答案。有初始温度、终止温度和衰减系数三个概念。即初始温度 \(T_s\) 不断乘上一个系数最终到终止温度。一般衰减系数为 \((0, 1)\) 之间，一般越接近 \(1\) 越可能找到正确答案。
每次在一个区域内随机选择一个新点 \(v\)，设当前点为 \(u\)，然后将 \(f(u)\) 和 \(f(v)\) 比较，判断是否跳过去或者有概率跳过去。
比如找区间最小值：
假设 \(f(v) - f(u) = \Delta E\)。
如果 \(\Delta E < 0\)，当前点一定不可选，\(u\) 跳到 \(v\)。
否则 \(\Delta E > 0\)，有一定概率跳过去，因为我们要求出全局最小值，如果不跳，可能变成局部最小值，如果 \(\Delta E\) 越小，跳过去的概率越大。一般概率取 \(e^{-\frac{\Delta E}{T}}\)，可以证明这个值在 \(0\sim 1\) 之间。
当 \(\Delta E\) 越来越逼近 \(0\)，那么答案就可能稳定到最优解。
同时，为了降低错误概率，我们要多次执行上述过程，比如 100 次从不同的点开始做。
例题
MyBlog:AcWing 3167 / UVA10228 A Star not a Tree 题解
标签：跳过去,概率,最小值,模拟退火,搜索,答案,Delta,模板 From： https://www.cnblogs.com/Yuan-Jiawei/p/18315345