共计 3011 个字符，预计需要花费 8 分钟才能阅读完成。
导引
少年啊，你是否发现自己的贪心不够优秀？
少年啊，你是否发现自己不会此题的 DP？
少年啊，你是否发现自己对正解毫无头绪？
少年啊，想不想再向上提高自己的分数？
如果你也有以上问题，那就来看看这里吧。
过时的果实——爬山算法
一个很简单的题目类似于这样：
有一个复杂的未知函数 \(f(x)\)，变量 \(x\) 控制它的结果，需要尝试在 \([l, r]\) 上找到它的最大值。
你可能会说：枚举不行吗？
那如果，未知函数 \(f(x)\) 运行超慢？
人类完蛋啦！
其实非也，如果函数图像呈现一个山峰的形状，那就意味着有一种算法相当简单：一直往高处走就好了（也就是尝试将 \(x\) 固定调小和调大一个值（步长），取结果好的那个调整 \(x\)，然后把步长缩小一点点，如此循环）。
不难发现，这样的算法其实相当优秀，只要步长到达一个极小值后结束爬山，自己其实就在山顶了。
但是不难发现它的弊端和限制：
- 如果函数有多个峰谷，极大可能找不到最优解，而是找到了一个局部最优解；
- 很多时候，我们遇到的问题都是多个参数，甚至一个数组的调整。
聪慧的调整——模拟退火
让我们上一点高难度的说法：化步长为 温度。
众所周知，一个物体的 温度 越高，它就越不稳定。
不难发现，爬山算法之所以常会陷入局部最优解，是因为它 只会接受较优解 ，而不会 接受可能对跳出局部最优有帮助的较差解。
那么，解决问题的方法就很简单了：设置一个温度 \(T \in [0, 1)\)，以 \(T\) 的概率接受较差解。
这样的话，一开始就自然而然地学会尝试，之后就慢慢求稳。
但是……步长就不能直接用了吧，毕竟参数可能有好多，调整范围可能较大……
那就——上达尔文的《进化论》！
生物基因发生随机的基因突变，然后被自然选择。
我们已经创建了“自然选择”，“基因突变”如何处理？呵呵 o(*~︶~*)o，答案是——
随机扰动
随机在当前状态改变一点东西，看看结果如何呗，最多就是回退嘛。
那么你将得到：
那么这就很简单了，参考代码如下：
// 随机数生成函数
double rand_double() {
return rand() / (RAND_MAX + 1.0); // [0, 1)
}
double rand_range(double lo, double hi) {
return lo + (hi - lo) * rand_double();
}
double perturb(double v, double T, double vmin, double vmax) { // 随机扰动（不一定要这么写）
double delta = T * (vmax - vmin);
double nv = v + rand_range(-delta, delta);
if (nv < vmin) nv = vmin;
if (nv > vmax) nv = vmax;
return nv;
}
void simulate_annealing() { // 模拟退火
// 初始解
double cur_x = rand_range(X_MIN, X_MAX);
double cur_y = rand_range(Y_MIN, Y_MAX);
double cur_f = f(cur_x, cur_y);
// 答案初始（因为有可能我的最后状态正好随机接受了劣解，所以答案更新和状态更新异步）
ans_x = cur_x; ans_y = cur_y; ans_f = cur_f;
for (double T = 1; T > 1e-7; T *= DELTA) { // DELTA 一般取 0.95 左右，1e-7 也是可以改的
// 随机扰动一下
double nx = perturb(cur_x, T, X_MIN, X_MAX);
double ny = perturb(cur_y, T, Y_MIN, Y_MAX);
double nf = f(nx, ny);
// 是更优解 或 生成随机数看看接不接受劣解
if (nf > cur_f || rand_double() < T) {
cur_x = nx; cur_y = ny; cur_f = nf;
if (cur_f > ans_f) {
ans_x = cur_x; ans_y = cur_y; ans_f = cur_f;
}
}
}
}
C++
随机扰动甚至可以随机交换数组元素等，\(f\) 一般就是把题目给的贡献计算函数翻译成代码。
所以说，这样的退火即为 模拟退火，是很有可能达到全局最优解而不超时的，又可以称为——“优雅的暴力”。
优美的优化——余弦退火
但是，真实考试中计算梯度下降次数太难了，很难具体控制退火几次，此时数学就可以发力了。
目前，我们第 \(i\) 次的温度是：\(\Delta^i\)。
我们发现，其实 \(\cos(x)\) 也符合类似的规律：一开始下降快，后面下降慢。
恭喜你，发明了 余弦退火 ，只需要使用一个优美的数学公式（\(N\) 是 目标迭代次数）：
\[
T_i = T_{min} + \frac{1 – T_{min}}{2}\left(1 + \cos\left(\frac{\pi \cdot i}{N – 1}\right)\right)
\]
看晕了？而 \(T_{min}\) 为 \(0\)，所以 \(T_i\) 是：
\[
T_i = \frac{1}{2}\left(1 + \cos\left(\frac{\pi \cdot i}{N – 1}\right)\right)
\]
因此，模板就成了：
// 随机数生成函数
double rand_double() {
return rand() / (RAND_MAX + 1.0); // [0, 1)
}
double rand_range(double lo, double hi) {
return lo + (hi - lo) * rand_double();
}
double perturb(double v, double T, double vmin, double vmax) { // 随机扰动（不一定要这么写）
double delta = T * (vmax - vmin);
double nv = v + rand_range(-delta, delta);
if (nv < vmin) nv = vmin;
if (nv > vmax) nv = vmax;
return nv;
}
void simulate_annealing() { // 余弦退火
// !!! 没有 T 啦！
// 初始解
double cur_x = rand_range(X_MIN, X_MAX);
double cur_y = rand_range(Y_MIN, Y_MAX);
double cur_f = f(cur_x, cur_y);
// 答案初始（因为有可能我的最后状态正好随机接受了劣解，所以答案更新和状态更新异步）
ans_x = cur_x; ans_y = cur_y; ans_f = cur_f;
// !!! 只从这里改了两行 !!!
for (int i = 0; i < MAX_ITER; i++) { // MAX_ITER 是退火次数
double T = 0.5 * (1.0 + cos(3.1415926 * i / (MAX_ITER - 1)));
// 随机扰动一下
double nx = perturb(cur_x, T, X_MIN, X_MAX);
double ny = perturb(cur_y, T, Y_MIN, Y_MAX);
double nf = f(nx, ny);
// 是更优解 或 生成随机数看看接不接受劣解
if (nf > cur_f || rand_double() < T) {
cur_x = nx; cur_y = ny; cur_f = nf;
if (cur_f > ans_f) {
ans_x = cur_x; ans_y = cur_y; ans_f = cur_f;
}
}
}
}
C++
所以，这就是——退火！
例题
注：模拟退火的题也可以使用余弦退火哦~
进食后人
记得初始化随机种子哦。
