模拟退火，将净化一切 :qp:
模拟退火 simulateAnneal ( 期末特刊 )
前言
模拟退火是一个基于 随机化和物理 的，『非常乱来』的算法，
一般用于 答案最优化 / 点集划分 / 分配权值 / 输出方案 问题.
在数据规模较小时，几乎不可能拦住这个算法成功乱搞，
但是如果根据正解，刻意扩大数据范围到大约 $10^5$ 的量级，那么这个算法往往无法通过.
由于模拟退火只是一种迭代求解的想法，并非特定领域的算法，
因此在数学、图论、dp、计算几何等题目中都有很亮眼的表现.
模拟退火本质和爆搜是一样的，只不过用一个热力学 + 统计学方法优化了一下，就有一点强了
由于做法基本上就是瞎搞，这个算法非常轻松搞笑，理解成本很低，很适合在期末周进行学习.
简单介绍
爬、山
考虑一个很多山峰的函数 $f$，如果你从左往右跑 ($x$ 递增)，每次间隔一点步长 $d$，
就可以在这些点值里找到一个 “极值”，也就是 $\max { f(x + id) }$
但是这个东西显然不能真的就是函数的极值。
换个角度，如果你在找到一个较大值 $f(x_1)$ 以后，不再采用后续的较小值 $f(x_2)$
也就是出现了 $x_1 < x_2, f(x_1) > f(x_2)$
那么你可以在 $x_1$ 前后 震荡，一定可以找到目前这个较大值所在的那个山峰极值，这下确实是局部的极值了。
不过这个山峰极值，是否 真的是最高的那个，我们也说不清。
摸你、退火
伟大的物理学告诉我们，我们模拟一个系统熵减(?)的过程，居然能概率得到良的近似解.
具体来说是这样的，上面那段有个加粗的 震荡，
实际上只要我们 震荡 足够离谱，那么确实可以离开自己的这个山峰，跳到隔壁山峰上
模拟退火模拟的是温度下降的过程，温度越高，震荡 越离谱，否则只会小幅度地扰动.
我们希望一开始通过剧烈的 震荡，抵达一个最高峰附近，接下来随着温度降低，降低 震荡 幅度.
事实证明，这个做法是靠谱的.
不过有个问题就是，假如我们跳到隔壁山峰上的点 $x_3$，可能还是有 $f(x_1) > f(x_3)$，也就是依然不优，怎么办呢?
模拟退火给了我们一个神秘的，概率上比较对的，很物理的，怪东西
假设历史最优答案为 $(x,f(x))$，目前 震荡 (应用一个 随机增量) 后的答案为 $(y,f(y))$，
以下为是否选取 $y$ 作为答案的概率
(这个也渲染不出来)
\begin{cases}
1,&\qquad f(y) \gt f(x)\ 答案更优，必然更新答案为 (y, f(y))\
e^{-\Delta / t} > Rand(),&\qquad 如果不优，概率更新答案为 (y, f(y)) \end{cases}
主要关注后者，它以一定概率接受一个不优的解，以便你跳到隔壁山峰上.
其中
- $\Delta$ 永远定义为 $f(y) – f(x)$ ( 这个$f$ 可以是你自己的估价函数 )，
- 你需要保证指数位置上的 $\frac{-\Delta}{t}$ 是负数，也就是说，这个负号是可以人为增减的
- 随机数 $Rand() \in [0,1]$
- $t$ 表示目前的温度，下面解释这个温度
为了模拟降温，我们需要设置一个初温 $T = 10^5$，降温速度 $\delta = 0.97$，目前温度为 $t = T$，温度下限为 $0.001$
这个参数可以自己调。
t = T = 100000;
ans // 目前答案 f(x)
ans_x // 答案对应的 x
while( t > 0.001 ) {
int y = x + t * random() // 振动幅度是根据温度大小 t 来的
int newAns = f(y); // 求解 f(y)
int delta = newAns - ans; // Δ = f(y) - f(x), 这是定义
if( newAns > ans ) // 更好就接受
accept_and_update();
else if (exp(delta / t) > Rand()) // 否则有概率接受
accept_and_update();
t *= 0.97; // 每次降温 就乘一下这个 δ
}
这样，我们的算法就基本完成了。
由于 有概率接受 部分 exp(delta / t) > Rand() 真的只负责 有概率接受，往上抄就行了
所以你为了完成算法，你必须再实现两个东西
- 估价函数 $f(x)$
这个东西有时候是题目给你的，好比说让你求 $f(x)$ 极小值，以及对应的 $x$
给了的话直接求就行，否则需要自己定义一个合适的. - 更好就接受 : 要能比较估价函数 $f(x), f(y)$ 哪个状态更优
比如说，求函数最小值，那么当 $f(y) \lt f(x)$ 时，认为 $y$ 优于 $x$
但是换一个问题的话，你需要有一个固定的标准去选择是否采纳
解决这两个东西以后，模拟退火就搞定了，我们来看一些具体的例子.
题目™
每题会根据 正解 给出难度，分为：签到题、铜牌题、银牌题、金牌题、出线题
但是如果你使用模拟退火做这些题，它们的难度大概全是 铜牌题。
题目选择的标准是，在使用模拟退火的情况下，依然有一定的思维量，或者是较为有趣的题目.
因此并不是所有题目都值得去写，但它们的做法应该值得一看，值得大家留下一些思考或印象.
Lev OJ P1234 猜谜大师 $\quad$ [ 签到题 ]
题意: 给定一区间 $[L,R]$，某个函数 $f(x)$ 在区间上连续，求区间内的一个 $x$，
使得 $f(x) = 0$，不保证有解，多解可以输出任一解，精度 $10^{-6}$
我们的目标是使得函数值为 $0$，那么距离 $0$ 越远，我们认为它越劣
所以显然可以得到一个估价函数为 $calc(x) := abs(f(x))$
模拟退火的过程如下 (伪代码):
funciton simulateAnneal() {
double t = T = 1e5, ans_x = nxt_x = L;
while ( t > 0.001 ) {
double nxt_x = ans_x + t * rnd()
// rnd() ∈ [-1, 1]，根据目前温度进行随机扰动
nxt_x = max(L, min( nxt_x, R ) );
// 题目要求 x 在 [L, R] 内，扰动后不能越界
double now_val = calc(ans_x);
double nxt_val = calc(nxt_x);
double delta = nxt_val - now_val; // 就这么定义的
if( nxt_val < now_val ) // 更好就接受(这里'更好'的定义是越接近 0 越好，所以是小于号)
ans_x = nxt_x;
else if (exp(-delta / t) > Rand()) // 否则有概率接受不优的解
ans_x = nxt_x;
t *= 0.97;
}
}
参数是可以调的，我们这里的初温 1e5，末温大约是 1e-3，也就是 1e8 的范围，
$$\log_{\frac{1}{0.97}} 1e8 = 605$$
也就是每次调用 simulateAnneal() 会大概进行 $600$ 次运算，
以及在本题中，估价函数 $calc()$ 是 $O(1)$ 的，这也是模拟退火需要关注的
由于一轮退火可能无法得到正确答案 (可能得到局部最优解，或者是精度要求没有到)
所以我们可以多退火几次
itn mian() {
for( i = 1 ; i <= 1000 ; i++ )
simulateAnneal();
retu 0;
}
每轮初始化的时候，记得初始化为目前的最优解.
本题解决的是：
单点值 x
最优值 f(x)，条件极值
求解过程: 随机震荡
$\bold { \color{red}weak : }$ 本题中，模拟退火弱于数值方法
模拟退火很难在 $50$ ms 内求出符合精度要求的解，针对问题，使用好的数值方法可以快速得到高精度解
P1337 [JSOI2004] 平衡点 / 吊打XXX $\quad$ [ 签到 / 铜牌题 ]
https://www.luogu.com.cn/problem/P1337
题意: 给你一个二维平面桌子，桌面上方有一个绳结，桌子上有很多小洞，下面挂着不同重量的重物，
求绳结最后停在二维平面的哪里，输出坐标，精度 $10^{-3}$
桌面 $20000 * 20000 $，重物数量为 $10^3$
本题是退火典题之一，题面可以进一步简化为几个字，『 求带权费马点 』
很容易想到模拟退火，由于平面不太大，可以继续使用上一题的 随机增量 方案，
对绳结的 $x,y$ 都应用一个和温度有关的 震荡 幅度即可，随后验证是否更接近平衡状态
本题还有另外一种 随机增量 方式
当你选择了一个点以后，每个重物对你这个点施加的向量是确定的
他们最后的合力方向也是可以知道的，所以可以往那个合力方向做 随机增量
由于末状态是稳定的，合力为 0，估价函数可以选择为 合力的模
此外，不难发现这个 『 求带权费马点 』 问题是一个单峰函数，所以一种正解是直接三分套三分就行
本题解决的是：
单点值 x
最优值 f(x)，条件极值
求解过程: 随机震荡 / 利用特殊性质
$\bold { \color{red}weak : }$ 本题中，模拟退火严格弱于三分套三分
后者可以在 $O(n\log^2V)$ 时间内求出极高精度解，严格强于模拟退火
P4035 [JSOI2008] 球形空间产生器 $\quad$ [ 银牌题 ]
https://www.luogu.com.cn/problem/P4035
题意: 给你一个 $10$ 维空间上的 $11$ 个点，保证它们在一个 $10$ 维球面上，输出球心坐标.
精度 $10^{-3}$
存在高斯消元做法，具体做法是得到一个 $n$ 元高次方程组，通过作差变成一组 1次方程组，
可是，我们是乱搞爱好者.
我们可以瞎选一个球心，然后得到和其他点的距离，以及距离的平均值
不难发现，最后的平衡状态一定是距离很接近距离平均值的，
那么，对于每个点，如果当前状态距离比平均值远，我们就往那个点拉，否则就往反方向推
这个想法非常有趣，因为是从末状态的特征来考虑的，正确性往往是有保证的
和前面那题类似，可以说是一种好的退火策略。
估价函数我们也可以继续用这个想法，末状态下，所有距离与平均值之差为 $0$
所以我们选择 $calc := \sum abs($ 距离与平均值之差 $)$
洛谷有的题解说可能精度不够，这只能说明菜，我们后面说明怎么搞定精度.
本题解决的是：
单点值 x
最优值 f(x)，条件极值
求解过程: 特殊性质
$\bold { \color{red}Weak : }$ 本题中，模拟退火弱于高斯消元，
高斯消元由于 $O(n^3)$ 的复杂度，可以做到 $n=1000$，模拟退火不能快速计算估值函数
2023 CCPC 哈尔滨 H. Energy Distribution $\quad$ [ 金牌题 ]
https://codeforces.com/gym/104813/problem/H
题意: 无向图，点数 $n=10$ 的团，边权 $0 \le w_{i,j} \le 1000$,
给每个点分配 非负点权 $e_i$，满足 $ \sum e_i = 1$
最大化 $\sum_{i=1}^n { \sum_{j=i+1}^n e_i \times e_j \times w_{i,j} }$ (式子相当于枚举边)
输出最大值，精度 $10^{-6}$.
存在高斯消元做法，$O(2^n)$ 枚举点权为 $0$ 的点，其余点的梯度必须一样，$O(n^3)$ 高斯消元，
记得舍去负值，总复杂度 $O(2^n n^3)$
那数学不好，想不出金牌题怎么办？我们是乱搞爱好者.
初始状态，先用边权给每个点加权，然后把 $1$ 按加权分给每个点.
这是一种 贪心方法，只不过是错的，但是很适合作为初始状态.
此外，贪心方法 也可以作为退火过程的方案，我们后面会见到.
每次暴力选两个下标，然后 按比例$\Delta$ 修改权值
$\Delta = \frac{t}{T} * rnd$，$rnd \in [-1,1]$
为了防止精度爆炸，每次更新完要按比例重构一下点权，让他们加起来还是 $1$
然后我们普通退火更新答案就行
由于本题在退火过程中没有什么好的性质便于更新，
在退火结束后，用最后的温度 $t$ 继续进行 100 – 500 组随机扰动，
同时更新答案，可以大大提高 AC 率，这就是防止精度不够的好办法 (必然 $10^{-5}$ )
有一点很重要，注意到最初加权为 $0$ 的点一定不会被分配到点权，
直接把他们从随机选择的下标里丢掉，否则会被退火得到点权，很难跳出来，对精度影响比较大
我想这个也是 模拟退火 的魅力
前面的题目，我们通过物理知识，知道可以在某个合力方向扰动
这题我们通过肉眼观察，手动剪枝，提高退火精度
精度比较看运气，$10^{-5}$ 到 $10^{-8}$ 都可能出现，
以及要说的是，精度要求 $10^{-8}$ 的题，退火也是可做的，只要时长给 $4s$ 以上
本题解决的是：
多点值 x1 … xn
多元函数最优值 f(x1, … , xn)，条件极值
在有限制的情况下分配点值
高精度要求
求解过程: 随机震荡
可以说，这个题，相较于前面的几题，是大大强化了模拟退火的
$\bold { \color{green}Win : }$ 本题中，模拟退火强于正解（枚举子集 + 高斯消元）
模拟退火可以轻松解决 $n=50$ 至 $ 100$ 的数据范围，
然而正解的复杂度高达 $O(2^n n^3)$，只能做到 $n=20$
P5544 [JSOI2016] 炸弹攻击1 $\quad$ [ 出线题 ]
https://www.luogu.com.cn/problem/P5544
题意: 二维平面 $20000 * 20000$，上面有 $n = 20$ 个不同半径的圆 (建筑)，有 $ m = 1000$ 个点 (敌人)
你有一个圆 (炸弹)，爆炸半径可以自己调为 $[0,R]$，不能炸到建筑，可以相切
最大化: 炸到的敌人数
正解 是计算几何，做法很复杂，离散化扫描，角前缀和，然后转转转，和二分，可能需要适当分类讨论
但 模拟退火 就很简单，首先随便选一个点，然后求出 $\min($ 和建筑$_i$ 相切的距离，$R\ )$
这是可以选到的最大半径，接下来你算出这个半径下覆盖了多少敌人，这就是估价函数。
接下来对圆心坐标做随机增量即可。
注意到平面还是有点大，估价函数可能一直是 $0$ ，导致乱跑，有两种解决方法:
1. 分割平面为 16 (?) 块，每个里面单独退火，保证圆心在那个块内即可
2. 优化估价函数
一种优化估价函数是 $ calc := kill + C \times dis$
$kill$ 是击杀数，$C$ 是一个常数，$dis$ 表示最近的敌人距离自己多远
这个估价函数是平滑的，且效果很好.
本题解决的是：
最优化问题
分割问题规模 / 优化估价函数
求解过程: 随机震荡
$\bold { \color{royalblue}Tie : }$ 模拟退火弱于计算几何做法，但是就比赛而言无法决出高下
计算几何的正解达到了 $\color{#0e1d69} \mathbf{ NOI/NOI+/CTSC }$ 难度，思维难度和花费的时间非常高昂。
而模拟退火由于简单好写，代码量短，思维量相对少，写的时候也很难出现错误，
同时，正解具有一定常数，如果题目因此给出 $5$ 秒时限，模拟退火依然可以通过.
小姿势
根据一些观察，模拟退火是一个 马尔可夫过程
存在严格证明：当温度下降十分缓慢，而在每个温度都有足够多次的状态转移，则 全局最优解将以概率 $1$ 被找到.
这告诉我们：如果降温够慢，这个算法的正确性是 $100\%$
笔者总结一下自己的经验
- 反复多轮退火的原因是，我们有时候一轮退火没法得到最优解，或者精度要求没有达到
这对耗时的影响是乘数的 -
如果修改退温速度，比如说 $\delta = 0.97 \rightarrow 0.993$ (这也是一个常用的参数)
这对耗时的影响是指数的，$\log_{ 1/0.97 } 10^8 = 600$ 而 $ \log_{ 1/0.993 } 10^8 = 2622$
前文给出的参数($T_r = 10^8，\delta = 0.97$)，退火一轮很可能跑不到 20ms
有些时候，选择让一轮退火跑 500ms，也是可以同样达到多轮退火效果的，主要看实际情况
比如说，估价函数存在缺陷 (比如前面那个丢炸弹)，把退温时间交给多轮退火是相对更理想的
但在其他时候，让降温速度变慢往往是用于提高精度的
也可以选择先正常退温，最后在温度较低的地方以较慢的降温速度进行退火
稍微降点强度，看点集划分类型的退火
P3878 [TJOI2010] 分金币 $\quad$ [ 签到题 ]
https://www.luogu.com.cn/problem/P3878
题意: $n \le 30$ 个价值不同的金币，分成两堆，堆内数量最多差 $1$，
最小化: 两堆价值之差
做法比较多，爆搜剪枝，折半 dp，或者随便乱搞也能过
这里说模拟退火做法:
由于两堆的数量是确定的，所以可以初始随机分配，然后随机交换两堆里的金币即可
估价函数 $calc :=$ $abs ($ 价值之差 $)$
本题解决的是：
类似 2sat 的点集划分
最优值 f(x)，条件极值
求解过程: 随机震荡
$\bold { \color{green}Win : }$ 作为一道乱搞/搜索题，就码量、实现细节、逻辑连续性而言，模拟退火又简单又好写
本题搜索方法非常复杂，需要各种剪枝。模拟退火赢嘛了。
P2503 [HAOI2006] 均分数据 $\quad$ [ 签到题 ]
https://www.luogu.com.cn/problem/P2503
题意: $n \le 20$ 个价值不同的金币，分成 $m \le 10$ 堆，
最小化: 每堆价值之和 的均方差
容易想到一种 贪心方法，每次把金币放入目前价值最小的一堆，很容易证明是假的
所以你可以随机打乱序列，每次都跑一下，概率是对的。
模拟退火，狗都不写。
我是人，我不是狗，那模拟退火怎么写呢？
依然每次选择两个不同的金币，交换即可，呵呵。
怎么确定某个金币分在哪堆里呢？直接用 贪心方法 分堆即可。
估价函数直接选择 均方差 即可。
本题解决的是：
点集划分
最优值 f(x)，条件极值
求解过程: 随机震荡
$\bold { \color{green}Win : }$ 本题搜索方法非常复杂，需要各种剪枝。模拟退火赢嘛了。
P2538 [SCOI2008] 城堡 $\quad$ [ 金牌题 ]
https://www.luogu.com.cn/problem/P2538
题意: 给你一个无向图，保证是基环树森林，有 $V=E=50$，有边权
目前有一些点上面建造了城堡，你可以再建造 $k$ 个，
最小化: 每个点到最近城堡的距离的最大值
正解是 dp，算是一个典题的加强版，略显复杂，所以必须大力乱搞，否则无法体现本题难度。
先随便选 $k$ 个点，然后每次从造了城堡和没造的里面找一个点随机交换即可，计算答案只需要跑最短路即可
由于是一个基环树，大力 spfa / dijkastra 都是可以的
实际上，这部分暴力最短路还存在一个优化 trick:
在 $n$ 个点中有 $m$ 个特殊点，求剩下 $n−m$ 个点到这些特殊点最短路最大值
- 对于有向图，我们建出反图，再建立虚点链接 $m$ 个特殊点，
从虚点跑一次单源最短路，得到的最短路最大值即为答案； - 对于无向图，省去建反图的操作，其余相同。
$\bold { \color{red}Weak : }$ 正解是 $O(n\log^2n)$
但是模拟退火对思维量实在是太降维打击了
点集划分类似物
图论
优化实现
P3959 [NOIP2017 提高组] 宝藏 $\quad$ [ 银牌题 ]
https://www.luogu.com.cn/problem/P3959
题意: 无向图，$V= 12$，$E \le V^2$，有边权.
你可以选一个点作为根，建立一颗生成树，生成树的边权为: 原始边权 * 到根的节点数
最小化: 生成树的总边权和
正解是 dp，可以状压.
主要考虑怎么退火，由于每个根造成的答案都可能不一样，所以先枚举根，然后对每个根的树进行退火.
由于这题没有性质，只能乱换，有点悬
可以用 贪心方法 跑一下初始状态，先分别求出 最小生成树 & bfs 可以得到的两个答案，从他们开始跑
退火过程肯定是加边然后断边，但是想想的话，实现起来还是有点麻烦的
实际上也存在着比较好的实现方式，具体来说就是：
随机选择一个节点，断掉它和父亲的边，再和一个随机父亲连
这部分需要记录父亲以及利用邻接表，还是比较有趣的想法
$\bold { \color{green}Win : }$ 本题有多种做法，爆搜剪枝、模拟退火、状压 DP $O(n3^n)$ 都可以通过，
就实际效果而言，模拟退火表现较好，也可以应付稍微大一点的数据范围
点集划分类似物
图论
优化实现
P4044 [AHOI2014/JSOI2014] 保龄球 $\quad$ [ 铜牌题 ]（但是挺诈骗的，可能会变成金牌区的题目）
https://www.luogu.com.cn/problem/P4044
题意: 有 $n = 50$ 轮保龄球比赛，根据规则，每轮丢两个球 (a,b)，每击倒一个瓶子，积分++。
在每轮中:
* 如果第一个球击倒 10 个瓶子，下一轮丢的两个球，积分都翻倍
* 第一个球没有击倒 10 个，但是第二个球补到了 10 个，下一轮第一个球的积分翻倍
* 合起来没击倒 10 个，依然记算这轮积分，只不过下一轮没有翻倍
特别地，如果最后一轮，一发全灭，会有第 $n+1$ 轮，由于上述规则，$n+1$ 轮的积分是全部翻倍的
现在给出 $n+1$ 个 (a+b)，你可以重排他们，最大化积分
不是，这个看起来很像 dp 吗，怎么感觉不可做的。
所以大力乱搞实现 AC 自由。
模拟退火的不等式(?)：随机交换下标，秒了，
记得每次特判是否存在最后一轮的贡献即可
$\bold { \color{green}Win : }$ 本题目前只有模拟退火的解。
究其原因就是 $n!$ 的状态数以及复杂的贡献计算方法，连爆搜+疯狂剪枝都望而却步了
序列、调度安排类似物
如果写一下这题，会发现，每次计算答案的时候，
如果暴力是 $O(n)$ 的，但是如果只计算增量是可以做到 $O(1)$ 的
这有时候是一个 重要的优化，因为时间多了可以用来 增加精度 / 保证正确，来看一个具体题目.
P4360 [CEOI2004] 锯木厂选址 $\quad$ [ 银牌题 / 金牌题 ]
https://www.luogu.com.cn/problem/P4360
题意: 整数点的线段，值域 $2e9$，上面有 $ n = 20000$ 棵树，每棵树有一个重量 $w$，
线段最右侧有一个伐木场，所有树都要运往伐木场，花费为 距离 * 重量，树只能往右边运
为了减少费用，你可以把两颗树替换成伐木场，也就是可以有 $3$ 个伐木场
最小化: 花费
本题存在一定的思维量，可以先不看题解，思考一下如何模拟退火
正解：斜率优化 dp 的典题，所以我们必须立刻乱搞。
乍一看还是比较简单，随机换一个伐木场的位置就行，问题是现在算一次答案，
复杂度是 $O(n)$ 的，而这个 $n$ 太大了，对退火次数影响很大，很影响正确率
所以可以推式子，假设建在 $a,b$ 处，令 $dis(i,j):=$ 两颗树的距离
贡献当然是拆成三段的
$$
ans = \sum_1^a w_i * dis(i,a) + \sum_{a+1}^b w_i * dis(i,b) + \sum_{b+1}^n w_i *dis(i,n)
$$
然后我们改写一下 $dis(i,j)$，变成前缀的差分 $D_j – D_i$
$$
ans = \sum_1^a w_i * (D_a-D_i) + \sum_{a+1}^b w_i * (D_b-D_i) + \sum_{b+1}^n w_i *(D_n-D_i)
$$
看这括号，就很有展开的欲望
$$
ans = D_a * \sum_1^a w_i * + D_b * \sum_{a+1}^b w_i + D_n * \sum_{b+1}^n w_i \
-\sum_1^a w_i * D_i – \sum_{a+1}^b w_i * D_i – \sum_{b+1}^n w_i * D_i
$$
合并
$$
ans = D_a * \sum_1^a w_i * + D_b * \sum_{a+1}^b w_i + D_n * \sum_{b+1}^n w_i – \sum_1^n w_i * D_i
$$
可以预处理前三项中的 $W_a = \sum_1^a w_i$ 以及最后一项 $S = \sum_1^n w_i * D_i$
$$
ans = D_a * W_a + D_b * (W_b – W_a) + D_n * (W_n – W_b) – S
$$
就可以 $O(1)$ 了，这样代数运算次数降低至少 $10000$ 倍，你可以狂暴退火 $114514$ 次
$\bold { \color{red}Weak : }$ 正解通过斜率优化实现了 $O(n)$ ，如果数据范围提高到 $5*10^6$，模拟退火将会去世。
本题解决的是：
优化退火过程，变相提高精度和正确性
序列、调度安排类似物
BZOJ 2832 宅男小C
题意: 你有 $M$ 块钱，每次点外卖要花 $F$ 外送费.
餐厅会提供 $n = 200$ 种食物，每种食物都可以吃一整天，但是价格为 $p_i$，保质期为 $S_i$ 天.
一次外卖可以装无限个食物，而你一天不吃饭就会死。 $1\le M,F,p,S \le 10^{18}$
最大化: 活着的时间
考虑枚举购买外卖的次数，
- 买的次数很少，由于保质期问题，死的太早
- 买的次数很多，由于存在外送费，死的太早
可以猜到是一个两边低，中间高的函数，但不确定能否三分，实际上也是不能直接三分的，必须需要一些复杂数学结论才行
那为何不大力退火。
注意到，每个食物都可以续一天，那我们肯定先买便宜的，直到某种食物的保质期都用满了，再换后面的。
而后面的必须保质期更长，否则没有购买的必要。
因此，我们可以得到一种最优策略，在每次外卖中，依照一种顺序购买，使得 $p_i$ 和 $s_i$ 同时递增 (不降).
我们先让每次购买都选一样的商品（越靠前的食物越优，买一样的是 ok 的），这可以通过二分存活天数做到。
接下来，我们分配没花完的余钱，让几次购买的存活时间 +1 即可
这样，我们就求出了 估价函数 / 目标函数，也就是目前状态下最长的存活日期.
当然，根据上面的分析可以猜到，存在一种正解是，三分套二分，不过如果要保证正确，是很有难度的.
现在你可能比较熟悉退火了，看看我们能不能快速秒了这几题
2018 ICPC 南京 D. Country Meow $\quad$ [ 铜牌题 ]
https://codeforces.com/gym/101981/problem/D
题意: 三维空间，每维 $2e5$，上面有 100 个点 $p_i$，求一个点 $x$，
最小化 $x$ 与 $p_i$ 距离的最大值，精度 $10^{-3}$
最小球覆盖秒了，三分套三分套三分
然后选择了写模拟退火，对点做随机增量，估价函数就是最大值，让它最小即可
哎呀这都不要动脑，性质都不要了
改一下问题。最大化: 距离的最小值，
揭开面纱。这题叫 poj1379 Run Away 。
类似的还有 HDU 3932，HDU 3644（限制答案范围的）
2014 ICPC 西安 Ellipsoid $\quad$ [ 铜牌题 ]
http://acm.hdu.edu.cn/showproblem.php?pid=5017
题意: 给你一个椭球面 $ax^2 + by^2 + cz^2 + dyz + exz + fxy = 1$
求椭球面上一点，与原点距离最近.
如果没学好 拉格朗日乘数法，就乖乖退火吧
第一眼看起来需要对 x y z 都随机化一下增量，但是发现很可能不满足公式啊
所以只需要随机化 x y，然后用求根公式求出 z 就可以了
附赠高数做法，大家都在气专的卷子上见过很类似的题，但是还记得怎么写吗？
$L = \lambda (ax^2 + by^2 + cz^2 + dyz + exz + fxy -1 ) + x^2 + y^2 + z^2$
分别对 $x,y,z,\lambda$ 求偏导得到
$ \begin{cases}
2a \lambda x + e \lambda z + \lambda fy + 2x = 0 \
2b \lambda y + d \lambda z + \lambda fx + 2y = 0 \
2c \lambda z + d \lambda y + \lambda ex + 2z = 0 \
ax^2 + by^2 + cz^2 + dyz + exz + fxy -1 = 0 \end{cases} $
这里有四个方程，可以解出 $x,y,z,\lambda$，算一下距离即可.
哎呀这是 2014 的题，我觉得 2023 的难题要用模拟退火.
(其实是因为我们数学不好对吧)
2016 ICPC 日本筑波 J Cover the Polygon with Your Disk $\quad$ [ 银牌题 ]
https://codeforces.com/gym/101158
题意: 二维平面 $200*200$，给你 $10$ 个点组成的凸包，以及一个半径确定的圆
挑一个风水宝地放它，最大化面积的交
存在三分套三分做法，细节较多
模拟退火想法就很简单，大家也都知道怎么做，但是估价函数必须要求出面积交
这部分逃不过去，可以三角剖分，不会的可以去学一下（抄个板子）
希望大家认清模拟退火的本质是，聪明退火公式 + 你的智慧代码
以及需要一些观察，比如说问题规模非常小的时候，就可以考虑大力乱搞.
##课后作业
1$s$ $ \quad $ 512 MiB $\quad$ [ 出线题 ]
题意: 二维平面 $2000*2000$，有 $n=500$ 个人，给定初始位置，进行两轮集合。
第一轮，题目会把人分成不超过 $500$ 组，请你独立地为每组分配一个集结点，每组成员前往他们的集结点（结束后会站在那里）
第二轮，题目会进行新的分组，请你独立地为每组分配一个集结点，每组成员前往他们的集结点
最小化: 所有人走过的距离之和 (欧几里得距离)，精度 $10^{-5}$
存在高斯消元做法，但也可以乱搞。
加工生产调度 $\quad$ [ 金牌题 ]
题意: 有 $n=1000$ 个物品，每个物品需要先在 $A$ 流水线造 $a_i$ 秒，再去 $B$ 流水线造 $b_i$ 秒.
$AB$ 流水线都只能同时造一个物品
请最小化总时间，并输出方案.
经典问题，存在比较难证的做法，但也可以乱搞.
[USACO12MAR] Cows in a Skyscraper G 或 2023 CCPC 秦皇岛 J $\quad$ [ 签到题 ]
题意: 有 $n=18$ 个物品，具有体积 $w_i$，同时一个袋子只能装 $V$ 体积的物品，全部物品都要装袋
最小化: 袋子数
玉藻前喜欢 模拟退火，你喜欢吗？
模拟退火 可以解决:
求点值，最优化问题，输出方案，点集划分，分配权值，小数/离散问题，也支持对解的类型/范围有所限制
相较于纯粹的随机化，或者是爬山算法，能够达到的精度也非常高，
参数也给了我们很多的操作空间，可以用时间换取正确率 / 精度
可以说是比较暴力而万能的算法了，不过弱点还是比较多，
1. 如果有 100 组测试数据，可能需要一些好的实现，至少不能出现丢炸弹那种估值函数
2. 如果问题规模较大，那么退火可能会花费更多时间在:
* 让随机的扰动尽可能抵达更多的 “山峰”（比如函数值域非常大，峰值非常多）
* 求估值函数的值（可以思考能否优化）
3. 题目本身需要一些复杂算法，模拟退火只能作为辅助手段
相当多题目是可以加强到模拟退火难以通过的，因此这个东西只能作为最终手段，
如果参加比赛的话，确实可以在最后一段时间里用这种非正解手段冲一冲，
希望大家在期末周学得高兴，学得搞笑！
最后附赠一个毫无意义的卡时代码，当将要 TLE 但还未 TLE 时，把带火星的答案塞进评测机里
可能观察到输出 WA / TLE / AC / RE
const double MAX_TIME = 0.95;
while ((double)clock() / CLOCKS_PER_SEC < MAX_TIME)
simulateAnneal();
当 $calc$ 约 $200$ 次长浮点运算时
| 时长 | $1$ 次提交 | $10$ 次提交 |
|---|---|---|
| 1s | $10^{-4}$ | $10^{-6}$ |
| 2s | $10^{-6}$ | $10^{-8}$ |
| 3s | $10^{-8}$ | $10^{-8}$ |
Views: 46
您可能也喜欢
一条评论
Kuns_Yu
牛逼牛 ^.^