首页 > 编程语言 >随机化算法

随机化算法

时间:2024-11-11 14:08:45浏览次数:1  
标签:rd clock int mt19937 随机化 算法 rand

随机化算法

随机化函数

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; 
	}
}

模拟退火

用于找一个复杂多峰函数的极值。常用于对于求出最优状态的题目骗分。

好评:大白话解析模拟退火算法

算法流程

  1. 设一个初始温度 \(temperture=T\),和下降率 \(\Delta t\),大概 \(0.9\) 左右吧,越大时间越久,正确率越高。
  2. 每次根据当前状态随机一个新状态,计算新状态的答案。如果新答案大于历史最优答案,则当前状态设为新状态,否则以 \(\frac{\exp(|bestans-newans|)}{temperture}\) 的概率接受这个状态。
  3. 如果 \(temperture<eps\),可以设 \(eps=10^{-15}\) 左右,结束算法,认为此时已经找到了最优答案。

一般可以多做几次退火(或者设一个卡时,一直做退火)以提高正确率。

标签:rd,clock,int,mt19937,随机化,算法,rand
From: https://www.cnblogs.com/liyixin0514/p/18539575

相关文章

  • 代码随想录算法训练营第十一天 | 150. 逆波兰表达式求值+ 239. 滑动窗口最大值+347.前
    今天接着补上周末的栈与队列的part2,下午继续完成今天的任务。150.逆波兰表达式求值 给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意:有效的算符为 '+'、'-'、'*' 和 '/' 。每个......
  • 代码随想录算法训练营第十天 | 232.用栈实现队列+225. 用队列实现栈+20. 有效的括号+1
    加入训练营有点晚,没跟上任务就开始有些偷懒没有真的认真开始,从第十天开始下决心认真完成每天任务还有博客记录学习过程。栈与队列理论基础首先是学习了栈和队列的理论基础,队列 先进先出,栈 先进后出。栈 以底层容器完成其所有的工作,且对外接口统一,有.push,.pop等,不提供......
  • (动画版)排序算法 -选择排序
    文章目录1.选择排序(SelectionSort)1.1简介1.2选择排序的步骤1.3选择排序的C实现1.4选择排序的时间复杂度1.5选择排序的空间复杂度1.6选择排序的动画1.选择排序(SelectionSort)1.1简介选择排序(SelectionSort)是一种简单直观的排序算法。它的工作原理是反复......
  • 数组算法练习题
    第一题:寻找锦鲤公司年会有一个寻找锦鲤的游戏,每一个员工随意写一个字,如果在“锦鲤”词库中有这个字,那么就奖励500元锦鲤红包,否则就没有,每人只能玩一次。现有锦鲤字库如下,它们按照Unicode编码值从小到大排序:char[]koiFishWords={'一','今','地','定','年','开','我','果','......
  • 算法性能测试基础
    算法的性能测试是一个综合评估算法在不同条件下的表现和效率的过程。在进行算法性能测试时,需要关注多个关键指标,以确保全面、准确地评估算法的性能。以下是对算法性能测试的详细解释和需要关注的指标的归纳:一、算法性能测试概述算法性能测试的目的是验证算法在各种输入情况下的......
  • 毕业设计:python考研院校推荐系统 混合推荐 协同过滤推荐算法 爬虫 可视化 Django框架(
    毕业设计:python考研院校推荐系统混合推荐协同过滤推荐算法爬虫可视化Django框架(源码+文档)✅1、项目介绍技术栈:Python语言MySQL数据库Django框架协同过滤推荐算法requests网络爬虫pyecharts数据可视化html页面、爬取院校信息:https://yz.chsi.com.cn/sch/(研招网......
  • 基于game-based算法的动态频谱访问matlab仿真
    1.算法运行效果图预览(完整程序运行后无水印)   展示了负载因子P和次级传输功率不同的HPE。         从图中可以看出,随着|hPE|²扩大,用户P更好的为二级用户分配更多的频谱机会,以便刺激二级用户传输更多的干扰功率,因此,导致ρ的减少和Psu的增加。 ......
  • 基于免疫算法的TSP问题求解matlab仿真
    1.程序功能描述旅行商问题(TravellingSalesmanProblem,TSP)是一个经典的组合优化问题,其目标是在给定一组城市及其相互之间的距离情况下,寻找一条经过每个城市恰好一次且返回起点的最短回路。TSP因其NP完全性及广泛应用背景而备受关注。免疫算法(ImmuneAlgorithm,IA),作为......
  • 操作系统调度算法
    操作系统使用各种算法来有效地调度处理器上的进程。调度算法的目的最大CPU利用率公平分配CPU最大吞吐量最短周转时间最短的等待时间最短响应时间有以下算法可用于计划作业。1.先来先服务这是最简单的算法。最短到达时间的过程将首先获得CPU。到达时间越少,进程得到CPU的......
  • Django电影推荐系统 豆瓣电影 协同过滤推荐算法 Echarts可视化 爬虫 机器学习 大数据
    博主介绍:✌全网粉丝10W+,前互联网大厂软件研发、集结硕博英豪成立工作室。专注于计算机相关专业项目实战6年之久,选择我们就是选择放心、选择安心毕业✌>......