随机化算法与模拟退火

前言

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

随机爬山

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

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

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

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

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

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

模拟退火

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

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

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

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

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 | $

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