算法小课堂(十)随机化算法

这篇具有很好参考价值的文章主要介绍了算法小课堂(十)随机化算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、概述

1.1概念

1.2分类

二、数值随机化算法

2.1随机数

2.2用随机投点法计算Π值

 2.3随机投点法计算定积分

 三、舍伍德(Sherwood)型随机化算法

3.1随机洗牌算法

3.2随机快速排序:随机选择枢点的快速排序算法

3.3找出这n个元素中第k小的元素。

四、拉斯维加斯(LasVegas)型随机化算法

4.1八皇后问题

4.2整数因子分解问题

 五、蒙特卡罗(MonteCarlo)型随机化算法

5.1主元素问题

5.2素数测试


一、概述

1.1概念

随机化算法概述是一个关于随机化算法的简单介绍。随机化算法是一种在算法中使用了随机函数的算法,随机函数的返回值会影响算法的执行流程或结果1。根据算法的性质,随机化算法可以分为数值随机算法、舍伍德算法、拉斯维加斯算法和蒙特卡罗算法

1.2分类

随机化算法大致分为四类:

  • 数值随机化算法
  • 蒙特卡罗算法
  • 拉斯维加斯算法
  • 舍伍德算法

数值化随机算法常用于数值问题求解。这类算法得到的往往是近似解,且近似解的精度随着计算时间的增加而不断提高。在许多情况下,要计算出问题的精确解是不可能的或没有必要的,用数值化税基算法可得到相当满意的解。

数值类问题常用多见于 各种积分微分,数学计算中。

蒙特卡罗算法用于求问题的准确解。对许多问题,近似解是毫无意义的。用蒙特卡罗算法能求得问题的一个解,但这个解未必是正确的。其求得正确解的概率依赖算法所用的时间。算法所用时间越多,得到正确解的概率就越高。蒙特卡罗算法的主要缺点也在于此。一般情况下,无法有效的判断所得到的解是否可定正确。(非一般情况是可以判定的!)

拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解,这个解就一定是正确解。但有时用拉斯维加斯算法会找不到解。拉斯维加斯算法找到正确解的概率会随着它所用的计算时间的增加而提高。

舍伍德算法 总能求得问题的一个正确解,消除算法最坏情形行为与特定实例之间的关联性,并不提高平均性能,也不是刻意避免算法的最坏情况行为

二、数值随机化算法

2.1随机数

随机数在随机化算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数,因此在随机化算法中使用的随机数都是一定程度上随机的,即伪随机数。 线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,…,an满足

随机化算法,算法学习笔记,算法

#include <stdio.h>

// 定义线性同余法参数
unsigned long long int seed = 0;  // 种子
const unsigned long long int a = 1664525;  // 乘法因子
const unsigned long long int c = 1013904223;  // 增量
const unsigned long long int m = 4294967296;  // 模数

// 生成伪随机数
unsigned long long int random() {
    seed = (a * seed + c) % m;
    return seed;
}

int main() {
    int i;
    unsigned long long int randomNumber;


    for (i = 0; i < 10; i++) {
        randomNumber = random();
        printf("%llu\n", randomNumber);
    }

    return 0;
}

2.2用随机投点法计算Π值

随机化算法,算法学习笔记,算法

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef long long ll;
// 使用随机投点法计算 π 值
double Darts(int n) {
    // 初始化随机数种子
    srand((unsigned)time(NULL));

    ll k = 0;
    for (ll i = 1; i <= n; i++) {
        // 生成0~1之间的随机数
        double x = rand() / (double)RAND_MAX;
        double y = rand() / (double)RAND_MAX;
        // 判断是否落在圆内
        if ((x * x + y * y) <= 1)
            k++;
    }

    // 返回π的近似值
    return 4 * k / (double)n;
}

int main() {
    ll numPoints;
    printf("请输入投点数量:");
    // 检查输入是否有效
    if (scanf("%lld", &numPoints) != 1) {
        printf("输入错误!\n");
        return -1;
    }

    double pi = Darts(numPoints);
    printf("使用随机投点法计算得到的 π 值为:%f\n", pi);

    return 0;
}

 2.3随机投点法计算定积分

随机化算法,算法学习笔记,算法

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

// 被积函数 f(x)
double f(double x) {
 return sin(x); // 示例使用 sin(x) 函数作为被积函数
}

