精华内容
下载资源
问答
  • 随机化算法求定积分
    千次阅读
    2020-12-31 10:52:31

    随机化算法作业题,求定积分

    1.题目描述

    用随机化算法求解下面定积分
    在这里插入图片描述

    2.解题思路

    2.1将题目所给函数大致情况画出,如下

    在这里插入图片描述
    思路:由上图可以看出,当 x(1,2)区间内时,函数f(x)的值是不大于 1的,故可在1 < x < 20 < y < 1范围内进行随机投介质,观察落在f(x)范围的概率

    3.代码片段

    public double darts(int n)
    {
        double sum =0;
        for (int i = 0; i < n; i ++)
        {
            double x = Math.random() + 1;	//考虑到Math.random()的值在(0,1)之间,故+1到x范围
            double y = Math.random();
            if (y <= f(x))	//统计在f(x)范围的个数
                sum ++;
    	}
        return sum / n;		//求得f(x)范围内的个数占总数的比例,即概率
    }
    
    public double f(int x)
    {
        return x * exp(-x * x);
    }
    

    4.运行结果

    在这里插入图片描述

    5.结果分析

    通过执行结果发现,当随机次数较少时,所得结果与正确值相差较大;
    随着随机次数的增加,当达到百万量级时,所得结果与正确值相差无几

    在这里插入图片描述

    更多相关内容
  • 【PDF】数值随机化算法 预览:https://blog.csdn.net/weixin_36994568/article/details/122246905 1. 学习笔记(学习自《计算机算法设计与分析》第4版 王晓东) 2. Python代码实现 2.1 求解定积分 2.2 平均值法...
  • 数值随机化算法和舍伍德随机算法

    千次阅读 2020-06-01 19:25:04
    开篇 我们之前讨论过的动态规划算法、回溯法、分支限界算法、二分法等等都是每个计算步骤确定的算法,而这次要讨论的是随机化算法,允许算法在执行过程中随机地选择下一个计算步骤。...数值随机化算法

    开篇

    我们之前讨论过的动态规划算法、回溯法、分支限界算法、二分法等等都是每个计算步骤确定的算法,而这次要讨论的是随机化算法,允许算法在执行过程中随机地选择下一个计算步骤。
    随机化算法不一定是最优的,甚至不一定是正确的,但是它一定是最快的,可在很大程度上降低算法的复杂度。
    随机化算法的一个基本特征就是对所求解的问题的同一实例用同一随机化算法求解两次可能得到完全不同的结果。
    随机化算法可以分为四类:数值随机化、蒙特卡洛算法、拉斯维加斯算法和舍伍德算法。这次我们主要介绍数值随机化算法和舍伍德算法

    数值随机化算法

    数值随机化算法常用于数值问题的求解,得到的往往是近似解,且近似解的精度随计算时间的增加而不断提高。在许多情况下,要计算出问题的精确解是不可能的或没有必要的,因此用数值随机化算法可以得到相当满意的解。
    随机数
    随机数在随机化算法中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数,因此在随机化算法中使用的随机数都是一定程度上随机的,即伪随机数。线性同余法是产生伪随机数最常用的方法。由线性同余法产生的随机序列a1,a2,a3,…,an满足:

    a0 = d
    an = (ban-1 + c)mod m  n = 1,2,...

    式中,b>=0,c>=0,d>=m。d称为该随机序列的种子,如何选取该方法中的常数b、c和m直接关系到所称生的随机序列的随机性能,这是随机性能理论研究的内容。
    从直观上看,m应该取得充分大,因此可取m为机器大数,另应取gcd(m,d)=1,所以d可取为一素数。
    我们建立一个随机数类RandomNumber,包含一个需由用户初始化的种子randSeed。给定初始种子后,即可产生与之相应的随机序列。种子randSeed是一个无符号整数,可由用户选定也可用系统时间自动产生。函数Random()的输入参数n<=65535是一个无符号整数,返回0~n-1范围内的随机整数。函数fRandom()返回一个0-1之间的随机实数。

    #include <iostream>
    #include <time.h>
    #include <iomanip>
    using namespace std;
    //随机数类
    const unsigned long maxshort = 65536L;
    const unsigned long multiplier = 1194211696L;
    const unsigned long adder = 12345L;
    class RandomNumber
    {
        private:
            unsigned long randSeed;//当前种子
            //线性同余法产生新的种子,其高16位的随机性较好,将randomSeed右移16位,得到一个0~65535的随机整数
            //再将此随机整数映射到0~n-1范围内
        public:
            RandomNumber(unsigned long s = 0);//构造函数,默认值0表示由系统自动产生种子
            unsigned short Random(unsigned long n);//产生0:n-1之间的随机整数
            double fRandom(void);//产生(0,1)之间的随机实数
    };
    RandomNumber::RandomNumber(unsigned long s)
    {
        //产生种子
        if(s==0)
            randSeed = time(0);//用系统时间产生种子
        else
            randSeed = s;//由用户提供种子
    }
    unsigned short RandomNumber::Random(unsigned long n)
    {
        //产生0~n-1之间的随机整数
        randSeed = multiplier * randSeed + adder;
        return (unsigned short)((randSeed>>16) % n);
    }
    double RandomNumber::fRandom(void)
    {
        //产生0~1之间的随机整数
        return Random(maxshort) / double(maxshort);
    }

    下面我们来将一个实际的例子来说明随机数的应用场景。

    用伪随机数模拟抛硬币试验

    假设抛10次硬币,每次抛硬币得到正面和反面是随机的。抛10次硬币构成一个事件,调用Random(2)返回一个二值结果,0表示反面,1表示正面。我们模拟抛10次硬币这一事件50000次,计算出点数朝上次数分别为0,1,2…,10 的次数分别为多少。

    //用随机数模拟抛十次硬币,Random(2)返回一个二值结果:0表示反面,1表示正面
    //TossCoins模拟扔10次硬币这一时间,在主程序中反复用函数TossCoins模拟抛10次硬币恰好得到i次正面的次数
    int TossCoins(int numberCoins)
    {
        //随机抛硬币
        static RandomNumber coinToss;
        int i,tosses = 0;
        for(i = 0;i < numberCoins;i++)
            tosses += coinToss.Random(2);
        return tosses;
    }
    //测试程序
    int main()
    {
        const int NCOINS = 10;
        const long NTOSSES = 50000L;
        //heads[i]是得到i次正面的次数
        long i,heads[NCOINS+1];
        int j,position;
        for(j = 0;j < NCOINS + 1;j++)//初始化head数组
            heads[j] = 0;
        for(i = 0;i < NTOSSES;i++)//重复50000次模拟事件
            head[TossCoins(NCOINS)]++;
        for(i = 0;i < NCOINS;i++)
        {
            //输出频率图
            position = int(float(heads[i]) / NTOSSES * 72);
            cout<<setw(6)<<i;
            for(j = 0;j < position - 1;j++)
                cout<<" ";
            cout<<"*"<<endl;
        }
        return 0;
    }
    

    结果应如下:
    在这里插入图片描述

    用随机数估计Π值

    设一半径为r的圆及其外切四边形,向该正方形随机地投掷n个点。设落入圆内的点数为k,由于所投入的点在正方形上均匀分布,因而所投入的点落入圆内的概率为:
    在这里插入图片描述
    所以当n足够大时,k与n之比就逼近这一概率,即Π/4,从而Π≈4k/n。由此可得用随机投点法计算Π值的数值随机化算法。同理,定积分问题也可以利用随机投点法来计算
    在这里插入图片描述

    在这里插入图片描述

    //计算Π值
    double Darts(int n)//用随机投点法计算Π值
    {
        static RandomNumber dart;
        int k = 0;
        for(int i = 1;i <= n;i++)
        {
            double x = dart.fRandom();
            double y = dart.fRandom();
            if((x*x+y*y)<=1)
                k++;
        }
        return 4*k / double(n);
    }

    解非线性方程组在这里插入图片描述

    随机数还可以用来解决非线性方程组,在这里我们就不具体介绍了,大致思路是,构造一个目标函数,目标函数的极小值点即使所求非线性方程组的一组解。
    在求根区域内,选定一个x0作为一个选取随机点x,计算目标函数,并把满足精度要求的随机点x作为所求非线性方程组的近似解。
    在指定的求根区域D内,选一个随机点x0当作随即搜索的出发点。在搜索过程中,假设第j步随机搜索得到的随机搜索点为xj。在第j+1步,先计算下一步的随机搜索方向r,再计算搜索步长a,由此可以得到第j+1步的随机搜索增量Δxj。从当前点xj依随机搜索增量Δxj得到第j+1步的随机搜索点xj+1 = xj + Δxj。
    当目标函数足够小的时候(因为非线性方程组要求等式等于0),取xj+1为所求非线性方程组的近似解,否则进行下一步新的随机搜索过程。

    舍伍德算法

    舍伍德算法总能求得问题的一个解,且求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大的差异时,可在这个确定性算法中引入随机性将它改为一个舍伍德算法,从而消除或者减少问题的好坏实例间的这种差别。
    舍伍德算法的精髓不是避免算法的最坏情形行为,而是设法消除这种最坏情形行为与特定实例之间的关联性。
    假如有一确定性算法A,A是固定的,所以我们每次在A算法中的每一步选择都是固定好的,有章法可循的。
    但是现在又有一算法B,算法B在每一步是可以随机选择的,因此它就可以优化时间复杂度。
    随机选择的时间时间复杂度应该是一个平均值,所以这个时间复杂度可以消除或者减少最坏情况与实例的关联性。否则我们总会产生一种固定的形式,浪费巨大的时间,这就是我们的最坏情况。但是如果我们采用随机选择的方法,可以有效降低这种情况的概率。

    线性时间选择算法

    线性时间选择算法我们在之前讨论分治法的时候已经讨论过了,我们会在所以数列中选出中位数,再在所有中位数中选出中位数,以这个中位数为基准划分。
    但是在随机化版本中,用拟中位数作为划分基准可以保证在最坏情况下用线性时间完成选择。如果只简单地用待划分数组的第一个元素作为划分基准,则算法的平均性能较好,而在最坏情况下需要O(n^2)计算时间。
    舍伍德选择算法则随机地选择一个数组元素作为划分基准,这样既能保证算法的线性时间平均性能,也避免了计算拟中位数的麻烦。

    跳跃表

    舍伍德思想还可以用于设计高效的数据结构,跳跃表就是一例。提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能。在增设附加指针的有序链表中搜索一个元素时,可借助附加指针跳过链表中的若干节点,加快搜索速度。这种增加了向前附加指针的有序链表称为跳跃表。应在跳跃表的哪些结点增加附加指针,以及在该结点处应增加多少指针完全采用随机化方法确定。这使得跳跃表可在O(logn)平均时间内支持有序集的搜索、插入和删除等运算。
    在这里插入图片描述
    为了在动态变化中维持跳跃表中附加指针的平衡性,必须使跳跃表中k级结点数维持在总结点数的一定比例范围内。在一个完全跳跃表中,50%的指针式0级指针,25%式1级指针,…,(100/2^(k+1))%的指针是k级指针。
    因此插入一个元素的时候,1/2的概率插入一个0级结点,1/4的概率插入一个1级结点,…,以概率1/2^(k+1)引入一个k级结点**。舍伍德算法就是为跳跃表中每个结点的级数做随机**。

    展开全文
  • 随机化算法-数值随机化算法

    千次阅读 2016-10-16 15:09:23
    在现实计算机上无法产生真正的随机数,因此在随机化算法中使用的随机数都是一定程度上随机的,即伪随机数。 线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,…,an满足 其中b³0,c...

    随机数

    随机数在随机化算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数,因此在随机化算法中使用的随机数都是一定程度上随机的,即伪随机数。

    线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,…,an满足


    其中b³0c³0d£md称为该随机序列的种子。如何选取该方法中的常数bcm直接关系到所产生的随机序列的随机性能。从直观上看,m应取得充分大,因此可取m为机器大数,另外应取gcd(m,b)=1,因此可取b为一素数。

    用随机投点法计算pi

    设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布,因而所投入的点落入圆内的概率为           。所以当n足够大

    时,kn之比就逼近这一概率。从而

    double Darts(int n)
    { // 用随机投点法计算值
        static RandomNumber dart;
        int k=0;
        for (int i=1;i <=n;i++) {
          double x=dart.fRandom();
          double y=dart.fRandom();
          if ((x*x+y*y)<=1) k++;
          }
        return 4*k/double(n);
    }

    计算定积分

    f(x)[01]上的连续函数,且0£f(x)£1

    需要计算的积分为                 ,积分I等于图中的面积G


    在图所示单位正方形内均匀地作投点试验,则随机点落在曲线下面的概率为

    假设向单位正方形内随机地投入n个点(xi,yi)。如果有m个点落入

    G内,则随机点落入G内的概率

    解非线性方程组

    求解下面的非线性方程组


    其中,x1,x2,…,xn是实变量,fi是未知量x1,x2,…,xn的非线性实函数。要求确定上述方程组在指定求根范围内的一组解

    在指定求根区域D内,选定一个随机点x0作为随机搜索的出发点。在算法的搜索过程中,假设第j步随机搜索得到的随机搜索点为xj。在第j+1步,计算出下一步的随机搜索增量Dxj。从当前点xjDxj得到第j+1步的随机搜索点。当x<e时,取为所求非线性方程组的近似解。否则进行下一步新的随机搜索过程。








    展开全文
  • 第7章 随机化算法.ppt

    2019-12-08 10:45:55
    * 第7章 随机化算法 * 学习要点 理解产生伪随机数的算法 掌握数值随机化算法的设计思想 掌握蒙特卡罗算法的设计思想 掌握拉斯维加斯算法的设计思想 掌握舍伍德算法的设计思想 * 随机数 随机数在随机化算法设计中扮演...
  • 随机化算法

    2018-08-05 13:20:16
    掌握数值随机化算法的设计思想 掌握舍伍德算法的设计思想 本章将要介绍的随机化算法包括: 数值随机化算法:求解数值问题的近似解,精度随计算时间增加而不断提高 舍伍德算法:消除算法最坏情形行为与特定实例之间...
  • 随机化算法

    千次阅读 2013-08-03 21:42:47
    解非线性方程组随机化算法目标函数算法笔记数值随机化算法  问题描述  求解下面的非线性方程组  其中,x1,x2,…,xn是实变量,fi是未知量x1,x2,…,xn的非线性实函数。要求确定上述方程组在指定求
     

    0043算法笔记——【随机化算法】解非线性方程组

    分类: 算法   308人阅读  评论(0)  收藏  举报

           问题描述

         求解下面的非线性方程组


        其中,x1,x2,…,xn是实变量,fi是未知量x1,x2,…,xn的非线性实函数。要求确定上述方程组在指定求根范围内的一组解

        问题分析

         解决这类问题有多种数值方法,如:牛顿法、拟牛顿法、粒子群算法等。最常用的有线性化方法和求函数极小值方法。为了求解所给的非线性方程组,构造一目标函数


         式中,x=(x1,x2,……xn)。易知,上式取得极小值点即是所求非线性方程组的一组解

        求解思路

        在指定求根区域D内,选定一个随机点x0作为随机搜索的出发点。在算法的搜索过程中,假设第j步随机搜索得到的随机搜索点为xj。在第j+1步,计算出下一步的随机搜索增量dxj。从当前点xj依dxj得到第j+1步的随机搜索点。当x<时,取为所求非线性方程组的近似解。否则进行下一步新的随机搜索过程。

        题外话:笔者在读王晓东《算法设计与分析》中这一节时,发现书上所给的代码似乎有些问题。在这里指出,如果提得不对,还请大侠们拍砖。书中给出的代码具体如下:

    [cpp]  view plain copy
    1. bool nonlinear(double *x0,double *dx0, double *x,double a0,  
    2.       double epsilon, double k,int n, int steps,int m)  
    3. {   
    4.     static randomnumber rad;  
    5.     bool success;  
    6.     double *dx, *r;  
    7.     dx=new double[n+1];  
    8.     r=new double[n+1];  
    9.     int mm=0;  
    10.     int j=0;  
    11.     double a=a0;  
    12.     for(int i=1;i<=n;i++)  
    13.     {  
    14.         x[i]=x0[i];  
    15.         dx[i]=dx0[i];  
    16.     }  
    17.     double fx=f(x,n);  
    18.     double min=fx;  
    19.     while ((min>epsilon)&&(j<steps))  
    20.     {  
    21.         if(fx<min)  
    22.         {  
    23.             min=fx;  
    24.             a*=k;  
    25.             success=true;  
    26.          }  
    27.         else  
    28.         {  
    29.             mm++;  
    30.             if (mm>m)a/=k;  
    31.             success=false;  
    32.         }  
    33.         for(int i=1;i<=n;i++)  
    34.             r[i]=2.0*rnd.fRandom()-1;  
    35.         if(success)  
    36.             for(int i=1;i<n;i++)  
    37.                 dx[i]=a*r[i];  
    38.         else   
    39.         for (int i=1;i<n;i++)  
    40.             dx[i]=a*r[i]-dx[i];  
    41.         for (int i=1;i<n;i++)  
    42.             x[i]+=dx[i];  
    43.         fx=f(x,n);     
    44.    }  
    45.    if(fx<=epsilon)  
    46.        return ture;  
    47.    else  
    48.        return false;  
    49. }  
           问题1: while ((min>epsilon)&&(j<steps))句中,循环控制变量j<steps,但在循环体中,j没有自加,while循环永远不会结束。

         问题2:在循环体结束时,有赋值语句:fx=f(x,n);   笔者发现如果此时fx<epsilon时,程序while循环体会继续执行,到while开始几句是会更新min的值,可循环不会跳出,而会继续往下执行,更新数组x的值,重新计算目标函数f(x)。这样即时程序找到方程的解,也不会停下来。

        笔者纠正后具体程序如下:

    [cpp]  view plain copy
    1. //随机化算法 解线性方程组  
    2. #include "stdafx.h"  
    3. #include "RandomNumber.h"  
    4. #include <iostream>  
    5. using namespace std;  
    6.   
    7. bool NonLinear(double *x0,double *dx0,double *x,double a0,  
    8.                     double epsilon,double k,int n,int Steps,int M);  
    9. double f(double *x,int n);  
    10.   
    11. int main()  
    12. {  
    13.     double  *x0,                //根初值  
    14.             *x,                 //根  
    15.             *dx0,               //增量初值  
    16.             a0 = 0.0001,            //步长  
    17.             epsilon = 0.01,     //精度  
    18.             k = 1.1;            //步长变参  
    19.     int n = 2,                  //方程个数  
    20.         Steps = 10000,          //执行次数  
    21.         M = 1000;               //失败次数  
    22.   
    23.     x0 = new double[n+1];  
    24.     dx0 = new double[n+1];  
    25.     x = new double[n+1];  
    26.   
    27.     //根初值  
    28.     x0[1] = 0.0;  
    29.     x0[2] = 0.0;  
    30.   
    31.     //增量初值  
    32.     dx0[1] = 0.01;  
    33.     dx0[2] = 0.01;  
    34.   
    35.     cout<<"原方程组为:"<<endl;  
    36.     cout<<"x1-x2=1"<<endl;  
    37.     cout<<"x1+x2=3"<<endl;  
    38.   
    39.     cout<<"此方程租的根为:"<<endl;  
    40.   
    41.     bool flag = NonLinear(x0,dx0,x,a0,epsilon,k,n,Steps,M);  
    42.     while(!flag)  
    43.     {         
    44.         flag = NonLinear(x0,dx0,x,a0,epsilon,k,n,Steps,M);  
    45.     }     
    46.     for(int i=1; i<=n; i++)  
    47.     {  
    48.         cout<<"x"<<i<<"="<<x[i]<<" ";  
    49.     }  
    50.     cout<<endl;  
    51.   
    52.     return 0;  
    53. }  
    54.   
    55. //解非线性方程组的随机化算法  
    56. bool NonLinear(double *x0,double *dx0,double *x,double a0,  
    57.                     double epsilon,double k,int n,int Steps,int M)  
    58. {  
    59.     static RandomNumber rnd;  
    60.     bool success;           //搜索成功标志  
    61.     double *dx,*r;  
    62.   
    63.     dx = new double[n+1];   //步进增量向量  
    64.     r = new double[n+1];    //搜索方向向量  
    65.     int mm = 0;             //当前搜索失败次数  
    66.     int j = 0;              //迭代次数  
    67.     double a = a0;          //步长因子  
    68.   
    69.     for(int i=1; i<=n; i++)  
    70.     {  
    71.         x[i] = x0[i];  
    72.         dx[i] = dx0[i];  
    73.     }  
    74.   
    75.     double fx = f(x,n);     //计算目标函数值  
    76.     double min = fx;        //当前最优值  
    77.   
    78.     while(j<Steps)  
    79.     {  
    80.         //(1)计算随机搜索步长  
    81.         if(fx<min)//搜索成功  
    82.         {  
    83.             min = fx;  
    84.             a *= k;  
    85.             success = true;  
    86.         }  
    87.         else//搜索失败  
    88.         {  
    89.             mm++;  
    90.             if(mm>M)  
    91.             {  
    92.                 a /= k;  
    93.             }  
    94.             success = false;  
    95.         }  
    96.   
    97.         if(min<epsilon)  
    98.         {  
    99.             break;  
    100.         }  
    101.   
    102.         //(2)计算随机搜索方向和增量  
    103.         for(int i=1; i<=n; i++)  
    104.         {  
    105.             r[i] = 2.0 * rnd.fRandom()-1;  
    106.         }  
    107.   
    108.         if(success)  
    109.         {  
    110.             for(int i=1; i<=n; i++)  
    111.             {  
    112.                 dx[i] = a * r[i];  
    113.             }  
    114.         }  
    115.         else  
    116.         {  
    117.             for(int i=1; i<=n; i++)  
    118.             {  
    119.                 dx[i] = a * r[i] - dx[i];  
    120.             }  
    121.         }  
    122.   
    123.         //(3)计算随机搜索点  
    124.         for(int i=1; i<=n; i++)  
    125.         {  
    126.             x[i] += dx[i];  
    127.         }  
    128.   
    129.         //(4)计算目标函数值  
    130.         fx = f(x,n);  
    131.         j++;  
    132.     }     
    133.   
    134.     if(fx<=epsilon)  
    135.     {  
    136.         return true;  
    137.     }  
    138.     else  
    139.     {  
    140.         return false;  
    141.     }  
    142. }  
    143.   
    144. double f(double *x,int n)  
    145. {  
    146.     return (x[1]-x[2]-1)*(x[1]-x[2]-1)  
    147.             +(x[1]+x[2]-3)*(x[1]+x[2]-3);  
    148. }  
          程序运行结果如图:

     

    0042算法笔记——【随机化算法】计算π值和计算定积分

    分类: 算法   297人阅读  评论(1)  收藏  举报

         1、计算π值

        问题描述

        设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布,因而所投入的点落入圆内的概率为           。所以当n足够大时,k与n之比就逼近这一概率。从而


        程序具体代码如下:

    [cpp]  view plain copy
    1. //随机化算法 用随机投点法计算π值  
    2. #include "stdafx.h"  
    3. #include "RandomNumber.h"  
    4. #include <iostream>  
    5. using namespace std;  
    6.   
    7. double Darts(int n);  
    8.   
    9. int main()  
    10. {  
    11.     int n1 = 100,n2 = 1000,n3 = 1000,n4 = 10000,n5 = 10000000;  
    12.     cout<<"n1="<<n1<<",π1="<<Darts(n1)<<endl;  
    13.     cout<<"n2="<<n2<<",π2="<<Darts(n2)<<endl;  
    14.     cout<<"n3="<<n3<<",π3="<<Darts(n3)<<endl;  
    15.     cout<<"n4="<<n4<<",π4="<<Darts(n4)<<endl;  
    16.     cout<<"n5="<<n5<<",π5="<<Darts(n5)<<endl;  
    17.     return 0;  
    18. }  
    19.   
    20. //用随机投点法计算π值  
    21. double Darts(int n)  
    22. {  
    23.     static RandomNumber dart;  
    24.     int k = 0;  
    25.   
    26.     for(int i=1; i<=n; i++)  
    27.     {  
    28.         double x = dart.fRandom();  
    29.         double y = dart.fRandom();  
    30.         if((x*x + y*y)<=1)  
    31.         {  
    32.             k++;  
    33.         }  
    34.     }  
    35.   
    36.     return 4*k/double(n);  
    37. }  
         程序运行结果如图:


        2、计算定积分

        例:设f(x)=x^2,求

        解:

        1)随机投点法计算定积分

         基本思想是在矩形区域上随机均匀的投点实现。本算法的基本思想是在积分区间上随机均匀的产生点, 即在[a,b]上随机均匀的取点, 求出由这些点产生的函数值的算术平均值, 再乘以区间宽度, 即可解出定积分得近似解


        算法具体代码如下:

    [cpp]  view plain copy
    1. //随机化算法 用随机投点法计算定积分  
    2. #include "stdafx.h"  
    3. #include "RandomNumber.h"  
    4. #include <iostream>  
    5. using namespace std;  
    6.   
    7. double Darts(int n,double a,double b);  
    8. double f(double x);  
    9.   
    10. int main()  
    11. {  
    12.     int n1 = 100,n2 = 1000,n3 = 1000,n4 = 10000,n5 = 10000000;  
    13.     double a = 2.0,b = 3.0;  
    14.     cout<<"n1="<<n1<<",r1="<<Darts(n1,a,b)<<endl;  
    15.     cout<<"n2="<<n2<<",r2="<<Darts(n2,a,b)<<endl;  
    16.     cout<<"n3="<<n3<<",r3="<<Darts(n3,a,b)<<endl;  
    17.     cout<<"n4="<<n4<<",r4="<<Darts(n4,a,b)<<endl;  
    18.     cout<<"n5="<<n5<<",r5="<<Darts(n5,a,b)<<endl;  
    19.     return 0;  
    20. }  
    21.   
    22. /* 
    23.  * 基本思想是在矩形区域内随机均匀投点,求出由这些点 
    24.  * 产生的函数值的算术平均值,再乘以区间宽度,即可得 
    25.  * 出定积分的近似解 
    26.  */  
    27. double Darts(int n,double a,double b)  
    28. {  
    29.     static RandomNumber dart;  
    30.     double sum = 0.0;  
    31.     for(int i=0; i<n; i++)  
    32.     {  
    33.         double x = (b-a)*dart.fRandom() + a;//产生[a,b)之间的随机数  
    34.         sum = sum + f(x);  
    35.     }  
    36.     return (b-a)*sum/n;  
    37. }  
    38.   
    39. double f(double x)  
    40. {  
    41.     return x*x;  
    42. }  
        程序运行结果如图:


       
     2)概率法法计算定积分

        设f:[a,b]→[c,d]连续函数(如图2 所示), 则由曲线y=f(x)以及x 轴和直线x=a,x=b 围成的面积由定积分给出。根据几何概型可知。假设向矩形区域随机均匀的投镖n 次, 落入阴影为K次, 又设M为x=a、x=b、y=c、y=d 所围成的矩形面积, s 为定积分面积,则, 所以s= k/n×M。


        算法具体代码 如下:

    [cpp]  view plain copy
    1. //随机化算法 用概率法计算定积分  
    2. #include "stdafx.h"  
    3. #include "RandomNumber.h"  
    4. #include <iostream>  
    5. using namespace std;  
    6.   
    7. double Darts(int n,double a,double b,double d);  
    8. double f(double x);  
    9.   
    10. int main()  
    11. {  
    12.     int n1 = 100,n2 = 1000,n3 = 1000,n4 = 10000,n5 = 10000000;  
    13.     double a = 2.0,b = 3.0;  
    14.     double d = f(b);  
    15.     cout<<"n1="<<n1<<",r1="<<Darts(n1,a,b,d)<<endl;  
    16.     cout<<"n2="<<n2<<",r2="<<Darts(n2,a,b,d)<<endl;  
    17.     cout<<"n3="<<n3<<",r3="<<Darts(n3,a,b,d)<<endl;  
    18.     cout<<"n4="<<n4<<",r4="<<Darts(n4,a,b,d)<<endl;  
    19.     cout<<"n5="<<n5<<",r5="<<Darts(n5,a,b,d)<<endl;  
    20.     return 0;  
    21. }  
    22.   
    23. /* 
    24.  * f 为积分函数, n 为投镖 
    25.  * 总数, a,b 为积分区间, c,d 为函 
    26.  * 数f 的值域的端点值 
    27.  */  
    28. double Darts(int n,double a,double b,double d)  
    29. {  
    30.     static RandomNumber dart;  
    31.     int k = 0;  
    32.     for(int i=0; i<n; i++)  
    33.     {  
    34.         double x = (b-a)*dart.fRandom() + a;//产生[a,b)之间的随机数  
    35.         double y = d * dart.fRandom();  
    36.   
    37.         if(y<=f(x))  
    38.         {  
    39.             k++;  
    40.         }  
    41.     }  
    42.     return d*(b-a)*k/n;  
    43. }  
    44.   
    45. double f(double x)  
    46. {  
    47.     return x*x;  
    48. }  
        程序运行结果如图:


      

     

    0041算法笔记——【随机化算法】随机化算法与随机数问题

    分类: 算法   295人阅读  评论(0)  收藏  举报

         1、随机化算法

        (1)描述随机化算法是这样一种算法,在算法中使用了随机函数,且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。随机化算法基于随机方法,依赖于概率大小。

        (2)分类:一般情况下,可将概率(随机化)算法大致分为四类:数值概率算法,蒙特卡罗(Monte Carlo)算法,拉斯维加斯(Las Vegas)算法和舍伍德(Sherwood)算法。

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

        蒙特卡罗(Monte Carlo)算法:蒙特卡罗(Monte Carlo)算法用于求问题的准确解。用蒙特卡罗算法能求得问题的一个解,但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多,得到正确解的概率就越高。蒙特卡罗算法的主要缺点就在于此。一般情况下,无法有效判断得到的解是否肯定正确。

        拉斯维加斯(Las Vegas)算法:拉斯维加斯(Las Vegas)算法不会得到不正确的解,一旦用拉斯维加斯算法找到一个解,那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似。拉斯维加斯算法得到正确解的概率随着它用的计算时间的增加而提高。对于所求解问题的任一实例,用同一拉斯维加斯算法反复对该实例求解足够多次,可使求解失效的概率任意小。

        舍伍德(Sherwood)算法舍伍德(Sherwood)算法总能求得问题的一个解,且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时,可以在这个确定算法中引入随机性将它改造成一个舍伍德算法,消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为,而是设法消除这种最坏行为与特定实例之间的关联性。这意味着不存在坏的输入,只有坏的随机数。

        2、随机数

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


         其中b>=0,c>=0,d<=m。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。从直观上看,m应取得充分大,因此可取m为机器大数,另外应取gcd(m,b)=1,因此可取b为一素数。

         利用线性同余法原理,可以设计出一个随机数类RandomNumber。该类包含一个由用户初始化的种子randSeed。给定初始种子后,即可产生与之相对应的随机序列。种子randSeed是一个无符号整型数,可由用户选定也可用系统时间自动产生。函数Random在每次计算时,用线性同余式计算新的种子randSeed。它的高16位的随机性较好。将randSeed右移16位得到一个0~65535间的随机整数。然后将此随机数映射到0~(n-1)范围内。函数fRandom,先用函数Random(maxshort)产生一个0~(maxshot-1)之间的整型随机序列,将每个整型随机数除以maxshort,就得到[0,1)区间中的随机实数。具体代码如下:

    [cpp]  view plain copy
    1. #include"time.h"  
    2. //随机数类  
    3. const unsigned long maxshort = 65536L;  
    4. const unsigned long multiplier = 1194211693L;  
    5. const unsigned long adder = 12345L;  
    6.   
    7. class RandomNumber  
    8. {  
    9.     private:  
    10.         //当前种子  
    11.         unsigned long randSeed;  
    12.     public:  
    13.         RandomNumber(unsigned long s = 0);//构造函数,默认值0表示由系统自动产生种子  
    14.         unsigned short Random(unsigned long n);//产生0:n-1之间的随机整数  
    15.         double fRandom(void);//产生[0,1)之间的随机实数  
    16. };  
    17.   
    18. RandomNumber::RandomNumber(unsigned long s)//产生种子  
    19. {  
    20.     if(s == 0)  
    21.     {  
    22.         randSeed = time(0);//用系统时间产生种子  
    23.     }  
    24.     else  
    25.     {  
    26.         randSeed = s;//由用户提供种子  
    27.     }  
    28. }  
    29.   
    30. unsigned short RandomNumber::Random(unsigned long n)//产生0:n-1之间的随机整数  
    31. {  
    32.     randSeed = multiplier * randSeed + adder;//线性同余式  
    33.     return (unsigned short)((randSeed>>16)%n);  
    34. }  
    35.   
    36. double RandomNumber::fRandom(void)//产生[0,1)之间的随机实数  
    37. {  
    38.     return Random(maxshort)/double(maxshort);  
    39. }  
        3、随机数测试

        用计算机产生的伪随机数来模拟抛硬币试验。假设抛10次硬币,每次抛硬币得到正面和反面是随机的。拋10次硬币构成一个事件。调用Random(2)返回一个二值结果。在主程序中反复调用函数TossCoins模拟拋10次硬币这一事件50000次。用head[i](0<=i<=10)记录这50000次模拟恰好得到i次正面的刺手。最终输出模拟抛硬币事件得到的正面事件的概率图。具体代码如下:

    [cpp]  view plain copy
    1. //随机数类抛硬币实验测试  
    2. #include "stdafx.h"  
    3. #include "RandomNumber.h"  
    4. #include <iostream>  
    5. using namespace std;  
    6.   
    7. int TossCoins(int numberCoins);  
    8.   
    9. int main()  
    10. {  
    11.     //模拟随机抛硬币事件  
    12.     const int NCOINS = 10;  
    13.     const long NTOSSES = 50000L;  
    14.     //heads[i]是得到i次正面的次数  
    15.     long i,heads[NCOINS+1];  
    16.   
    17.     int j,position;  
    18.   
    19.     //初始化数组heads  
    20.     for(int j=0; j<NCOINS+1;j++)  
    21.     {  
    22.         heads[j] = 0;  
    23.     }  
    24.   
    25.     //重复50,000次模拟事件  
    26.     for(int i=0; i<NTOSSES; i++)  
    27.     {  
    28.         heads[TossCoins(NCOINS)]++;  
    29.     }  
    30.   
    31.     //输出频率图  
    32.     for(int i=0; i<=NCOINS; i++)  
    33.     {  
    34.         position = int(float(heads[i])/NTOSSES*72);  
    35.         cout<<i<<" ";  
    36.         for(int j=0; j<position-1; j++)  
    37.         {  
    38.             cout<<" ";  
    39.         }  
    40.         cout<<"*"<<endl;  
    41.     }  
    42.   
    43.     return 0;  
    44. }  
    45.   
    46. int TossCoins(int numberCoins)  
    47. {  
    48.     //随机抛硬币  
    49.     static RandomNumber coinToss;  
    50.     int i,tosses = 0;  
    51.     for(int i=0; i<numberCoins; i++)  
    52.     {  
    53.         //Random(2) = 1表示正面  
    54.         tosses += coinToss.Random(2);  
    55.     }  
    56.     return tosses;  
    57. }  
        程序运行结果如图:

     

    0044算法笔记——【随机化算法】舍伍德(Sherwood)算法和线性时间选择问题

    分类: 算法   236人阅读  评论(2)  收藏  举报

          1、舍伍德(Sherwood)算法

         设A是一个确定性算法,当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体,则当问题的输入规模为n时,算法A所需的平均时间为。这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B,使得对问题的输入规模为n的每一个实例均有。这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时,舍伍德算法可获得很好的平均性能。

         2、线性时间选择算法

         1)随机划分选择基准

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

    [cpp]  view plain copy
    1. //随机化算法 线性时间选择 随机划分选择基准  
    2. #include "stdafx.h"  
    3. #include "RandomNumber.h"  
    4. #include <iostream>  
    5. using namespace std;  
    6.   
    7. template<class Type>  
    8. Type select(Type a[],int l,int r,int k);  
    9.   
    10. template<class Type>  
    11. Type select(Type a[],int n,int k);  
    12.   
    13. template <class Type>  
    14. inline void Swap(Type &a,Type &b);  
    15.   
    16. int main()  
    17. {  
    18.     int a[] = {5,7,3,4,8,6,9,1,2};    
    19.     cout<<"原数组为:"<<endl;  
    20.     for(int i=0; i<9; i++)    
    21.     {    
    22.         cout<<a[i]<<" ";    
    23.     }    
    24.     cout<<endl;    
    25.     cout<<"所给数组第7小元素为:"<<select(a,9,7)<<endl;    
    26.     return 0;  
    27. }  
    28.   
    29. //计算a[0:n-1]中第k小元素  
    30. //假设a[n]是一个键值无穷大的元素  
    31. template<class Type>  
    32. Type select(Type a[],int n,int k)  
    33. {  
    34.     if(k<1 || k>n)  
    35.     {  
    36.         cout<<"请输入正确的k!"<<endl;  
    37.         return 0;  
    38.     }  
    39.     return select(a,0,n-1,k);  
    40. }  
    41.   
    42. //计算a[l:r]中第k小元素  
    43. template<class Type>  
    44. Type select(Type a[],int l,int r,int k)  
    45. {  
    46.     static RandomNumber rnd;  
    47.     while(true)  
    48.     {  
    49.         if(l>=r)  
    50.         {  
    51.             return a[l];  
    52.         }  
    53.   
    54.         int i = l,  
    55.             j = l + rnd.Random(r-l+1);//随机选择划分基准  
    56.   
    57.         Swap(a[i],a[j]);  
    58.   
    59.         j = r+1;  
    60.         Type pivot = a[l];  
    61.   
    62.         //以划分基准为轴做元素交换  
    63.         while(true)  
    64.         {  
    65.             while(a[++i]<pivot);  
    66.             while(a[--j]>pivot);  
    67.             if(i>=j)  
    68.             {  
    69.                 break;  
    70.             }  
    71.             Swap(a[i],a[j]);  
    72.         }  
    73.   
    74.         if(j-l+1 == k)//第k小  
    75.         {  
    76.             return pivot;  
    77.         }  
    78.   
    79.         //a[j]必然小于pivot,做最后一次交换,满足左侧比pivot小,右侧比pivot大  
    80.         a[l] = a[j];  
    81.         a[j] = pivot;  
    82.   
    83.         //对子数组重复划分过程  
    84.         if(j-l+1<k)  
    85.         {  
    86.             k = k-j+l-1;//右侧:k-(j-l+1)=k-j+l-1  
    87.             l = j + 1;  
    88.         }  
    89.         else  
    90.         {  
    91.             r = j - 1;  
    92.         }  
    93.     }  
    94. }  
    95.   
    96. template <class Type>  
    97. inline void Swap(Type &a,Type &b)  
    98. {  
    99.     Type temp = a;  
    100.     a = b;  
    101.     b = temp;  
    102. }  
         程序运行结果如图:


         2)随机洗牌预处理

          有时也会遇到这样的情况,即所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术,不改变原有的确定性算法,仅对其输入进行随机洗牌,同样可收到舍伍德算法的效果。例如,对于确定性选择算法,可以用下面的洗牌算法shuffle将数组a中元素随机排列,然后用确定性选择算法求解。这样做所收到的效果与舍伍德型算法的效果是一样的。

    [cpp]  view plain copy
    1. //随机化算法 线性时间选择 输入预处理,洗牌  
    2. #include "stdafx.h"  
    3. #include "RandomNumber.h"  
    4. #include <iostream>  
    5. using namespace std;  
    6.   
    7. template<class Type>  
    8. Type select(Type a[],int l,int r,int k);  
    9.   
    10. template<class Type>  
    11. Type select(Type a[],int n,int k);  
    12.   
    13. template<class Type>  
    14. void Shuffle(Type a[],int n);  
    15.   
    16. template <class Type>  
    17. inline void Swap(Type &a,Type &b);  
    18.   
    19. int main()  
    20. {  
    21.     int a[] = {5,7,3,4,8,6,9,1,2};    
    22.     cout<<"原数组为:"<<endl;  
    23.     for(int i=0; i<9; i++)    
    24.     {    
    25.         cout<<a[i]<<" ";    
    26.     }    
    27.     cout<<endl;   
    28.     Shuffle(a,9);//洗牌  
    29.     cout<<"洗牌后数组为:"<<endl;  
    30.     for(int i=0; i<9; i++)    
    31.     {    
    32.         cout<<a[i]<<" ";    
    33.     }    
    34.     cout<<endl;    
    35.     cout<<"所给数组第7小元素为:"<<select(a,9,7)<<endl;    
    36.     return 0;  
    37. }  
    38.   
    39. //计算a[0:n-1]中第k小元素  
    40. //假设a[n]是一个键值无穷大的元素  
    41. template<class Type>  
    42. Type select(Type a[],int n,int k)  
    43. {  
    44.     if(k<1 || k>n)  
    45.     {  
    46.         cout<<"请输入正确的k!"<<endl;  
    47.         return 0;  
    48.     }  
    49.     return select(a,0,n-1,k);  
    50. }  
    51.   
    52. //计算a[l:r]中第k小元素  
    53. template<class Type>  
    54. Type select(Type a[],int l,int r,int k)  
    55. {  
    56.     while(true)  
    57.     {  
    58.         if(l>=r)  
    59.         {  
    60.             return a[l];  
    61.         }  
    62.         int i = l;  
    63.         int j = r+1;  
    64.         Type pivot = a[l];  
    65.   
    66.         //以划分基准为轴做元素交换  
    67.         while(true)  
    68.         {  
    69.             while(a[++i]<pivot);  
    70.             while(a[--j]>pivot);  
    71.             if(i>=j)  
    72.             {  
    73.                 break;  
    74.             }  
    75.             Swap(a[i],a[j]);  
    76.         }  
    77.   
    78.         if(j-l+1 == k)//第k小  
    79.         {  
    80.             return pivot;  
    81.         }  
    82.   
    83.         //a[j]必然小于pivot,做最后一次交换,满足左侧比pivot小,右侧比pivot大  
    84.         a[l] = a[j];  
    85.         a[j] = pivot;  
    86.   
    87.         //对子数组重复划分过程  
    88.         if(j-l+1<k)  
    89.         {  
    90.             k = k-j+l-1;//右侧:k-(j-l+1)=k-j+l-1  
    91.             l = j + 1;  
    92.         }  
    93.         else  
    94.         {  
    95.             r = j - 1;  
    96.         }  
    97.     }  
    98. }  
    99.   
    100. template <class Type>  
    101. inline void Swap(Type &a,Type &b)  
    102. {  
    103.     Type temp = a;  
    104.     a = b;  
    105.     b = temp;  
    106. }  
    107.   
    108. //随机洗牌算法  
    109. template<class Type>  
    110. void Shuffle(Type a[],int n)  
    111. {  
    112.     static RandomNumber rnd;  
    113.     for(int i=0; i<n; i++)  
    114.     {  
    115.         int j = rnd.Random(n-i)+i;  
    116.         Swap(a[i],a[j]);  
    117.     }  
    118. }  
          程序运行结果如图:

    0045算法笔记——【随机化算法】舍伍德随机化思想搜索有序表

    分类: 算法   315人阅读  评论(1)  收藏  举报

         问题描述

         用两个数组来表示所给的含有n个元素的有序集S。用value[0:n]存储有序集中的元素,link[0:n]存储有序集中元素在数组value中位置的指针(实际上使用数组模拟链表)。link[0]指向有序集中的第一个元素,集value[link[0]]是集合中的最小元素。一般地,如果value[i]是所给有序集S中的第k个元素,则value[link[i]]是S中第k+1个元素。S中元素的有序性表现为,对于任意1<=i<=n有value[i]<=value[link[i]]。对于集合S中的最大元素value[k]有,link[k]=0且value[0]是一个大数。

        例:有序集S={1,2,3,5,8,13,21}的一种表现方式如图所示:


        搜索思想

         对于有序链表,可采用顺序搜索的方式在所给的有序集S中搜索值为x的元素。如果有序集S中含有n个元素,则在最坏的情况下,顺序搜索算法所需的计算时间为O(n)。利用数组下标的索引性质,可以设计一个随机化搜索算法,一改进算法的搜索时间复杂性。算法的基本思想是,随机抽取数组元素若干次,从较接近搜索元素x的位置开始做顺序搜索。如果随机搜索数组元素k次,则其后顺序搜索所需的平均比较次数为O(n/k+1)。因此,如果去k=|sqrt(n)|,则算法所需的平均计算时间为(Osqrt(n))。

        随机化思想下的有序表实现具体代码如下:

       1、RandomNumber.h

    [cpp]  view plain copy
    1. #include"time.h"  
    2. //随机数类  
    3. const unsigned long maxshort = 65536L;  
    4. const unsigned long multiplier = 1194211693L;  
    5. const unsigned long adder = 12345L;  
    6.   
    7. class RandomNumber  
    8. {  
    9.     private:  
    10.         //当前种子  
    11.         unsigned long randSeed;  
    12.     public:  
    13.         RandomNumber(unsigned long s = 0);//构造函数,默认值0表示由系统自动产生种子  
    14.         unsigned short Random(unsigned long n);//产生0:n-1之间的随机整数  
    15.         double fRandom(void);//产生[0,1)之间的随机实数  
    16. };  
    17.   
    18. RandomNumber::RandomNumber(unsigned long s)//产生种子  
    19. {  
    20.     if(s == 0)  
    21.     {  
    22.         randSeed = time(0);//用系统时间产生种子  
    23.     }  
    24.     else  
    25.     {  
    26.         randSeed = s;//由用户提供种子  
    27.     }  
    28. }  
    29.   
    30. unsigned short RandomNumber::Random(unsigned long n)//产生0:n-1之间的随机整数  
    31. {  
    32.     randSeed = multiplier * randSeed + adder;//线性同余式  
    33.     return (unsigned short)((randSeed>>16)%n);  
    34. }  
    35.   
    36. double RandomNumber::fRandom(void)//产生[0,1)之间的随机实数  
    37. {  
    38.     return Random(maxshort)/double(maxshort);  
    39. }  
        2、7d3d2.cpp

    [cpp]  view plain copy
    1. //随机化算法搜素有序表  
    2. #include "stdafx.h"  
    3. #include "RandomNumber.h"  
    4. #include "math.h"  
    5. #include <iostream>  
    6. using namespace std;  
    7.   
    8. template<class Type>  
    9. class OrderedList  
    10. {  
    11.     friend int main();  
    12.     public:  
    13.         OrderedList(Type Small,Type Large,int MaxL);  
    14.         ~OrderedList();  
    15.         bool Search(Type x,int& index);     //搜索指定元素  
    16.         int SearchLast(void);               //搜索最大元素  
    17.         void Insert(Type k);                //插入指定元素  
    18.         void Delete(Type k);                //删除指定元素  
    19.         void Output();                      //输出集合中元素  
    20.     private:  
    21.         int n;                              //当前集合中元素的个数  
    22.         int MaxLength;                      //集合中最大元素的个数  
    23.         Type *value;                        //存储集合中元素的数组  
    24.         int *link;                          //指针数组  
    25.         RandomNumber rnd;                   //随机数产生器  
    26.         Type Small;                         //集合中元素的下界  
    27.         Type TailKey;                       //集合中元素的上界    
    28. };  
    29.   
    30. //构造函数  
    31. template<class Type>  
    32. OrderedList<Type>::OrderedList(Type small,Type Large,int MaxL)  
    33. {  
    34.     MaxLength = MaxL;  
    35.     value = new Type[MaxLength+1];  
    36.     link = new int[MaxLength+1];  
    37.     TailKey = Large;  
    38.     n = 0;  
    39.     link[0] = 0;  
    40.     value[0] = TailKey;  
    41.     Small = small;  
    42. }  
    43.   
    44. //析构函数  
    45. template<class Type>  
    46. OrderedList<Type>::~OrderedList()  
    47. {  
    48.     delete value;  
    49.     delete link;  
    50. }  
    51.   
    52. //搜索集合中指定元素k  
    53. template<class Type>  
    54. bool OrderedList<Type>::Search(Type x,int& index)  
    55. {  
    56.     index = 0;  
    57.     Type max = Small;  
    58.     int m = floor(sqrt(double(n)));//随机抽取数组元素次数  
    59.   
    60.     for(int i=1; i<=m; i++)  
    61.     {  
    62.         int j = rnd.Random(n)+1;//随机产生数组元素位置  
    63.         Type y = value[j];  
    64.           
    65.         if((max<y)&& (y<x))  
    66.         {  
    67.             max = y;  
    68.             index = j;  
    69.         }  
    70.     }  
    71.   
    72.     //顺序搜索  
    73.     while(value[link[index]]<x)  
    74.     {  
    75.         index = link[index];  
    76.     }  
    77.   
    78.     return (value[link[index]] == x);  
    79. }  
    80.   
    81. //插入指定元素  
    82. template<class Type>  
    83. void OrderedList<Type>::Insert(Type k)  
    84. {  
    85.     if((n == MaxLength)||(k>=TailKey))  
    86.     {  
    87.         return;  
    88.     }  
    89.     int index;  
    90.   
    91.     if(!Search(k,index))  
    92.     {  
    93.         value[++n] = k;  
    94.         link[n] = link[index];  
    95.         link[index] = n;  
    96.     }  
    97. }  
    98.   
    99. //搜索集合中最大元素  
    100. template<class Type>  
    101. int OrderedList<Type>::SearchLast(void)  
    102. {  
    103.     int index = 0;  
    104.     Type x = value[n];  
    105.     Type max = Small;  
    106.     int m = floor(sqrt(double(n)));//随机抽取数组元素次数  
    107.   
    108.     for(int i=1; i<=m; i++)  
    109.     {  
    110.         int j = rnd.Random(n)+1;//随机产生数组元素位置  
    111.         Type y = value[j];  
    112.   
    113.         if((max<y)&&(y<x))  
    114.         {  
    115.             max = y;  
    116.             index = j;  
    117.         }  
    118.     }  
    119.   
    120.     //顺序搜索  
    121.     while(link[index]!=n)  
    122.     {  
    123.         index = link[index];  
    124.     }  
    125.     return index;  
    126. }  
    127.   
    128. //删除集合中指定元素  
    129. template<class Type>  
    130. void OrderedList<Type>::Delete(Type k)  
    131. {  
    132.     if((n==0)&&(k>=TailKey))  
    133.     {  
    134.         return;  
    135.     }  
    136.   
    137.     int index;  
    138.     if(Search(k,index))  
    139.     {  
    140.         int p = link[index];  
    141.         if(p == n)  
    142.         {  
    143.             link[index] = link[p];  
    144.         }     
    145.         else  
    146.         {  
    147.             if(link[p]!=n)  
    148.             {  
    149.                 int q = SearchLast();  
    150.                 link[q] = p;  
    151.                 link[index] = link[p];  
    152.             }  
    153.             value[p] = value[n];//删除元素由最大元素来填补  
    154.             link[p] = link[n];  
    155.         }  
    156.         n--;  
    157.     }  
    158. }  
    159.   
    160. //输出集合中所有元素  
    161. template<class Type>  
    162. void OrderedList<Type>::Output()  
    163. {  
    164.     int index = 0,i = 0;  
    165.     while(i<n)  
    166.     {  
    167.         index = link[index];  
    168.         cout<<value[index]<<" ";  
    169.         i++;  
    170.     }  
    171.     cout<<endl;  
    172.     cout<<"value:";  
    173.     for(i=0; i<=n; i++)  
    174.     {  
    175.         cout.width(4);  
    176.         cout<<value[i];  
    177.     }  
    178.     cout<<endl;  
    179.     cout<<"link:";      
    180.     for(i=0; i<=n; i++)  
    181.     {  
    182.         cout.width(4);  
    183.         cout<<link[i];  
    184.     }  
    185.     cout<<endl;     
    186. }  
    187.   
    188. int main()  
    189. {  
    190.     static RandomNumber rnd;  
    191.     OrderedList<int> *ol = new OrderedList<int>(0,100,100);  
    192.   
    193.     //创建  
    194.     cout<<"=========创建==========="<<endl;  
    195.     while(ol->n<10)  
    196.     {  
    197.         int e = rnd.Random(99);  
    198.         ol->Insert(e);  
    199.     }  
    200.     ol->Output();  
    201.     cout<<endl;  
    202.   
    203.     //搜索  
    204.     cout<<"=========搜索==========="<<endl;  
    205.     int index;  
    206.     cout<<"搜索有序表value数组中第5个元素如下:"<<endl;  
    207.     cout<<"value[5]="<<ol->value[5]<<endl;  
    208.     ol->Search(ol->value[5],index);  
    209.     cout<<"位置搜索结果为:"<<ol->link[index]<<endl;  
    210.     cout<<endl;  
    211.   
    212.     //删除  
    213.     cout<<"=========删除==========="<<endl;  
    214.     cout<<"删除有序表value数组中第5个元素如下:"<<endl;  
    215.     cout<<"value[5]="<<ol->value[5]<<endl;  
    216.     ol->Delete(ol->value[5]);  
    217.     ol->Output();  
    218.   
    219.     delete ol;  
    220.     return 0;  
    221. }  
         程序运行结果如图:


     

    0046算法笔记——【随机化算法】舍伍德随机化思想解决跳跃表问题

    分类: 算法   200人阅读  评论(0)  收藏  举报

         问题描述

         如果用有序链表来表示一个含有n个元素的有序集S,则在最坏情况下,搜索S中一个元素需要O(n)计算时间。提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能。在增设附加指针的有序链表中搜索一个元素时,可借助于附加指针跳过链表中若干结点,加快搜索速度。这种增加了向前附加指针的有序链表称为跳跃表。
         应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多少指针完全采用随机化方法来确定。这使得跳跃表可在O(logn)平均时间内支持关于有序集的搜索、插入和删除等运算。 

         例如:如图,(a)是一个没有附加指针的有序表,而图(b)在图(a)的基础上增加了跳跃一个节点的附加指针。图(c)在图(b)的基础上又增加了跳跃3个节点的附加指针。


        在跳跃表中,如果一个节点有k+1个指针,则称此节点为一个k级节点。以图(c)中跳跃表为例,看如何在改跳跃表中搜索元素8。从该跳跃表的最高级,即第2级开始搜索。利用2级指针发现元素8位于节点7和19之间。此时在节点7处降至1级指针进行搜索,发现元素8位于节点7和13之间。最后,在节点7降至0级指针进行搜索,发现元素8位于节点7和11之间,从而知道元素8不在搜索的集合S中。

        相关原理

         在一般情况下,给定一个含有n个元素的有序链表,可以将它改造成一个完全跳跃表,使得每一个k级结点含有k+1个指针,分别跳过2^k-1,2^(k-1)-1,…,2^0-1个中间结点。第i个k级结点安排在跳跃表的位置i2^k处,i>=0。这样就可以在时间O(logn)内完成集合成员的搜索运算。在一个完全跳跃表中,最高级的结点是级结点。

        完全跳跃表与完全二叉搜索树的情形非常类似。它虽然可以有效地支持成员搜索运算,但不适应于集合动态变化的情况。集合元素的插入和删除运算会破坏完全跳跃表原有的平衡状态,影响后继元素搜索的效率。

         为了在动态变化中维持跳跃表中附加指针的平衡性,必须使跳跃表中k级结点数维持在总结点数的一定比例范围内。注意到在一个完全跳跃表中,50%的指针是0级指针;25%的指针是1级指针;…;(100/2^(k+1))%的指针是k级指针。因此,在插入一个元素时,以概率1/2引入一个0级结点,以概率1/4引入一个1级结点,…,以概率1/2^(k+1)引入一个k级结点。另一方面,一个i级结点指向下一个同级或更高级的结点,它所跳过的结点数不再准确地维持在2^i-1。经过这样的修改,就可以在插入或删除一个元素时,通过对跳跃表的局部修改来维持其平衡性。 

         跳跃表中节点的级别在插入是确定,一旦确定便不再更改。下图是遵循上述原则的跳跃表的例子。对其进行搜索与对完全跳跃表所作的搜索是一样的。如果希望在所示跳跃表中插入一个元素8,则应现在跳跃表中搜索其插入位置。经搜索发现应在节点7和11之间插入元素8.此时在节点7和11之间增加1个存储元素8的新节点,并以随机的方式确定新节点的级别。例如,如果元素8是作为一个2级节点插入,则应对图中虚线相交的指针进行调整,如果新插入的节点是一个1级节点,则只要修改2个指针,虚线相交的指针是有可能被修改的指针,这些指针可在搜索元素插入位置时动态地保存起来,以供插入时使用


         在一个完全跳跃表中,具有i级指针的结点中有一半同时具有i+1级指针。为了维持跳跃表的平衡性,可以事先确定一个实数0<p<1,并要求在跳跃表中维持在具有i级指针的结点中同时具有i+1级指针的结点所占比例约为p。为此目的,在插入一个新结点时,先将其结点级别初始化为0,然后用随机数生成器反复地产生一个[0,1]间的随机实数q。如果q<p,则使新结点级别增加1,直至q>=p。由此产生新结点级别的过程可知,所产生的新结点的级别为0的概率为1-p,级别为1的概率为p(1-p),…,级别为i的概率为p^i(1-p)。如此产生的新结点的级别有可能是一个很大的数,甚至远远超过表中元素的个数。为了避免这种情况,用作为新结点级别的上界。其中n是当前跳跃表中结点个数。当前跳跃表中任一结点的级别不超过 

         算法具体实现如下:

         1、RandomNumber.h

    [cpp]  view plain copy
    1. #include"time.h"  
    2. //随机数类  
    3. const unsigned long maxshort = 65536L;  
    4. const unsigned long multiplier = 1194211693L;  
    5. const unsigned long adder = 12345L;  
    6.   
    7. class RandomNumber  
    8. {  
    9.     private:  
    10.         //当前种子  
    11.         unsigned long randSeed;  
    12.     public:  
    13.         RandomNumber(unsigned long s = 0);//构造函数,默认值0表示由系统自动产生种子  
    14.         unsigned short Random(unsigned long n);//产生0:n-1之间的随机整数  
    15.         double fRandom(void);//产生[0,1)之间的随机实数  
    16. };  
    17.   
    18. RandomNumber::RandomNumber(unsigned long s)//产生种子  
    19. {  
    20.     if(s == 0)  
    21.     {  
    22.         randSeed = time(0);//用系统时间产生种子  
    23.     }  
    24.     else  
    25.     {  
    26.         randSeed = s;//由用户提供种子  
    27.     }  
    28. }  
    29.   
    30. unsigned short RandomNumber::Random(unsigned long n)//产生0:n-1之间的随机整数  
    31. {  
    32.     randSeed = multiplier * randSeed + adder;//线性同余式  
    33.     return (unsigned short)((randSeed>>16)%n);  
    34. }  
    35.   
    36. double RandomNumber::fRandom(void)//产生[0,1)之间的随机实数  
    37. {  
    38.     return Random(maxshort)/double(maxshort);  
    39. }  
         2、7d3d3.cpp

    [cpp]  view plain copy
    1. //随机化算法 跳跃表  
    2. #include "stdafx.h"  
    3. #include "RandomNumber.h"  
    4. #include <cmath>  
    5. #include <iostream>  
    6. using namespace std;  
    7.   
    8. template<class EType,class KType> class SkipList;  
    9. template<class EType,class KType>  
    10. class SkipNode  
    11. {  
    12.     friend SkipList<EType,KType>;  
    13.     private:  
    14.         SkipNode(int size)  
    15.         {  
    16.             next = new SkipNode<EType,KType>*[size];  
    17.         }  
    18.         ~SkipNode()  
    19.         {  
    20.             delete []next;  
    21.         }  
    22.         EType data;//集合中的元素  
    23.         SkipNode<EType,EType> **next;//指针数组 next[i]是第i级指针  
    24. };  
    25.   
    26. template<class EType,class KType>  
    27. class SkipList  
    28. {  
    29.     public:  
    30.         SkipList(KType Large,int MaxE = 10000,float p = 0.5);  
    31.         ~SkipList();  
    32.         bool Search(const KType& k,EType& e) const;  
    33.         SkipList<EType,KType>& Insert(const EType& e);  
    34.         SkipList<EType,KType>& Delete(const KType& k,EType& e);  
    35.         void Output();  
    36.     private:  
    37.         int Level();  
    38.         SkipNode<EType,KType> *SaveSearch(const KType& k);  
    39.         int MaxLevel;                   //跳跃表级别上界  
    40.         int Levels;                     //当前最大级别  
    41.         RandomNumber rnd;               //随机数产生器  
    42.         float Prob;                     //用于分配节点级别  
    43.         KType TailKey;                  //元素键值上界  
    44.         SkipNode<EType,KType> *head;  //头结点指针  
    45.         SkipNode<EType,KType> *NIL;       //尾节点指针  
    46.         SkipNode<EType,KType> **last; //指针数组  
    47. };  
    48.   
    49. //构造函数  
    50. template<class EType,class KType>  
    51. SkipList<EType,KType>::SkipList(KType Large,int MaxE,float p)  
    52. {  
    53.     Prob = p;  
    54.     MaxLevel = ceil(log(float(MaxE))/log(1/p))-1;       //初始化跳跃表级别上界  
    55.     TailKey = Large;                            //元素键值上界  
    56.     Levels = 0;                                 //初始化当前最大级别  
    57.   
    58.     //创建头、尾节点和数组 last  
    59.     head = new SkipNode<EType,KType>(MaxLevel+1);  
    60.     NIL = new SkipNode<EType,KType>(0);  
    61.     last = new SkipNode<EType,KType> *[MaxLevel+1];  
    62.     NIL->data = Large;  
    63.   
    64.     //将跳跃表初始化为空表  
    65.     for(int i=0; i<=MaxLevel; i++)  
    66.     {  
    67.         head->next[i] = NIL;  
    68.     }  
    69. }  
    70.   
    71. //析构函数  
    72. template<class EType,class KType>  
    73. SkipList<EType,KType>::~SkipList()  
    74. {  
    75.     SkipNode<EType,KType> *next;  
    76.   
    77.     //删除所有节点  
    78.     while(head!=NIL)  
    79.     {  
    80.         next = head->next[0];  
    81.         delete head;  
    82.         head = next;  
    83.     }  
    84.   
    85.     delete NIL;  
    86.     delete []last;  
    87. }  
    88.   
    89. class element  
    90. {  
    91.     friend int main(void);  
    92.     public:  
    93.         operator long() const   
    94.         {  
    95.             return key;  
    96.         }  
    97.         element& operator = (long y)  
    98.         {  
    99.             key = y;  
    100.             return *this;  
    101.         }  
    102.     private:  
    103.         int data;  
    104.         long key;  
    105. };  
    106.   
    107. //搜索指定元素k  
    108. template<class EType,class KType>  
    109. bool SkipList<EType,KType>::Search(const KType& k,EType& e) const  
    110. {  
    111.     if(k>=TailKey)  
    112.     {  
    113.         return false;  
    114.     }  
    115.     //位置p恰好位于指定元素k之前  
    116.     SkipNode<EType,KType> *p = head;  
    117.     for(int i=Levels; i>=0; i--)//逐渐向下搜索  
    118.     {  
    119.         while(p->next[i]->data<k)//在第i级链中搜索  
    120.         {  
    121.             p = p->next[i];//每次搜索尽可能滴接近要搜索的元素  
    122.         }  
    123.     }  
    124.     e = p->next[0]->data;  
    125.     return (e==k);  
    126. }  
    127.   
    128. //搜索指定元素k,并将每一级中遇到的上一个节点存放在数组last中  
    129. template<class EType,class KType>  
    130. SkipNode<EType,KType> *SkipList<EType,KType>::SaveSearch(const KType& k)  
    131. {  
    132.     //位置p恰好位于指定元素k之前  
    133.     SkipNode<EType,KType> *p = head;  
    134.     for(int i = Levels; i>=0; i--)  
    135.     {  
    136.         while(p->next[i]->data<k)  
    137.         {  
    138.             p = p->next[i];  
    139.         }  
    140.         last[i] = p;    //上一个第i级结点  
    141.     }  
    142.     return (p->next[0]);  
    143. }  
    144.   
    145. //产生不超过MaxLevel 的随机级别  
    146. template<class EType,class KType>  
    147. int SkipList<EType,KType>::Level()  
    148. {  
    149.     int lev = 0;  
    150.     while(rnd.fRandom()<Prob)  
    151.     {  
    152.         lev++;  
    153.     }  
    154.     return (lev<=MaxLevel)?lev:MaxLevel;  
    155. }  
    156.   
    157. //插入指定元素e  
    158. template<class EType,class KType>  
    159. SkipList<EType,KType>& SkipList<EType,KType>::Insert(const EType& e)  
    160. {  
    161.     KType k = e;//取得元素键值  
    162.     if(k>=TailKey)  
    163.     {  
    164.         cout<<"元素键值超界!"<<endl;  
    165.         return *this;  
    166.     }  
    167.     //检查元素是否已存在  
    168.     SkipNode<EType,KType> *p = SaveSearch(k);  
    169.     if(p->data == e)  
    170.     {  
    171.         cout<<"元素已存在!"<<endl;  
    172.         return *this;  
    173.     }  
    174.   
    175.     //元素不存在,确定新节点级别  
    176.     int lev = Level();  
    177.     //调整个级别指针  
    178.     if(lev>Levels)  
    179.     {  
    180.         for(int i=Levels+1; i<=lev; i++)  
    181.         {  
    182.             last[i] = head;  
    183.         }  
    184.         Levels = lev;  
    185.     }  
    186.   
    187.     //产生新节点,并将新节点插入p之后  
    188.     SkipNode<EType,KType> *y = new SkipNode<EType,KType>(lev+1);  
    189.     y->data = e;  
    190.   
    191.     for(int i=0; i<=lev; i++)  
    192.     {  
    193.         //插入第i级链  
    194.         y->next[i] = last[i]->next[i];  
    195.         last[i]->next[i] = y;  
    196.     }  
    197.     return *this;  
    198. }  
    199.   
    200. //删除键值为k的元素,并将所删除的元素存入e  
    201. template<class EType,class KType>  
    202. SkipList<EType,KType>& SkipList<EType,KType>::Delete(const KType& k,EType& e)  
    203. {  
    204.     if(k>=TailKey)  
    205.     {  
    206.         cout<<"元素键值超界!"<<endl;  
    207.     }  
    208.     //搜索待删除元素  
    209.     SkipNode<EType,KType> *p = SaveSearch(k);  
    210.     if(p->data!=k)  
    211.     {  
    212.         cout<<"未找到待删除元素!"<<endl;  
    213.     }  
    214.     //从跳跃表中删除节点  
    215.     for(int i=0; i<=Levels && last[i]->next[i] == p; i++)  
    216.     {  
    217.         last[i]->next[i] = p->next[i];  
    218.     }  
    219.     //更新当前级别  
    220.     while(Levels>0 && head->next[Levels] == NIL)  
    221.     {  
    222.         Levels--;  
    223.     }  
    224.     e = p->data;  
    225.     delete p;  
    226.     return *this;  
    227. }  
    228.   
    229. //输出集合中的元素  
    230. template<class EType,class KType>  
    231. void SkipList<EType,KType>::Output()  
    232. {  
    233.     SkipNode<EType,KType> *y = head->next[0];  
    234.     for(;y!=NIL; y=y->next[0])  
    235.     {  
    236.         cout<<y->data<<' ';  
    237.     }  
    238.     cout<<endl;  
    239. }  
    240.   
    241. int main()  
    242. {  
    243.     SkipList<int,int> *s = new SkipList<int,int>(100,10,0.5);  
    244.   
    245.     //创建  
    246.     cout<<"=========创建==========="<<endl;  
    247.   
    248.     int a[] = {5,3,2,11,7,13,19,17,23};  
    249.   
    250.     for(int i=0; i<9; i++)  
    251.     {  
    252.         s->Insert(a[i]);  
    253.     }  
    254.     s->Output();  
    255.   
    256.     //搜索  
    257.     cout<<"=========搜索==========="<<endl;  
    258.     int k=17,e;  
    259.     cout<<"搜索元素k="<<k<<"如下:"<<endl;  
    260.     if(s->Search(17,e))  
    261.     {  
    262.         cout<<"位置搜索结果为:k="<<k<<",e="<<e;  
    263.     }  
    264.     cout<<endl;  
    265.   
    266.     //删除  
    267.     cout<<"=========删除==========="<<endl;  
    268.     cout<<"删除跳跃表元素k="<<k<<"剩余元素如下:"<<endl;  
    269.     s->Delete(k,e);  
    270.     s->Output();  
    271.   
    272.     delete s;  
    273.     return 0;  
    274. }  
        程序运行结果如图:



     

    0047算法笔记——【随机化算法】拉斯维加斯(Las Vegas)算法和n后问题

    分类: 算法   200人阅读  评论(0)  收藏  举报

          1、拉斯维加斯(Las Vegas)算法

         拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解,这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。与蒙特卡罗算法类似,拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例,用同一拉斯维加斯算法反复对该实例求解足够多次,可使求解失败的概率任意小。拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。

    [cpp]  view plain copy
    1. void obstinate(Object x, Object y)  
    2. {// 反复调用拉斯维加斯算法LV(x,y),直到找到问题的一个解y  
    3.     bool success= false;  
    4.     while (!success) success=lv(x,y);  
    5. }  

          设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0。设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间,则有。解此方程得:


         2、n后问题

         问题描速:在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。


         1)纯拉斯维加斯随机算法求解思路

          对于n后问题的任何一个解而言,每一个皇后在棋盘上的位置无任何规律,不具有系统性,而更象是随机放置的。在棋盘上相继的各行中随机地放置皇后,并注意使新放置的皇后与已放置的皇后互不攻击,直至n个皇后均已相容地放置好,或已没有下一个皇后的可放置位置时为止。

          具体实现代码如下:

         1、RandomNumber.h

    [cpp]  view plain copy
    1. #include"time.h"  
    2. //随机数类  
    3. const unsigned long maxshort = 65536L;  
    4. const unsigned long multiplier = 1194211693L;  
    5. const unsigned long adder = 12345L;  
    6.   
    7. class RandomNumber  
    8. {  
    9.     private:  
    10.         //当前种子  
    11.         unsigned long randSeed;  
    12.     public:  
    13.         RandomNumber(unsigned long s = 0);//构造函数,默认值0表示由系统自动产生种子  
    14.         unsigned short Random(unsigned long n);//产生0:n-1之间的随机整数  
    15.         double fRandom(void);//产生[0,1)之间的随机实数  
    16. };  
    17.   
    18. RandomNumber::RandomNumber(unsigned long s)//产生种子  
    19. {  
    20.     if(s == 0)  
    21.     {  
    22.         randSeed = time(0);//用系统时间产生种子  
    23.     }  
    24.     else  
    25.     {  
    26.         randSeed = s;//由用户提供种子  
    27.     }  
    28. }  
    29.   
    30. unsigned short RandomNumber::Random(unsigned long n)//产生0:n-1之间的随机整数  
    31. {  
    32.     randSeed = multiplier * randSeed + adder;//线性同余式  
    33.     return (unsigned short)((randSeed>>16)%n);  
    34. }  
    35.   
    36. double RandomNumber::fRandom(void)//产生[0,1)之间的随机实数  
    37. {  
    38.     return Random(maxshort)/double(maxshort);  
    39. }  
         2、7d4d1.cpp

    [cpp]  view plain copy
    1. //随机化算法 拉斯维加斯算法 n后问题  
    2. #include "stdafx.h"  
    3. #include "RandomNumber.h"  
    4. #include <cmath>  
    5. #include <iostream>  
    6. using namespace std;  
    7.   
    8. class Queen  
    9. {  
    10.     friend void nQueen(int);  
    11.     private:  
    12.         bool Place(int k);      //测试皇后k置于第x[k]列的合法性  
    13.         bool QueensLv(void);    //随机放置n个皇后拉斯维加斯算法  
    14.         int n;                  //皇后个数  
    15.         int *x,*y;              //解向量  
    16. };  
    17.   
    18. //测试皇后k置于第x[k]列的合法性  
    19. bool Queen::Place(int k)  
    20. {  
    21.     for(int j=1; j<k; j++)  
    22.     {  
    23.         if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))  
    24.         {  
    25.             return false;  
    26.         }  
    27.     }  
    28.     return true;  
    29. }  
    30.   
    31. //随机放置n个皇后的拉斯维加斯算法  
    32. bool Queen::QueensLv(void)  
    33. {  
    34.     RandomNumber rnd;       //随机数产生器  
    35.     int k = 1;              //下一个皇后的编号  
    36.     int count = 1;          //在一列中,可以放置皇后的个数  
    37.   
    38.     while((k<=n)&&(count>0))  
    39.     {  
    40.         count = 0;  
    41.         for(int i=1; i<=n; i++)  
    42.         {  
    43.             x[k] = i;//位置  
    44.             if(Place(k))  
    45.             {  
    46.                 y[count++] = i;  
    47.             }  
    48.         }  
    49.         if(count>0)  
    50.         {  
    51.             x[k++] = y[rnd.Random(count)];      //随机位置  
    52.         }  
    53.     }  
    54.   
    55.     return (count>0);        //count>0 表示放置成功  
    56. }  
    57.   
    58. //解n后问题的拉斯维加斯算法  
    59. void nQueen(int n)  
    60. {  
    61.     Queen X;  
    62.     X.n = n;  
    63.   
    64.     int *p = new int[n+1];  
    65.     for(int i=0; i<=n; i++)  
    66.     {  
    67.         p[i] = 0;  
    68.     }  
    69.     X.x = p;  
    70.     X.y = new int[n+1];  
    71.   
    72.     //反复调用随机放置n个皇后的拉斯维加斯算法,直到放置成功  
    73.     while(!X.QueensLv());  
    74.   
    75.     for(int i=1; i<=n; i++)  
    76.     {  
    77.         cout<<p[i]<<" ";  
    78.     }  
    79.     cout<<endl;  
    80.     delete []p;  
    81. }  
    82.   
    83. int main()  
    84. {  
    85.     int n=8;    
    86.     cout<<n<<"皇后问题的解为:"<<endl;    
    87.     nQueen(n);    
    88.     return 0;    
    89. }  
         程序运行结果如下:


         2)与回溯法结合的拉斯维加斯随机算法求解思路

         如果将上述随机放置策略与回溯法相结合,可能会获得更好的效果。可以先在棋盘的若干行中随机地放置皇后,然后在后继行中用回溯法继续放置,直至找到一个解或宣告失败。随机放置的皇后越多,后继回溯搜索所需的时间就越少,但失败的概率也就越大。 

      算法具体代码如下:

        1、RandomNumber.h如上

        2、7d4d1-2.cpp

    [cpp]  view plain copy
    1. //随机化算法 拉斯维加斯算法 n后问题  
    2. #include "stdafx.h"  
    3. #include "RandomNumber.h"  
    4. #include <cmath>  
    5. #include <iostream>  
    6. using namespace std;  
    7.   
    8. class Queen  
    9. {  
    10.     friend bool nQueen(int);  
    11.     private:  
    12.         bool Place(int k);                  //测试皇后k置于第x[k]的合法性  
    13.         bool Backtrack(int t);              //解n后问题的回溯法  
    14.         bool QueensLV(int stopVegas);       //随机放置n个皇后拉斯维加斯算法  
    15.         int n,*x,*y;  
    16. };  
    17.   
    18. //测试皇后k置于第x[k]列的合法性  
    19. bool Queen::Place(int k)  
    20. {  
    21.     for(int j=1; j<k; j++)  
    22.     {  
    23.         if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))  
    24.         {  
    25.             return false;  
    26.         }  
    27.     }  
    28.     return true;  
    29. }  
    30.   
    31. //解n后问题的回溯法  
    32. bool Queen::Backtrack(int t)  
    33. {  
    34.     if(t>n)  
    35.     {  
    36.         for(int i=1; i<=n; i++)  
    37.         {  
    38.             y[i] = x[i];//问题的解  
    39.         }  
    40.         return true;  
    41.     }  
    42.     else  
    43.     {  
    44.         for(int i=1; i<=n; i++)  
    45.         {  
    46.             x[t] = i;  
    47.             if(Place(t)&&Backtrack(t+1))  
    48.             {  
    49.                 return true;  
    50.             }  
    51.         }  
    52.     }  
    53.     return false;  
    54. }  
    55.   
    56.   
    57. //随机放置n个皇后拉斯维加斯算法  
    58. bool Queen::QueensLV(int stopVegas)  
    59. {  
    60.     RandomNumber rnd;       //随机数产生器  
    61.     int k = 1;  
    62.     int count = 1;  
    63.   
    64.     //1<=stopVegas<=n  
    65.     while((k<=stopVegas)&&(count>0))  
    66.     {  
    67.         count = 0;  
    68.         for(int i=1; i<=n; i++)  
    69.         {  
    70.             x[k] = i;  
    71.             if(Place(k))  
    72.             {  
    73.                 y[count++] = i;  
    74.             }  
    75.         }  
    76.   
    77.         if(count>0)  
    78.         {  
    79.             x[k++] = y[rnd.Random(count)];//随机位置  
    80.         }  
    81.     }  
    82.     return (count>0);        //count>0表示放置成功  
    83. }  
    84.   
    85. //与回溯法相结合的解n后问题的拉斯维加斯算法  
    86. bool nQueen(int n)  
    87. {  
    88.     Queen X;  
    89.       
    90.     //初始化X  
    91.     X.n = n;  
    92.   
    93.     int *p = new int[n+1];  
    94.     int *q = new int[n+1];  
    95.   
    96.     for(int i=0; i<=n; i++)  
    97.     {  
    98.         p[i] = 0;  
    99.         q[i] = 0;  
    100.     }  
    101.   
    102.     X.y = p;  
    103.     X.x = q;  
    104.   
    105.     int stop = 3;  
    106.     if(n>15)  
    107.     {  
    108.         stop = n-15;  
    109.     }  
    110.   
    111.     bool found = false;  
    112.     while(!X.QueensLV(stop));  
    113.   
    114.     //算法的回溯搜索部分  
    115.     if(X.Backtrack(stop+1))  
    116.     {  
    117.         for(int i=1; i<=n; i++)  
    118.         {  
    119.             cout<<p[i]<<" ";  
    120.         }  
    121.         found = true;  
    122.         cout<<endl;  
    123.     }  
    124.       
    125.     delete []p;  
    126.     delete []q;  
    127.     return found;  
    128. }  
    129.   
    130. int main()  
    131. {  
    132.     int n=8;    
    133.     cout<<n<<"皇后问题的解为:"<<endl;    
    134.     while(!nQueen(n));    
    135.     return 0;    
    136. }  
         程序运行结果如图:



    展开全文
  • 算法分析介绍随机化算法的课件 学习要点 理解产生伪随机数的算法 掌握数值随机化算法的设计思想 掌握蒙特卡罗算法的设计思想 掌握拉斯维加斯算法的设计思想 掌握舍伍德算法的设计思想
  • C++数值算法

    2014-08-01 09:47:41
    包含了当代科学计算过程中涉及的大量内容:求特殊函数值、随机数、排序、最优化、快速傅里叶变换、谱分析、小波变换、统计描述和数据建模、偏微分方程数值解、若干编码算法和任意精度计算等。
  • 概率算法(随机化算法

    千次阅读 2019-07-27 13:46:19
    概率算法也叫随机化算法。概率算法允许算法在执行过程中随机地选择下一个计算步骤。在很多情况下,算法在执行过程中面临选择时,随机性选择比最优选择省时,因此概率算法可以在很大程度上降低算法的复杂度。概率算法...
  • 控制部分的随机化是自然策略的基本概念 使用随机化可以通过付出很小的可靠性代价来显着提高效率。 快速随机算法比慢速确定性算法更可靠。 LSH算法 基于随机比特采样的LSH 我们的kNN算法 在汉明距离中查找k个近邻,而...
  • 随机化算法——遗传算法

    千次阅读 2018-03-18 13:24:06
    文中也简单提及了模拟退火算法。文章综合参考了一些互联网资料。发博客以备忘! 三:遗传算法 &nbsp; &nbsp; &nbsp; &nbsp; 照例先给出科学定义: &nbsp; &nbsp; &nbsp; &nbsp;...
  • 随机算法

    千次阅读 2018-05-17 08:35:26
    随机算法是一种在接受输入的同时,为了随机选择的目的,还接受一串随机比特流并且在运行过程中使用该比特流的算法(允许算法在执行过程中随机地选择下一个计算步骤)。 随机算法通常有两个优点: 较之那些我们所知...
  • 下面介绍一个用随机投点法计算圆周率的近似值的算法,利用圆与其外切正方形的面积之比来计算π的近似值。 题解思路: 半径为1的圆的1/4是一个扇形,是边长为1的正方形的一部分。k=πrr/4/rr=π/4;可得π=4k。这里用...
  • 第7章 随机化算法 概率算法只能实期望的结果更有效,它可能遭到最坏的可能性。 概率化算法两次运行的结果可能不一样。 1.主要类型: 数值概率算法、蒙特卡罗算法、拉斯维加斯算法、舍伍德算法 2....
  • 1、随机化算法  (1)描述:随机化算法是这样一种算法,在算法中使用了随机函数,且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。随机化算法基于随机方法,依赖于概率大小。  (2)分类:一般...