随机化算法
随机化函数
rand()
srand(seed);
int x=rand()%n+1;
seed
可以是一个常数如 114514
也可以是时间 time(0)
。
注意,rand()
函数在 windows 系统下返回的取值范围为 \([0,2^{15}-1]\),在 linux 系统下返回的取值范围为 \([0,2^{31}-1]\)。
mt19937
mt19937 rd(seed);
pf("%lld\n",rd()%N+1);
用法基本同 rand()
。
mt19937
的效率比 rand()
更高,随机数的范围同 unsigned int
的范围,即 \([0,2^{32}-1]\)。
类似地,mt19937_64
的取值范围是 unsigned long long
的范围,即 \([0,2^{64}-1]\)。
random_device
可以生成比较真的随机数,但是效率比较慢。
建议使用 random_device{}()
作为 mt19937 的种子,然后使用 mt19937.
随机排列 shuffle
mt19937 rd(time(0));
shuffle(a+1,a+n+1,rd);
计时函数
clock_t st=clock();
clock_t en=clock();
if(en-st>1.98*CLOCKS_PER_SEC) break;
一种基于随机化的方法
#include<bits/stdc++.h>
#define ll long long
#define pf printf
#define sf scanf
using namespace std;
const int N=1e5+7;
mt19937 rd(random_device {}());
int main(){
clock_t start=clock();
while(1){
int x=rd()%100;
pf("%d\n",x);
//利用 x 做一些操作
//防止超时
clock_t end=clock();
if(end-start>1.98*CLOCKS_PER_SEC) break;
}
}
模拟退火
用于找一个复杂多峰函数的极值。常用于对于求出最优状态的题目骗分。
好评:大白话解析模拟退火算法。
算法流程
- 设一个初始温度 \(temperture=T\),和下降率 \(\Delta t\),大概 \(0.9\) 左右吧,越大时间越久,正确率越高。
- 每次根据当前状态随机一个新状态,计算新状态的答案。如果新答案大于历史最优答案,则当前状态设为新状态,否则以 \(\frac{\exp(|bestans-newans|)}{temperture}\) 的概率接受这个状态。
- 如果 \(temperture<eps\),可以设 \(eps=10^{-15}\) 左右,结束算法,认为此时已经找到了最优答案。
一般可以多做几次退火(或者设一个卡时,一直做退火)以提高正确率。
标签:rd,clock,int,mt19937,随机化,算法,rand From: https://www.cnblogs.com/liyixin0514/p/18539575