// 使用平均值法计算定积分
double Average(int n) {
    // 初始化随机数种子
    srand((unsigned)time(NULL));

    double sum = 0;
    for (int i = 1; i <= n; i++) {
        // 生成0~2π之间的随机数
        double x = rand() / (double)RAND_MAX * 2 * M_PI;
        // 累加被积函数值
        sum += f(x);
    }

    // 返回定积分的近似值
    return sum / n * 2 * M_PI;
}

int main() {
    int numPoints;
    printf("请输入投点数量:");
    // 检查输入是否有效
    if (scanf("%d", &numPoints) != 1) {
        printf("输入错误!\n");
        return -1;
    }

    double integral = Average(numPoints);
    printf("使用平均值法计算得到的定积分结果为:%f\n", integral);

    return 0;
}

 三、舍伍德(Sherwood)型随机化算法

分析确定性算法在平均情况下的时间复杂性时,通常假定算法的输入实例满足某一特定的概率分布。事实上,很多算法对于不同的输入实例,其运行时间差别很大。

不再有最坏的情况的实例,但有最坏的执行时间。

3.1随机洗牌算法

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//舍伍德(Sherwood)型随机化算法 随机洗牌算法
void shuffle(int cards[], int n){
  if(cards==NULL) return ;
  srand(time(0));
  int i, index, temp;
  for(i=0; i<n-1; i++) {
    //保证每次第i位的值不会涉及到第i位以前
    index=i+rand()%(n-i); //保证前面已经确定的元素不会参加下面的选取
    //交换cards[i]和cards[index]
    temp=cards[i];
    cards[i]=cards[index];
    cards[index]=temp;
  }
}

//打印数组
void printArray(int arr[], int n){
  int i;
  for(i=0; i<n; i++){
    printf("%d ", arr[i]);
  }
  printf("\n");
}

//主函数
int main(){
  //定义一个数组,表示一副扑克牌
  int cards[52];
  //初始化数组,每个元素对应一张牌,从1到52
  int i;
  for(i=0; i<52; i++){
    cards[i] = i+1;
  }
  //打印原始数组
  printf("原始数组:\n");
  printArray(caards, 52);
  //调用洗牌函数
  shuffle(cards, 52);
  //打印洗牌后的数组
  printf("洗牌后的数组:\n");
  printArray(cards, 52);

  return 0;
}

3.2随机快速排序:随机选择枢点的快速排序算法

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//舍伍德(Sherwood)型随机化算法 随机快速排序:随机选择枢点的快速排序算法

//在区间[low,high]中随机选取一个元素,下标为i
int randomNum(int low, int high){
  return low + rand() % (high - low + 1);
}

//交换两个元素的值
void swap(int *a, int *b){
  int temp = *a;
  *a = *b;
  *b = temp;
}

//进行一次划分,得到轴值的位置k
int partition(int r[], int low, int high){
  int pivot = r[low]; //选取第一个元素作为轴值
  while(low < high){ //循环直到low和high相遇
    while(low < high && r[high] >= pivot) high--; //从右向左找到第一个小于轴值的元素
    swap(&r[low], &r[high]); //交换r[low]和r[high]的值
    while(low < high && r[low] <= pivot) low++; //从左向右找到第一个大于轴值的元素
    swap(&r[low], &r[high]); //交换r[low]和r[high]的值
  }
  return low; //返回轴值的位置
}

//快速排序函数
void quickSort(int r[], int low, int high)
{
	srand(time(0));
	int i, k;
	if (low<high)
	{
		i=randomNum(low, high); //在区间[low,high]中随机选取一个元素,下标为i
		swap(&r[low], &r[i]); //交换r[low]和r[i]的值
		k=partition(r, low, high); //进行一次划分,得到轴值的位置k
		quickSort(r, low, k-1);//在前半部分继续查找
		quickSort(r, k+1, high);//在后半部分继续查找
	}
}

//打印数组
void printArray(int arr[], int n){
  int i;
  for(i=0; i<n; i++){
    printf("%d ", arr[i]);
  }
  printf("\n");
}

//主函数
int main(){
  //定义一个数组,表示10个待排序的数
  int arr[10] = {23, 45, 12, 67, 89, 34, 56, 78, 90, 11};
  //打印原始数组
  printf("原始数组:\n");
  printArray(arr, 10);
  //调用快速排序函数
  quickSort(arr, 0, 9);
  //打印排序后的数组
  printf("排序后的数组:\n");
  printArray(arr, 10);

  return 0;
}

3.3找出这n个元素中第k小的元素。

给定线性序集中n个元素和一个整数k (1≤k≤n), 要求找出这n个元素中第k小的元素。 即如果将这n个元素依其线性序排列时,排在第k个位置的元素即为要找的元素。当k=1时,就是要找的最小元素:当k=n时, 就是要找最大元素;当k=(n+1)/2 时,称为找中位数。

