算法小课堂（十）随机化算法

骑猪看日落 2024-04-17 11:44 60阅读 0赞

**目录**

一、概述

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满足
> 
> ![86fb8507482743d89de4a9e4099b0c08.png][]

#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用随机投点法计算Π值 ###

![4a6d248f853747689f1286e3669b47db.png][]

#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随机投点法计算定积分 ###

![3e48074848c84c98945f1a192eefdd2c.png][]

#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整数因子分解问题 ###

> ![906b31b143e446ea91b50af1775fc933.png][]

#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主元素问题 ###

![bdd6bec8ef334a2b892bc3fee4794590.png][]

#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素数测试 ###

![6e42772238514f27a708fd04503e9761.png][]

![3d2d78fa1daa423ea3bb7766e5d7bc3f.png][]

[86fb8507482743d89de4a9e4099b0c08.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/974fc1a126bb4f9abc1316d23d4c9baf.png
[4a6d248f853747689f1286e3669b47db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/36ce04f3a3ed4ec7a0671798f3815256.png
[3e48074848c84c98945f1a192eefdd2c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/1d94adac038c4e8ab848968d330dc414.png
[906b31b143e446ea91b50af1775fc933.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/37dbb3af99fc4449b69d9ba822b1c1d9.png
[bdd6bec8ef334a2b892bc3fee4794590.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/2ed291f5dbde4817867f0c776f489dd4.png
[6e42772238514f27a708fd04503e9761.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/b4cdf85482524a3abb20df7fe821d441.png
[3d2d78fa1daa423ea3bb7766e5d7bc3f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/6fdd5095cb484199ad8592b8e408e624.png