再谈随机化
Python_enjoy · · 算法·理论
前言
书接上文（浅谈随机化）， @Redshift_Shine 在评论区里指出了优化的方向。在此感谢他！
本文支持的语言标准是 C++14，更高版本应该也适用。
根据 CCF 所说，NOI 系列比赛 C++ 语言标准为 C++14。
正文
mt19937
上文说：
你看这下面的代码：
srand(k); // 其中 k 是任意一个正整数就是我们的初始化操作。
也可以使用
srand(time(0));这两个写法都可以：第一种方便调试，第二种随机性强。两种都可以使用。我们这里使用第一种。
当我们想要调用一个随机数的时候，直接调用
rand()就可以了。
消息过时了。
实际上我们可以使用 mt19937 来实现。
mt19937 的初始化操作也极其简单：
mt19937 rnd(time(NULL));其中 rnd() 是我们定义的随机函数，当我们想要调用一个随机数的时候，直接调用 rnd() 就可以了。
为什么要用 time(NULL) 呢？当然是为了随机性啦。
mt19937 的最小值为 rnd.min() 和 rnd.max() 里去了。
shuffle
在上文中说：
而当我们想要打乱一个数组 a，其下标从
1 到n ，我们可以使用这段代码：random_shuffle(a + 1, a + n + 1);
实际上，消息过时了。
random_shuffle 在 C++14 中被弃用，在 C++17 中被移除。所以，这里推荐更加厉害的东西：shuffle。
当我们想要打乱一个数组 a，其下标从
shuffle(a + 1, a + n + 1， rnd);欸？这个 rnd 是什么？其实就是我们上面 mt19937 定义的随机函数。所以 shuffle 要和 mt19937 一起使用。
shuffle 相比于 random_shuffle 的优势是：随机性强。
实战
根据我们刚才介绍的 shuffle 和 mt19937，我们来试着做一道题目。
题目：P2210 [USACO13OPEN] Haywire B
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 12 + 5;
const int M = 5;
const int INF = 0x3f3f3f;
const double down = 0.996;
int n, a[N], fri[N][M];
signed main() {
mt19937 rnd(time(NULL));
cin >> n;
for (int i = 1; i <= n; i++) {
a[i] = i;
}
for (int i = 1; i <= n; i++) {
cin >> fri[i][1] >> fri[i][2] >> fri[i][3];
}
int temp = 2000000;
int ans = INF;
while (temp--) {
shuffle(a + 1, a + n + 1 , rnd);
int tot = 0;
for (int i = 1; i <= n; i++) {
for(int j = 1; j <= 3; j++) {
tot += abs(a[i] - a[fri[i][j]]);
}
}
ans = min(ans, tot / 2);
}
cout << ans;
return 0;
}认真做一道题
就拿我们上文的最后一道习题：P6505 Run Away 来分析吧。我个人认为这道题是非常不错的，有非常多的方法解决它。
首先我们看一看这道题：
这道题题面清晰易懂，我们思考可以使用什么算法：如果你往计算几何找，你几乎想不到任何做法（除非你了解笔者看了一眼就马上爆炸的三角剖分或 Voronoi 图）。如果你思路清奇，往经典算法想，你或许能够想到二分答案。但是以上的三种做法都挺难实现的，码量极大，思路极复杂。于是，我们选择了第四条路线：随机化。
那使用模拟退火还是爬山算法呢？如果你运气极佳且不愿思考了话，我的建议是模拟退火。但是我们应该严谨分析一下。
分析一下函数，最高峰点旁的其他点，这个点必定劣于先前的点。那么，搜索的点越接近最高峰，值便越大，所以这是单峰函数。综上，爬山算法，启动！
确认的算法，基本就没什么好说的了，使用模板就可以了：
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 5;
const double down = 0.9975;
int w, h, n;
int x[N], y[N];
double dis(double x_1, double y_1, double x_2, double y_2) {
return sqrt((x_1 - x_2) * (x_1 - x_2) + (y_1 - y_2) * (y_1 - y_2));
}
int rand(int l, int r) {
return rand() % (r - l + 1) + l;
}
double best;
double tx, ty;
double energy(double x0, double y0) {
double tot = 2e9;
for (int i = 1; i <= n; i++) {
tot = min(tot, dis(x0, y0, x[i], y[i]));
}
return tot;
}
void work() {
tx = rand(0, w), ty = rand(0, h);
double good = -1;
double t = 3000;
while (t > 1e-10) {
double dx = tx + (rand() * 2 - RAND_MAX) * t;
double dy = ty + (rand() * 2 - RAND_MAX) * t;
if (dx < 0) {
dx = 0;
}
if (dy < 0) {
dy = 0;
}
if (dx > w) {
dx = w;
}
if (dy > h) {
dy = h;
}
double now = energy(dx, dy);
if (now > good) {
tx = dx, ty = dy;
good = now;
best = max(best, now);
}
t *= down;
}
}
int main() {
srand(78321);
cin >> w >> h >> n;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
}
while(((double)clock() / CLOCKS_PER_SEC) < 0.9) {
work();
}
cout << fixed << setprecision(7) << best;
return 0;
}但是，你有没有发现，我们使用的随机数是使用的 rand，没有使用 mt19937，我经过调试，搓出来了这份代码：
// 省略 dis,energy,main 的实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000 + 5;
const double down = 0.996;
mt19937 rnd(time(NULL));
int w, h, n;
int x[N], y[N];
int rand(int l, int r) {
return rnd() % (r - l + 1) + l;
}
double best;
double tx, ty;
void work() {
tx = rand(0, w), ty = rand(0, h);
double good = -1;
double t = 3000;
while (t > 1e-10) {
double dx = tx + (rnd() % 2 == 0 ? 1 : -1) * rand(1, 2) * t;
double dy = ty + (rnd() % 2 == 0 ? 1 : -1) * rand(1, 2) * t;
if (dx < 0) {
dx = 0;
}
if (dy < 0) {
dy = 0;
}
if (dx > w) {
dx = w;
}
if (dy > h) {
dy = h;
}
double now = energy(dx, dy);
if (now > good) {
tx = dx, ty = dy;
good = now;
best = max(best, now);
}
t *= down;
}
}如你所见，使用 rand 和 mt19937 各有优势：rand 写的快，mt19937 随机性好。这个纯粹看个人习惯。
总结
学好随机化，到了哪里都骗分。
我整理了一个题单，适合练习：Python_enjoy 的随机化好题。