问题分析

对于选择问题而言,用拟中位数作为划分基准可以保证在最坏的情况下用线性时间完成选择。 如果只简单地用待划分数组的第一个元素作为划分基准,则算法的平均性能较好,而在最坏的情况下需要O(n^2)计算时间。 舍伍德选择算法则随机地选择一个数组元素作为划分基准,可以保证算法的线性时间平均性能。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 生成随机数
int randomNum(int low, int high) {
    return low + rand() % (high - low + 1);
}

// 划分函数
int partition(int r[], int low, int high) {
    int pivot = r[low];
    int i = low, j = high + 1;

    while (1) {
        do {
            i++;
        } while (r[i] < pivot && i <= high);

        do {
            j--;
        } while (r[j] > pivot);

        if (i >= j)
            break;

        // 交换元素 r[i] 和 r[j]
        int temp = r[i];
        r[i] = r[j];
        r[j] = temp;
    }

    // 交换轴值 r[low] 和 r[j]
    int temp = r[low];
    r[low] = r[j];
    r[j] = temp;

    return j;
}

int select(int r[], int low, int high, int k) {
    int i, s;
    if (high - low <= k)
        return r[high]; // 数组长度小于k
    else {
        i = randomNum(low, high); // 在区间[low,high]中随机选取一个元素,下标为i
        int temp = r[low];
        r[low] = r[i];
        r[i] = temp; // 交换元素r[low]和r[i]的值
        s = partition(r, low, high); // 进行一次划分,得到轴值的位置s
        if (k == s)
            return r[s]; // 元素r[s]就是第k小元素
        else if (k < s)
            return select(r, low, s - 1, k); // 在前半部分继续查找
        else
            return select(r, s + 1, high, k); // 在后半部分继续查找
    }
}

int main() {
    srand(time(NULL));

    int n, k;
    printf("请输入元素个数 n:");
    scanf("%d", &n);

    int r[n];
    printf("请输入 %d 个元素:", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &r[i]);
    }

    printf("请输入 k 值:");
    scanf("%d", &k);

    int result = select(r, 0, n - 1, k - 1);
    printf("第 %d 小的元素为:%d\n", k, result);

    return 0;
}

四、拉斯维加斯(LasVegas)型随机化算法

需要对同一输入实例反复多次运行算法,直到成功地获得问题的解。

4.1八皇后问题

对于n后问题的任何一个解而言,每一个皇后在棋盘上的位置无任何规律,不具有系统性,而更象是随机放置的。由此容易想到下面的拉斯维加斯算法。

在棋盘上相继的各行中随机地放置皇后,并注意使新放置的皇后与已放置的皇后互不攻击,直至n个皇后均已相容地放置好,或已没有下一个皇后的可放置位置时为止。 如果将上述随机放置策略与回溯法相结合,可能会获得更好的效果。

可以先在棋盘的若干行中随机地放置皇后,然后在后继行中用回溯法继续放置,直至找到一个解或宣告失败。随机放置的皇后越多,后继回溯搜索所需的时间就越少,但失败的概率也就越大。

思路

1八皇后问题

(1)将数组x[8]初始化为0;试探次数count初始化为0;

(2)for (i=1; i<=8; i++)   

 2.1产生一个[1,8]的随机数j;   

 2.2 count=count+1,进行第count次试探;  

 2.3若皇后i(固定在第i行)放置在第j列不发生冲突,  

      则x[i]=j;count=0; 转步骤(2)(for循环继续运行)放置下一个皇后;   

 2.4若(count==8),则无法放置皇后i,算法运行失败,       

转步骤2.1重新放置皇后i;

(3) 将元素x[1]~x[8]作为八皇后问题的一个解输出。

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

bool isSafe(int x[], int row, int col) {
    // 检查当前位置是否与之前放置的皇后冲突
    for (int i = 1; i < row; i++) {
        if (x[i] == col || abs(i - row) == abs(x[i] - col)) {
            return false;
        }
    }
    return true;
}

void solveEightQueens(int x[], int row) {
    if (row > 8) {
        // 所有皇后都放置完成,打印解
        for (int i = 1; i <= 8; i++) {
            cout << x[i] << " ";
        }
        cout << endl;
    } else {
        for (int j = 1; j <= 8; j++) {
            if (isSafe(x, row, j)) {
                x[row] = j;
                solveEightQueens(x, row + 1);
            }
        }
    }
}

