模拟退火与爬山法

通过向 chatGPT-4o-mini 提问，我注意到所有爬山法可以解决的问题模拟退火都可以解决，所以爬山法死了我不想学爬山法。

具体的，对于一个多峰函数求解最值的题目都可以用模拟退火来做。

如果现在在较优解 \(x\)，发现了一个新的解 \(x'\)，如果 \(x'\) 比 \(x\) 优那么 \(x\gets x'\) 否则有一定概率接受 \(x'\)，这就是模拟退火的核心思想。

考虑 \(x'\) 没有 \(x\) 优秀的概率是怎么计算的：

令 \(\Delta x=x-x'\)，那么我们就有 \(e^{\frac{\Delta x}{T}}\) 的概率更新 \(x\)，其中 \(T\) 是当前的温度。在进行了一次操作之后就进行降温操作，即 \(T\gets T\times 0.999\)。

下面的内容很重要！！！！！！

我们令新算出的结果为 \(f\)，原本的答案为 \(lst\)。

对于求解最小值的问题，取 \(\Delta=f-lst\)，那么：

• 如果 \(\Delta<0\)，那么就直接接受。
• 否则如果 exp(-del/t)>Rand()，那么接受。

对于求解最小值的问题，一样取 \(\Delta=f-lst\)，那么：

• 如果 \(\Delta>0\)，那么就直接接受。
• 否则如果 exp(del/t)>Rand()，那么接受。

需要注意的是 exp(x)\(=e^x\)，其中 \(x\) 就是自然函数，其图像如下：

发现对于 \(x>0\) 的情况 epx(x) 始终大于 \(1\)，这个概率就是没有意义的，所以 \(\Delta\) 的值一定是负数才有意义。

所以上面的公式在 epx 中是取 del 还是 -del 就十分好理解了，所以这并不需要死记硬背。

形象的，放一张从 OI-Wiki 偷的图：

JSOI2004 平衡点 / 吊打XXX

练手题，但是题目太困难了，考虑给一个形式化题意：

找到一个 \((x,y)\) 使 \(\sum\limits_{i=1}^n dis((X_i,Y_i),(x,y))\times Weight_i\) 最小，输出 \(x,y\)（可以是小数），其中 \(1\le n\le 1000\)。

就是模板，按照上面的思路写就行了。

AHOI2014/JSOI2014 保龄球

考虑每一次随机交换 \(x,y\) 的位置，跑模拟退火就行了。

JSOI2016 炸弹攻击

直接随机放炸弹的位置，因为函数长得奇丑无比所以要求扰动的范围较大，生成的时候需要使用：

double xx=(rand()*2-RAND_MAX)*t+x;

而不是：

double xx=(2.0*rand()/RAND_MAX-1)*t+x;

HAOI2006 均分数据

考虑先随机分组，然后模拟退火随机改变一个元素的分组就行了。

JSOI2008 球形空间产生器

设一个变量 \(r\)，表示这个高维球体的半径，由公式 \(r=\sqrt{\sum_{i=1}^n(a_i-b_i)^2}\) 可得 \(\sum_{i=1}^n(a_i-b_i)^2= r^2\)，其中 \(a_i\) 是高维球面上某一个点的坐标，\(b_i\) 是球心的坐标。

化简得：

\[\sum_{i=1}^n({a_i}^2-2a_ib_i+{b_i}^2)=r^2 \]

移项得：

\[\sum_{i=1}^n(-2a_ib_i)+\sum_{i=1}^n{b_i}^2-r^2=\sum_{i=1}^n({-a_i}^2) \]

其中 \(\sum_{i=1}^n{b_i}^2-r^2\) 与球面上的点无关，因此我们可以将其看做一个系数为 \(1\) 的变量，右边是常量。