一 随机化贪心
你是否曾经看到过这样的一道题目
一共有 $n$ 个数,请你将这些数分成两组,使得这两组数每组数的总和的差最小。
暴力很简单,但是时间是 $O(2^n)$ 的,显然不能接受。
我们是否可以考虑贪心呢?怎么贪心比较好想。对于一个新加入的数,它需要贪心地加入目前总和最小的那组。
比如例子 {10, 3, 6, 1},首先将 10 加入第一组,然后 3 加入第二组。第三个数 6 应该加入目前和较小的那一组,即第二组,然后 1 应该加入目前和较小的那一组,即第二组。这样下来,我们可以得到一个最优解。
但是贪心很多时候不能求出最优解。比如 {3,6,1,10},这样贪心的话会直接 WA。
但是我们可以发现,对于每一个例子,总有一种重排列,使得贪心是正确的。但是我们不能枚举所有全排列。怎么办呢?
随机化!
我们每次随机化一个重排列,得出这个重排列的贪心解,然后更新总答案。
所以我们给出伪代码
1 | repeat for many times: |
怎么实现随机重排列? C++ 有一个很好用的功能叫做 random_shuffle(x,y)
。其中 x 和 y 分别填入你想要随机化的左端点地址和右端点地址。
比如你想要随机化一段 $n$ 个元素的数组 ${a_1,…,a_n}$,你可以用 random_shuffle(a+1,a+n+1)
。
要注意,C++ 的随机化是伪随机,即如果不加特殊操作,每次运行程序,随机化的结果是一样的。有一个东西叫做随机化种子。对于不同的随机化种子,随机化的结果是不一样的。所以如果不是在 CCF 评测机上,可以这样做
1 | int main() { |
但是如果在 NOI 联赛中,推荐用这个
1 | int main() { |
srand()
内部的值可以你自己设定,比如你自己的生日,某位著名领导人的生日,某些著名大质数,你喜欢的人的学号或者生日 等等。
所以下面给出本题代码
1 | srand(19260817); |
例题一 三角形牧场
和所有人一样,奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师 Hei 想建造围有漂亮白色栅栏的三角形牧场。她拥有 $n$ 块木板,每块的长度 $l_i$ 都是整数,她想用所有的木板围成一个三角形使得牧场面积最大。如果不存在三角形则输出 $-1$。
请帮助 Hei 小姐构造这样的牧场,并计算出这个最大牧场的面积。
$n,l_i\le 40$
由柯西不等式(和直觉)可以得到,给定三条边的总长度,三条边越接近,三角形的面积最大。于是这道题被转换为和上面一道题一样的模型,我们用我们的随机化贪心解决即可。
1 |
|
例题二 Haywaire
Farmer John有 $N$ 只奶牛,($4 \leq N \leq 12$,其中 $N$ 是偶数)。每一头奶牛有 3 个朋友。现在请你给奶牛安排一个排列,使得每对奶牛朋友间的距离的总和最小。
这道题放这里是为了体现随机化的优美。暴力需要 $O(n!)$,撑不过去。理论上可以暴力截断,但是太烦了。有什么更加简便优美的方法吗?模拟退火!我们接下去会讲模拟退火,但是这道题模拟退火由于常数比暴力随机更劣。我们每次随机化一个排列,然后计算一下即可。
1 | struct friends {int l,r;}e[N*3]; |
例题三 最大团问题
我们体验一下用随机化做 NPC 问题的快感。
“团”指从一个图中选出来一堆点,每对点间都直接有边相连。“最大团”就是指包含的点最多的那个团。给定一张图,让你求出最大团的大小。
点数 $\le 50$。
最大团问题可以用 折半搜索+状压 DP 解决。但是我们并不想这么麻烦。有什么其他办法吗?
当然有!我们考虑普通的贪心。动态加入点。加入这个加入的点和以前所有加入的点都有连边,那么我们就选,否则就不选。第一个点必选。
贪心的正确性很低。那么怎么办呢?随机化!我们多随机几遍不就行了?
恭喜你,用优雅的暴力解决了一道 NPC 问题。
当然,这不是正解。所谓一个问题的正解,必须保证运行出来的结果的答案保证是对的,并不涉及一些可能性的问题。但是为了能在考场上拿分,我们完全可以通过这种非正解但又正确性很高无法卡掉的办法去做。
1 |
|
二 模拟退火
先放一张经久不衰的模拟退火图。
别慌,解释好就知道什么意思了。
模拟退火有几个关键因素
- 温度,降温系数,接受条件
- 随机的改变,计算答案
首先我们看“随机的改变”。
我们还是看上面那道题目(将一堆数平均分配成两堆)。我们不想每次都来一个贪心解。我们想在目前现存的一个解上去做一个改变。比如,我们可以随机交换两个数。
假设原来的解的答案是 $ans_0$,交换完了之后的的答案是 $ans_1$。我们首先肯定先用 $ans_1$ 去更新答案。那么我们怎么考虑是否让交换完了后的解覆盖当前的解(即之后的交换操作是在原先未改变的解上,还是在新的交换过了的解上)。
- 假如 $ans_1$ 比 $ans_0$ 更优,那么我们肯定接受这个新解,覆盖现在当前的解。
- 假如 $ans_1$ 比 $ans_0$ 更差,那么我们以一定的概率去接受这个新解。接下来就是模拟退火最重要的部分了。
首先我们知道,一次随机肯定不行,我们要随机很多次。其中,我们维护一个叫做 $T$ 的变量,代表温度。温度越高,我们做改变的幅度就可以越大,接受这个新解的可能越大。但是,每随机改变一次,这个温度就必须降下来,即乘上 降温系数 $\Delta$。
那么当温度为 $T$ 时,假设原解和新解的差是 $\Delta E$,且新解更差,那么我们接受新解并覆盖原解的概率为 $e^{\frac{-\Delta E}{T}}$。这个值是模拟退火的发明者们精心计算过的。
我们再来看一下上面的模拟退火图。横坐标代表一种解,纵坐标代表这个解的值(答案)。我们需要找最佳答案,即这张图上面的那个最高的峰。每次,我们做一个随机的修改,即跳到周围的地方。但是,假设我跳到了比我低的地方,我不能完全放弃我现在的位置,因为很有可能我可以从这里跳到更高的但是原来位置达不到的位置。(如果跳到更加低的地方就直接放弃这一步,那么我们就在做爬山算法)。
如果还是有一点懵,我们可以看一下模板代码和几道题目。
1 | double delta=.... //降温系数 |
例题四 [TJOI2010] 分金币
现在有 $n$ 枚金币,每一枚金币的都有价值 $v_i$。现在将其分为两堆,使得两堆数量相差不超过 $1$。问两堆金币价值之差最小值是多少。$T$ 组问询。
$T\le 20, n\le 30, v_i\le 2^{30}$
你说这道题和我们一开始引入的问题很像?再仔细读读题。我们可以发现,这道题不能用最简单的随机化贪心去做了。于是,我们拿出法宝——模拟退火。
我们一个一个来看模拟退火中东西,带入然后套板子就行了。
温度,降温系数,接受条件都是我们自己调的,和题意本身没有关系。
现在最大需要再随机的改变以及计算答案中。我们一开始先随机分为两堆。我们做一次随机改变,即随机交换两个两堆中的金币。对于统计答案,我们暴力求和即可。
有没有什么更好的做法?有!我们的答案开一个全局变量,然后每一次随机改变(交换)时,我们就可以增量求出当前的两堆的价值。如果我们发现这个新解过差以至于我们不能接受这个解,我们再变回来即可。
题目中所写到的题目的题目链接
例题一 三角形牧场 https://www.luogu.com.cn/problem/P1284
例题二 Haywire https://www.luogu.com.cn/problem/P2210
例题三 外太空旅行(最大团问题) https://www.luogu.com.cn/problem/P1284
例题四 [TJOI2010] 分金币 https://www.luogu.com.cn/problem/P3878