模拟退火

概述

模拟退火（SA）是一种随机化最优化方法，借鉴金属退火过程：温度高时允许大幅、甚至变差的跳动以跳出局部最优，温度降低后逐渐收敛到较优解附近。每步从当前解随机扰动得到新解，算出能量差：更优就接受，否则以指数形式的概率接受劣解；随后按降温系数把温度乘上一个略小于 1 的因子。它适合解空间连续、缺乏明显结构的最优化问题，常配合多次重跑与卡时来提高命中率。例题为洛谷 P1337。

参考资料

• 模拟退火 - OI Wiki

简介

模拟退火（Simulated Annealing，SA）是一种随机化最优化方法，借鉴金属退火：温度高时允许大幅、甚至变差的跳动以跳出局部最优，温度降低后逐渐稳定到更优解附近。

从当前解出发随机扰动得到新解，能量差为 $\Delta E$：若更优则接受，否则以概率 $\exp(-\Delta E/T)$ 接受；随后令温度 $T\gets T\cdot d$（降温系数 $d$ 略小于 $1$）。适合无明显结构、解空间连续的最优化问题。

例题

洛谷 P1337 [JSOI2004] 平衡点 / 吊打XXX

平面上有 $n$ 个点，第 $i$ 个点重 $w_i$。求一点 $P$，使各点到 $P$ 的距离与对应重量之积的总和最小，输出 $P$ 的坐标。