前言

在OI中,某些题是要求找一种方案,最大化或最小化某个值,此时可以选择动态规划、网络流、数学公式、线性规划、剪枝搜索、数据结构维护、二分三分等等,但如果想不出正确的方法的话,可以尝试随机化乱搞来大致骗分

随机爬山

随机爬山是一种较为容易的随机化方法,流程十分简单

  1. 随机一种初始状态
  2. 计算当前解
  3. 略微更改一下当前局面
  4. 如果当前局面比修改之前的局面更优,则将当前局面更新为全局局面
  5. 否则,忽略当前局面,回滚为之前局面
  6. 回到第三步

将这种操作多做几遍,将答案取最优值就好

当然这种方法写起来还是比较麻烦,下面给出一种简化版的随机爬山(准确的说已经不是随机爬山了,不再有爬山这个操作)

  1. 随机一种初始状态
  2. 计算当前解
  3. 回到第一步

将这种操作多做几遍,将答案取最优值就好,当然这种方法得到的答案可能会很差,仅限于时间不够的情况下去实现

模拟退火

随机爬山算法有一个缺陷,就是有可能会陷入当前局部最优解而忽略掉了全局最优解,模拟退火算法是允许一定概率的保留当前的局部非最优解,而使得可以去向全局最优解逐渐靠近,随着温度的降低,这个概率越来越低,最终退化为爬山算法

同随机爬山算法一样,模拟退火算法也需要多次执行取最优解,代码流程大致为

  1. 初始化温度
  2. 产生一个新状态,并计算解
  3. 如果新状态比当且解更优,或者有一定概率的产生,将新状态作为当前状态
  4. 降温
  5. 回到第二步

算法描述为(为了简单起见,一般不用物理学中的模拟退火公式实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
type hot() {
double T = 100000; // 初始化温度
State nowState = initState(); // 初始化状态
type ret = getvalue(nowState); // 返回最优解
while(T > 0.01) { // 达到常温
State nextState = get(nowState); // 产生新状态
if(getvalue(nextState) > getvalue(nowState) // 如果解更有就保留
|| rand() % 100000 < T) { // 一定概率更新,但随着温度升高而概率减小
nowState = nextState; // 更新状态
ret = max(ret, getvalue(nowState)); // 更新返回值
}
T *= 0.85; // 降温(退火)
}
return ret;
}
type sol() {
type ret = initState();
for(int i = 1 ; i <= 1000 ; ++ i) {
ret = max(ret, hot()); // 多次模拟退火,提高准确率
}
return ret;
}

产生新状态

一般来说,产生新状态要求从原先的状态改变之后,修改的地方比较小,定义其为邻域

比如说

图上选点集问题

邻域为某个点的选或不选

将某个序列重新排列后最优化某函数问题

邻域为选择两个位置进行互换

例题

北邮2018:F火焰炼金术

给你一张无向图,我们称一个火字,指的是对于$a,b,c,d$四个点,其中$a$与其它三个点相连的这样的四个点,两个火字不同当且仅当组成的部分有一个点不同、或者是中间那个点不同。要求你找一个点的子集,使得这些点组成的火字的个数除以该点集的大小最大

直接模拟退火,邻域为改变某个点是否选入点集

续一秒

给定数列$a_i$,将其重新排列之后最大化$ | | | a_1 - a_2 | -a_3 | \cdots -a_n | $

模拟退火,邻域为交换某两个位置上的值