本文所包含的思路来自于 NCC79601

* 算法剖析

简单来讲,背包退火就是用模拟退火的思路解决某些类型的背包问题,继承了模拟退火的玄学复杂度也继承了它的不稳定性,所以能够有效地解决大背包问题的 TLE 问题。这个算法能够把数十行的代码优化部分转移为 洗把脸 调参的问题。

例题 :LuoGuP1049【装箱问题】

有一个箱子容量为 V,同时有 n 个物品,每个物品有一个体积 vi。要求 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

·算法过程

首先就是模拟退火的随机设置自然就是把随机数种子设置好,别忘了先洗脸,然后通过模拟退火原理设置好转移概率表达式:

bool accept(int del)
{
    return ((del>0)||exp(-del/T) > (double)rand()/RAND_MAX);
} //转移概率表达式
使用这个概率从而达到刚开始退火,跳出当前最优解的概率大,而当靠近答案时跳出正确答案的可能性又逐渐减小。如有不懂请挪步模拟退火详解

·偏移过程

这就是上述问题的用武之地了: 以一定的概率不选当前最优解中的那个物品,从而衍生出另一种方案,如果比刚刚的更好,那么说明运气很好,跳到了一个更优解范围附近

if(accept(dE)) 
        {//以上述概率发生转移
            if(vis[a])
            {
                vis[a] = false;
                tot -= v[a];
            }//在当前物品已选的情况下放弃选用当前物品
            else
            {
                if(tot + v[a] > V)
                {
                    continue;
                }
                vis[a] = true;
                tot += v[a];
            }//在当前物品未选的情况下尝试选用当前物品
        }

·退火步骤

while(T > 1e-14) {
        ans=max(ans,tot); //维护最优答案,以防非酋情况发生
        a = rd; //进行随机
        int dE = v[a];
        if(vis[a])
        {
            dE *= -1; //产生能量差
        }
        if(accept(dE)) 
        {//发生转移
            if(vis[a])
            {
                vis[a] = false;
                tot -= v[a];
            }
            else
            {
                if(tot + v[a] > V)
                {
                    continue;
                }
                vis[a] = true;
                tot += v[a];
            }
        }
        T *= delta; //降温
    }

该过程通过降温系数 delta 对初温为 T 的物体降温,直到物体温度冷却接近 0。但是不能直接将 tot 作为答案输出,否则没洗脸的话可能会出现跳到了较劣解的情况。

退火的一些小技巧

1. 降温系数用 0.99789(玄学参数)
2. 初温设置为 1926(玄学参数)
3. 退火的转移概率计算式:e^(-dE/kT)
(del>0)||exp(-del/T) > (double)rand()/RAND_MAX
4. 最低温不要调的太低,不然妥妥的 TLE
5. 交一次不行说明 rp 不够你的时间不好,原代码再交一次也许 就行了呢
6. 别忘了洗脸 rp++

番外篇: 论欧皇的养成

iewqufhiwefdiweduiqwediuqedwedjewui

(被某个非酋网友摁在键盘上打/笑哭)

这是某个没洗脸的基佬的↑

这是我的↓

溜了溜了……

分类: 文章

first_fan

Just Do It,But Not Just Do It.

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注