int main() {
    srand(time(0));

    int x[9] = {0}; // 数组从下标 1 开始使用,初始化为0

    solveEightQueens(x, 1);

    return 0;
}

4.2整数因子分解问题

随机化算法,算法学习笔记,算法

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

//拉斯维加斯(LasVegas)型随机化算法 整数因子分解问题

//在区间[low,high]中随机选取一个整数
int randomNum(int low, int high){
  return low + rand() % (high - low + 1);
}

//求两个整数的最大公约数
int gcd(int a, int b){
  if(b == 0) return a;
  return gcd(b, a % b);
}

//pollard函数,返回n的一个非平凡因子
int pollard(int n)
{
  int i=1;
  int k=2;
  int x, y, d;
  x=randomNum(0, n-1); //x为[0,n-1]区间的随机整数
  y=x;
  while(true)
  {
    i++;
    x=(x*x-1)%n;
    d=gcd(y-x, n);
    if(d>1 && d<n)
      return d; //若y-x与n存在最大公约数d,则d即为n的非平凡因子
    if(i==k)
    {
      y=x;
      k*=2;
    }
  }
}

//主函数
int main(){
  //设置随机数种子
  srand(time(0));

  //定义一个待分解的整数n
  int n = 14;

  //调用pollard函数,返回n的一个非平凡因子
  int factor = pollard(n);

  //打印结果
  cout << "n = " << n << endl;
  cout << "一个非平凡因子是:" << factor << endl;

  return 0;
}

 五、蒙特卡罗(MonteCarlo)型随机化算法

基本概念

Def1:设p是一个实数,且1/2<p<1,若一个MC算法以不小于p的概率返回一个正确的解,则该MC算法称为p-正确,算法的优势(advantage)是 p-1/2.

Def2:若一个MC算法对同一实例决不给出两个不同的正确解,则该算法称是相容的(consistent)或一致的。

蒙特卡罗型概率算法总是给出解,但是,这个解偶尔可能是不正确的,一般情况下,也无法有效地判定得到的解是否正确。

求得正确解的概率依赖于算法所用的时间,算法所用的时间越多,得到正确解的概率就越高。

这类算法的时间复杂性通常由问题规模以及错误解可接受概率的函数T(n,)来描述,其中n为输入实例I的规模

5.1主元素问题

随机化算法,算法学习笔记,算法

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

// 在区间[low,high]中随机选取一个整数
int randomNum(int low, int high) {
    return low + rand() % (high - low + 1);
}

// 判断一个元素是否是主元素,即出现次数超过一半
bool isMajority(int arr[], int n, int x) {
    int count = 0; // 记录x出现的次数
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) count++;
    }
    return count > n / 2; // 如果x出现次数超过一半,返回true
}

