模拟退火

参考资料

• 模拟退火 - 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$ 的坐标。