模拟退火

模拟退火不是模拟题意，也不会让你退火（可能会让你上火），顾名思义，这个算法模拟的是“退火” 的过程。

基本原理

退火即晶体冷却的过程，将一个物体加热到一定温度后使其逐渐降温。而在物理中，物体内能越高，其粒子随机运动就更剧烈，状态也就越不稳定。物体温度高时，状态最不稳定。使降温，粒子运动变慢，状态就趋于稳定。当降温速度过快，会导致粒子来不及排列成稳定的原有的结构，从而形成能量高不稳定的非晶体。相对的，如果降温速度足够慢，粒子会渐趋有序，直至内能减为最小，此时物体呈现为晶体。

上面两段所说的“非晶体”可以看作“局部最优解”，而变回原有结构的晶体则可以看作“最优解”。

大体来说，模拟退火就是随机跳解，接受更优的解，同时为了防止局部最优解的陷阱，概率性接受不优的解，后者相当于物理过程中粒子的随机跳动，它带来了晶体降温结果的随机性。而跳随机解的次数多少，则相当于降温的速度，降温的速度越慢，晶体回到原有结构的可能性更高，也就相当于跳解的次数越多，跑出最优解的可能性更高。

先放一张图感性理解一下

有一个比较有趣的比喻

爬山算法：一个兔子从一个点往高爬，爬到了一个山顶，但是不知道这个山顶是不是珠穆朗玛峰
模拟退火：一个兔子喝醉了乱跳，跳到了某个山顶也要继续跳到别的山坡，但是它逐渐清醒，向最高点跳去

感性理解后我们详细讲解一下算法过程。

算法过程

设定好“初始解”，“初始温度”与“下降速度”，每一次“降温”都得到一个新解，于是出现两种情况，即新解优于旧解或不优于旧解。优于旧解显然是要接受的，但是只接受优解可能只能找到局部最优，与爬山算法无异，因而我们对于一个不优的解还需要进一步处理。

而这一步处理（可能是）模拟退火的精髓所在，是把这个随机化算法和热力学/统计力学等连接起来的部分，即接受这个不优解的概率。

摘自维基百科

玻尔兹曼分布是状态能量与系统温度的概率分布函数，给出了粒子处于特定状态下的概率

公式即为

$𝑝 𝑖 = 1 𝑄 𝑒 - 𝜖 𝑖 𝑘 𝑇$

此处 $𝑝 𝑖$ 是状态 $𝑖$ 的概率， $𝜖 𝑖$ 为状态 $𝑖$ 的能量， $𝑘$ 为 Boltzmann 常数， $𝑇$ 为温度

啊当然这个并不是我们接下来需要用到的准则，只是引入一个热力学常量，即 Boltzmann 常数。同时下面的准则很大程度基于上面的玻尔兹曼分布（可能是，我目测的

1953 年 Metropolis 提出了这样一个重要性采样的方法，即设从当前状态 $𝑖$ 生成新状态 $𝑗$ ，若新状态的内能小于状态 $𝑖$ 的内能，即 $𝐸 𝑗 < 𝐸 𝑖$ ，则接受新状态 $𝑗$ 作为新的当前状态；否则，以概率 $e x p (- (𝐸 𝑗 - 𝐸 𝑖) 𝑘 𝑇)$ 接受状态 $𝑗$ ，其中 $𝑘$ 为 Boltzmann 常数。

上面的概率公式中 $e x p$ 即 $𝑒$ 的指数函数，同时两个状态能量的差 $𝐸 𝑗 - 𝐸 𝑖$ 可以表示为 $Δ 𝐸$ ，则可以写出一个（我）更容易理解的表达方式，即

$𝑝 𝑗 = 𝑒 - Δ 𝐸 𝑘 𝑇$

总的来说，概率 $𝑝 𝑛 𝑒 𝑤$ 可以表示为

$𝑝 𝑛 𝑒 𝑤 = {1, i f E (𝑥 𝑛 𝑒 𝑤) < E (𝑥 𝑜 𝑙 𝑑) 𝑒 - Δ 𝐸 𝑘 𝑇 i f E (𝑥 𝑛 𝑒 𝑤) ⩾ E (𝑥 𝑜 𝑙 𝑑)$

概率处理完了，主要算法部分也基本上结束了，下面我们引入一道例题。

例题

[TJOI2010]分金币

题目描述

现在有 $𝑛$ 枚金币，它们可能会有不同的价值，第 $𝑖$ 枚金币的价值为 $𝑣 𝑖$ 。

现在要把它们分成两部分，要求这两部分金币数目之差不超过 $1$ ，问这样分成的两部分金币的价值之差最小是多少？

输入格式

本题单个测试点内有多组测试数据。

输入的第一行是一个正整数 $𝑇$ ，表示该测试点内数据组数。

对于每组测试数据的格式为：

每组测试数据占两行。

第一行是一个整数 $𝑛$ ，表示金币的个数。

第二行有 $𝑛$ 个整数，第 $𝑖$ 个整数表示第 $𝑖$ 个金币的价值 $𝑣 𝑖$ 。

输出格式

对于每组数据输出一行一个整数表示答案。

样例 #1

样例输入 #1

复制

样例输出 #1

1
2

0
2

复制

提示

数据规模与约定

对 $30 %$ 的数据，保证 $1 \leq 𝑣 𝑖 \leq 1000$
对于 $100 %$ 的数据，保证 $1 \leq 𝑇 \leq 20$ ， $1 \leq 𝑛 \leq 30$ ， $1 \leq 𝑣 𝑖 \leq 230$ 。

TODO

本文采用 GNU 自由文档许可证许可协议，转载请注明出处。