// 蒙特卡罗函数,返回数组中的一个主元素,如果不存在,返回-1
int monteCarlo(int arr[], int n) {
    srand(time(0)); // 设置随机数种子
    int k = 10; // 设置最大尝试次数

    // 候选主元素初始化为数组的第一个元素
    int candidate = arr[0];
    int count = 1; // 记录候选主元素的计数

    for (int i = 1; i < n; i++) {
        if (arr[i] == candidate) {
            count++;
        } else {
            count--;
            if (count == 0) {
                // 当前候选主元素计数为0,更新候选主元素为当前元素
                candidate = arr[i];
                count = 1;
            }
        }
    }

    // 最后确定的候选主元素需要再次验证
    if (isMajority(arr, n, candidate)) {
        return candidate; // 如果是,返回该元素
    }

    return -1; // 如果不存在主元素,返回-1
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 主函数
int main() {
    // 定义一个数组,表示n个待查找的数
    int arr[10] = {3, 3, 4, 4, 2, 4, 2, 4, 4,4};

    // 打印原始数组
    cout << "原始数组:\n";
    printArray(arr, 10);

    // 调用蒙特卡罗函数,返回数组中的一个主元素
    int result = monteCarlo(arr, 10);

    // 打印结果
    if (result == -1) {
        cout << "不存在主元素" << endl;
    } else {
        cout << "一个主元素是:" << result << endl;
    }

    return 0;
}

 主元素是指在数组中出现次数超过一半的元素。对于给定的数组 [3, 3, 4, 2, 4, 4, 2, 4, 4],其中元素4出现的次数是5次,超过总元素个数的一半,因此4是主元素。

5.2素数测试

随机化算法,算法学习笔记,算法

随机化算法,算法学习笔记,算法文章来源地址https://www.toymoban.com/news/detail-767832.html

到了这里,关于算法小课堂(十)随机化算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【毕业设计选题】基于深度学习的学生课堂行为检测算法系统 YOLO python 卷积神经网络 人工智能

    目录 前言 设计思路 一、课题背景与意义 二、算法理论原理 2.1 深度卷积神经网络 2.2 YOLOv5算法 三、检测的实现 3.1 数据集 3.2 实验环境搭建 3.3 实验及结果分析 实现效果图样例 最后        📅大四是整个大学期间最忙碌的时光,一边要忙着备考或实习为毕业后面临的就业升学

    2024年02月19日
    浏览(114)
  • 机器学习十大算法之七——随机森林

    集成学习(ensemble learning)是时下非常流行的机器学习算法,它本身不是一个单独的机器学习算法,而是通过在数据上构建多个横型,集成所有模型的建模结果,基本上所有的机器学习领域都可以看到集成学习的身影,在现实中集成学习也有相当大的作用,它可以用来做市场

    2024年02月11日
    浏览(39)
  • 智能合约学习笔记--随机数攻击复现

    智能合约中的随机数 在智能合约中随机数经常被用到,但是我们知道,这些生成的随机数都是伪随机数,当生成的随机数不是足够安全的时候就会产生漏洞。随机数攻击,就是针对智能合约的随机数生成算法进行攻击,预测智能合约的随机数。 目前来说常见的随机数获取有

    2023年04月12日
    浏览(43)
  • 传统机器学习(六)集成算法(1)—随机森林算法及案例详解

    集成学习(Ensemble Learning) 就是通过某种策略将多个模型集成起来,通过群体决策来提高决策准确率。 集成学习首要的问题是选择什么样的学习器以及如何集成多个基学习器,即集成策略。 一个有效的集成除了要让各个基学习器的学习效果好之外,还需要各个基学习器的差

    2024年02月01日
    浏览(56)
  • PyTorch学习笔记:data.RandomSampler——数据随机采样

    功能:随即对样本进行采样 输入: data_source :被采样的数据集合 replacement :采样策略,如果为 True ,则代表使用替换采样策略,即可重复对一个样本进行采样;如果为 False ,则表示不用替换采样策略,即一个样本最多只能被采一次 num_samples :所采样本的数量,默认采全部

    2023年04月08日
    浏览(38)
  • 机器学习5—分类算法之随机森林(Random Forest)

    随机森林(Random Forest) 是Bagging(一种并行式的集成学习方法)的一个拓展体,它的基学习器固定为决策树,多棵树也就组成了森林,而“随机”则在于选择划分属性的随机,随机森林在训练基学习器时,也采用有放回采样的方式添加样本扰动,同时它还引入了一种属性扰动

    2024年02月03日
    浏览(45)
  • 机器学习算法:线性回归、逻辑回归、决策树和随机森林解析

    引言 机器学习算法是人工智能领域的核心,它们用于解决各种问题,从预测房价到图像分类。本博客将深入探讨四种常见的机器学习算法:线性回归、逻辑回归、决策树和随机森林。 线性回归 什么是线性回归? 线性回归是一种用于建立连续数值输出的机器学习模型的算法。

    2024年02月10日
    浏览(53)
  • 《概率论与数理统计》学习笔记3-二维随机变量及其分布

    目录 二维随机变量及其分布函数 二维离散型随机变量及其概率分布 连续型随机变量及其概率密度 条件分布 二维随机变量的函数分布         二维随机变量的定义:                 X和Y是定义在随机试验E的 样本空间Ω 上的 两个随机变量 ,他们 构成的向量 (𝑋

    2024年02月07日
    浏览(54)
  • 【机器学习】P25 随机森林算法(2) 实现 “波士顿房价” 预测

    随机森林(Random Forest)算法 是一种 集成学习(Ensemble Learning)方法,它由多个决策树组成,是一种分类、回归和特征选择的机器学习算法。 在随机森林中,每个决策树都是独立地训练的,每棵树的建立都是基于随机选取的 特征子集 和随机选取的 训练样本集 。 在分类问题

    2024年02月01日
    浏览(55)
  • 机器学习实战6-糖尿病疾病的预测与分析(随机森林算法)

    大家好,我是微学AI,今天给大家介绍一下机器学习实战6-糖尿病疾病的预测与分析(随机森林算法),糖尿病是一种常见的慢性代谢性疾病,由于生活方式及基因等因素的影响,全球范围内糖尿病患者人数不断增加。预测糖尿病的发生有助于早期筛查和干预治疗,以降低糖尿

    2024年02月04日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包