浅谈随机化与模拟退火
前言
模拟赛时朋友经常用随机化乱搞，导致最后一道黑被他骗了 \(40pts\)，而我拼尽全力只有 \(10pts\)，不过也是我太菜了。
后来回家后研究了几天的随机化算法，本文是总结。
随机化算法如果能用上非常好用，几乎无脑敲代码，甚至可以轻松 A 掉难题。
随机数
随机是随机化的基础。即获取随机数。
这个比较简单，不想讲。
注意开始时随机下种子。
随机算法
随机算法的特点是玄学。一般用来打暴力骗分，或者用一些随机算法比如模拟退火搞正解。
随机算法可以分为以下步骤：
- 随机分配元素
比如打乱一个数列的顺序、每个元素分配集合、给元素赋值等。
即答案跟什么有关。
- 计算结果
字面意思，将随机后的元素状态进行计算。
- 与历史最优值比较
字面意思，把随机后的结果与最优值比较，取最优。
正确概率
这个在做题时一般不用算，因为算了不会优化也没用。
我们设随机的总情况有 \(S\) 种，能使答案正确的情况有 \(A\) 种，我们能够随机 \(T\) 次。
那么显然正确的概率就是 \((1-(\frac{S-A}{S})^T)\times 100\%\)。
注意概率不是 \(\frac{AT}{S}\)，至于为什么：
“一发导弹拦截率是 \(70\%\)，我一下子打 \(3\) 发，拦截率就是 \(210\%\)！”
随机算法的优化方法
随机算法本质是舍弃了正确性换时间复杂度。所以优化可以往时间和正确性想。
但正确性不怎么常用，而且每题都不一定一样。
优化时间
在随机过程中尽量避免无意义情况。
如果计算的时候有式子，可以化简一下，维护尽量少的元素得出答案。
剪枝。这一技巧对于数据水非常好用。有时甚至可以暴力剪枝当正解。
当你优化了每次流程的时间，就可以换来更多次的随机，正确性也有所提升。
例题
[洛谷 B3800 弹幕]([B3800 NICA #1] 弹幕 - 洛谷)。
这题可以更好理解如何算正确概率。
对于一个一元三次方程，它的解最多就是三个，而所有解最多 \(6\times 10^5\)，多随机几次一定是可以随机到的。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
inline void Rd(auto &num);
const int N=2e5+5,M=1e6+5;
const ljl Mod=1e6+1;
int n;
bool vis[M];
struct NODE{ljl a,b,c;
}node[N];
bool check(ljl x)
{for(int i=1;i<=n;++i){if(x*x*x+node[i].a*x*x+node[i].b*x+node[i].c==0)return 0;}return 1;
}
int main(){int ___=rand()%20120110;srand(___);Rd(n);ljl x=0;for(int i=1;i<=n;++i){Rd(node[i].a);Rd(node[i].b);Rd(node[i].c);}while(!check(x)){while(vis[x])x=1ll*rand()*rand()*rand()%Mod;vis[x]=1;x=1ll*rand()*rand()%Mod;}printf("%lld\n",x);return 0;
}
inline void Rd(auto &num)
{num=0;char ch=getchar();bool f=0;while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch-'0');ch=getchar();}if(f)num=-num;return;
}
[USACO13OPEN] Haywire B - 洛谷。
本题正解是状压 dp，但是显然这么做非常复杂。
考虑随机化算法。
注意到如果我们有了奶牛的排列，就可以 \(O(n)\) 算出答案。
所以我们可以给奶牛们随机排位置。
排完后计算答案，取最优值。
代码比较简单，就放下计算与随机的代码。
计算：
int calc()
{int ans=0;for(int i=1;i<=n;++i)for(int j=1;j<=3;++j)ans=ans+abs(a[i]-a[p[i][j]]);return ans/2;
}
随机：
for(int i=1;i<=n;++i)swap(a[i],a[rand()%n+1]);//每个奶牛的位置
这里也是一种对于数列随机打乱的模板。
爬山算法与模拟退火
爬山算法
爬山算法是一种类似于贪心的局部最优算法，类似于 dfs。
我们可以把所有可能的状态设为 \(x\) 轴坐标（有可能状态数量是无穷的），对应的答案设为 \(y\) 轴坐标。
那么我们的最优解就是这个函数的峰顶。
爬山算法的思想就是一开始随机个状态，然后在附近随机搜寻状态，如果更优则采纳，否则跳过。
显然爬山算法容易陷入局部最优解。因为如果全局最优与初始状态相距太远，就基本不会被爬山算法找到。
模拟退火
退火是一种金属热处理工艺，指的是将金属缓慢加热到一定温度，保持足够时间，然后以适宜速度冷却．目的是降低硬度，改善切削加工性；消除残余应力，稳定尺寸，减少变形与裂纹倾向；细化晶粒，调整组织，消除组织缺陷．准确的说，退火是一种对材料的热处理工艺，包括金属材料、非金属材料．而且新材料的退火目的也与传统金属退火存在异同．——百度百科
模拟退火与爬山算法的重要区别是它对待非更优状态不是否定，而是有概率接受。且这个概率随着时间缓慢降低。
假设我们现在的状态是 \(S\)，新状态是 \(S'\)，概率系数为 \(T\)，两个状态的差值为 \(D\)。需要保证 \(D\ge 0\)。
- \(S'\) 比 \(S\) 优：直接接受。
- 以 \(e^{\frac{-D}{T}}\) 的概率接受。
概率系数 \(T\) 又叫做温度。是为了模拟金属退火时的降温过程。
如何降温？
我们再制定一个降温系数 \(TD\)，每次搜寻状态后 \(T\leftarrow T\times TD\)，这样就可以让接收状态的概率越来越小，对应退火过程中分子运动越来越稳定。
而在平时做题的过程中，也可以多次退火取最优值以增加正确率。
看些例题。
[TJOI2010] 分金币 - 洛谷。
如何使用模拟退火？
首先不难想到将所有金币分为两个集合，大小相差不超过 \(1\)。
我们设状态序列为 \(a\)。\(a_i\) 表示第 \(i\) 个金币的价值。
每次搜寻新状态就是随机交换两个 \(a_i\) 与 \(a_j\) 的值。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
inline void Rd(auto &num);
#define db double
const db Td=0.996;
const int N=35;
const ljl inf=1e18;
int n,T;
ljl a[N],ans;
db Rand(){return (db)rand()/RAND_MAX;}//随机取小数
ljl calc()
{ljl ans=0;for(int i=1;i<=n/2;++i)ans+=a[i];for(int i=n/2+1;i<=n;++i)ans-=a[i];return abs(ans);
}
void Main()
{Rd(n);ans=inf;for(int i=1;i<=n;++i)Rd(a[i]);for(int _=1;_<=50;++_){for(db t=5000.0;t>1e-10;t*=Td){int x=rand()%n+1,y=rand()%n+1;swap(a[x],a[y]);//随即交换ljl nxt=calc();db delt=(db)nxt-(db)ans;//delt>=0if(ans>nxt)ans=nxt;if(exp(-delt/t)>Rand())continue;//概率达到了，接受新状态else//否则不接受新状态，换回原来的swap(a[x],a[y]);}}printf("%lld\n",ans);return;
}
int main(){int ___=rand()%20120110;srand(___);Rd(T);while(T--)Main();return 0;
}
inline void Rd(auto &num)
{num=0;char ch=getchar();bool f=0;while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch-'0');ch=getchar();}if(f)num=-num;return;
}P1559 运动员最佳匹配问题 - 洛谷。
也和上一题基本一样。注释在代码里。
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
inline void Rd(auto &num);
#define db double
const int N=25;
const db TD=0.9983;
db Rand(){return (db)rand()/RAND_MAX;}
int n;
ljl p[N][N],q[N][N],ans,a[N];
ljl calc()
{ljl ans=0;for(int i=1;i<=n;++i)ans+=p[i][a[i]]*q[a[i]][i];return ans;
}
void SA()
{
// for(int i=1;i<=n;++i)a[i]=i;for(int i=1;i<=n;++i)swap(a[i],a[rand()%n+1]);for(db T=5000.0;T>1e-10;T*=TD){int idx=rand()%n+1,t=rand()%n+1,y=0;//将idx号男与t号女配对 for(int i=1;i<=n;++i){if(a[i]==t){a[i]=a[idx];y=i;break;}}a[idx]=t;ljl nxt=calc();if(nxt>ans){ans=nxt;continue;}ljl delt=ans-nxt;//delt>=0if(exp(-delt/T)>Rand())continue;a[idx]=a[y];a[y]=t;}return;
}
int main(){srand(rand());Rd(n);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)Rd(p[i][j]);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)Rd(q[i][j]);for(int i=1;i<=n;++i)a[i]=i;for(int _=1;_<=600;++_)SA();printf("%lld\n",max(0ll,ans));return 0;
}
inline void Rd(auto &num)
{num=0;char ch=getchar();bool f=0;while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch-'0');ch=getchar();}if(f)num=-num;return;
}
所以说，模拟退火非常好用，把模板理解或背下来后，随便套题目。
模拟退火是对一道好题的不敬，但如果我又不用动脑又可以拿分我会更尊敬此题。