模拟退火,将净化一切 :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: 50
一条评论
Kuns_Yu
牛逼牛 ^.^