模拟退火

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

基本原理

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

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

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

先放一张图感性理解一下

有一个比较有趣的比喻

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

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

算法过程

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

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

摘自维基百科

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

公式即为

\[ p_i = \frac{1}{Q} e^{\frac{-\epsilon_i}{kT}} \]

此处 \(p_i\) 是状态 \(i\) 的概率，\(\epsilon_i\) 为状态 \(i\) 的能量，\(k\) 为 Boltzmann 常数，\(T\) 为温度

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

1953 年 Metropolis 提出了这样一个重要性采样的方法，即设从当前状态 \(i\) 生成新状态 \(j\)，若新状态的内能小于状态 \(i\) 的内能，即 \(E_j<E_i\)，则接受新状态 \(j\) 作为新的当前状态；否则，以概率 \(\exp(\frac{-(E_j-E_i)}{kT})\) 接受状态 \(j\)，其中 \(k\) 为 Boltzmann 常数。

上面的概率公式中 \(\exp\) 即 \(e\) 的指数函数，同时两个状态能量的差 \(E_j - E_i\) 可以表示为 \(\Delta E\)，则可以写出一个（我）更容易理解的表达方式，即

\[ p_j = e^\frac{-\Delta E}{kT} \]

总的来说，概率 \(p_{new}\) 可以表示为

\[ p_{new} = \begin{cases} 1, & \text{if } \operatorname{E}(x_{new}) < \operatorname{E}(x_{old}) \newline e^\frac{-\Delta E}{kT} & \text{if } \operatorname{E}(x_{new}) \geqslant \operatorname{E}(x_{old}) \end{cases} \]

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

例题

[TJOI2010]分金币

题目描述

现在有 \(n\) 枚金币，它们可能会有不同的价值，第 \(i\) 枚金币的价值为 \(v_i\)。

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

输入格式

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

输入的第一行是一个正整数 \(T\)，表示该测试点内数据组数。

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

每组测试数据占两行。

第一行是一个整数 \(n\)，表示金币的个数。

第二行有 \(n\) 个整数，第 \(i\) 个整数表示第 \(i\) 个金币的价值 \(v_i\)。

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
5

2
3
2 2 4
4
1 2 3 6

样例输出 #1

1
2

0
2

提示

数据规模与约定

• 对 \(30\%\) 的数据，保证 \(1 \leq v_i \leq 1000\)
• 对于 \(100\%\) 的数据，保证 \(1 \leq T \leq 20\)，\(1 \leq n \leq 30\)，\(1 \leq v_i \leq 2^{30}\)。

TODO