《随机算法简单介绍》由会员分享，可在线阅读，更多相关《随机算法简单介绍（29页珍藏版）》请在金锄头文库上搜索。
1、随机算法第七组第二次小组作业随机算法起源可以追溯到20世纪40年代中叶。 当时 Monte Carlo在进行数值计算时， 提出通过统计模拟或 抽样得到问题的近似解， 而且出现错误的概率随着实 验次数的增多而显著地减少， 即可以用时间来换取求 解正确性的提高。什么是随机算法?设有一含有n个未知量的函数表达式f（x1,x2.xn）， 要判断f在某一区域D中是否恒为0。通常做法：将f进行数学化简后在进行判断。但是！ 如果f不可以进行数学化简呢？Ps：f不能化简在实际情况中是很可能出现的。举个例子如果我们随机地产生一个n维的坐标 (r1，r2. rn) 属于 D, 代入f得f（r1，r2 rn）0，则
2、 可断定在区域D内f0。 如果f（r1，r2， rn）0，则 有两种可能： 1.在区域D内f0 2.在区域D内f0，得到上述结果只是巧合。于是就有了随机的思想如果我们对很多个随机产生的坐标进行测试，结果次 次均为0， 我们就可以断言f0的概率是非常之小的。在随机算法中不要求对同一输入算法每次执行时给出 相同的结果。 我们所关心的是算法在执行时，是否能 够产生真正随机的结果。最后将这些随机结果进行分 析，得出结论。因此我们可以这样做1）Random Sampling问题设给定n个元素（为简单起见，设为1，2n）， 要 求从n个数中随机地选取m个数（mn）。常规解法： 用一个长为m的数组，来存放产
3、生的随机数。产生一 个数后，看其是否在数组中： 若不在则将其加入，若 已在则抛弃该数，再去产生下一个数。看。一个例题。So easy！优化：建立一个长度为n的数组用下标i代表数字，bi 中来标记是否被选过。So easy这道题关键其实是在于如何随机的选 出m个数。 想到如何解决了吗？大家是否还记得上一次我们小组的小组作业？ 水王问题。 最后我们的组长有延伸这道题目。就是当发帖数 目太大，大到无法记录的时候怎么办？于是组长大人想到了一个好办法，随机取出一部分， 计算出其中的水王，反复进行多次，选错水王的概率 就会越来越低。 这其实就是随机算法。那么又如何随机的选出一部分呢？通过例子和例题可以看出
4、，这些解法都有一个共同 点。就是都包含随机数的生成。 在机械工业出版社出版的算法导论中有很好很强 大的概括：那么到底什么是随机算法?随机算法就是包含随机数生成器的算法。 很好理解能生成随机数的就是随机数生成器呗。 。 但是，重点不在这里。 那重点是什么？什么是随机数生成器？数学上是这样定义随机数的：在连续型随机变量的分 布中，最简单而且最基本的分布是单位均匀分布。由 该分布抽取的简单子样称为随机数序列，其中每一个 体称为随机数。首先提问什么是随机数？ 其实没那么 复杂。将n个标有序号的无差别的球（序号不重复），放入到 一个不透明容器里，随机有放回的抽取几个球，记录产 生的序号，这样的一列数就是
5、随机数列，而其中的每一 个数，就是随机数了。举个例子81,6,9,16随机数列随机数在用随机算法解决问题时，都会要求随机的产生一些 数，那产生随机数很难吗？按照随机数的产生方式，随机数列可以分为两类：真 随机数列和伪随机数列。听起来很简单？其实又没那么简单。 。1）伪随机数序列 伪随机数序列由数学公式计算所产生。实质上，伪随 机数并不随机，序列本身也必然会重复，但由于它可 以通过不同的设计产生满足不同要求的序列且可以复 现因而得到广泛的应用。 2）真随机数列 利用物理方法选取自然随机性产生的随机数可以看作 真随机数。生成随机数。目前已经出现了多种随机数生产生方法，主要有以下 三种 1人工方法
6、通过拋硬币、扔骰子等方法获得随机序 列。由这类方法产生的随机序列具有高度的随机性， 但是这种方法效率极低。常用的随机数生成方法 2利用计算机生成伪随机数 这是最常见的随机序 列产生方法，它是基于“随即种子”产生的。由计 算机算法来获得的随机序列是有规律可循的，所以 其安全性较差。 3通过检测随机噪声源来获取真随机数 产生真随机 数需要熵源即随机源，目前熵源一般是通过检测放 射性衰变、粒子轨迹、电子电路噪声、大气噪声、 机械振动噪声、电子振荡器频率抖动等物理噪声来 获取的。随机算法关键显而易见。如何用计算机产生伪随机数随机数在计算机生成中通常都是用迭代算法 通过将n带入迭代公式计算出n+1；那迭
7、代公式如何确定？是由冯诺依曼提出的。它的实现方法为：首先任取一 个非0的2m位的数，用它中间的m位数码作为所生成的 伪随机序列的第一个元素，然后将该数做平方运算， 得到一个新的2m位的数，取其中间m位作为伪随机序 列的第二个元素，依次进行。当取十进制时，用公式 可表示为：平方取中法这种方法比较容易实现，但是它的周期受初始值的影 响很大，初始值选得不好，会严重影响随机数序列的 质量和周期。 而且存在周期退化问题，这种平方取中法并不是生成 伪随机序列的好方法。它的缺点在于这样产生的序列 中很容易出现重复元素的短循环，而且，一旦某一个 元素是0，则后面所有的元素都将是0在伪随机数的产生方式中最常见的
8、就是线性同余法， 生成公式：其中： m，模数；m0 a， 乘数；0 a m c， 增量；0 c m X0，初始值，种子；0 X0m线性同余法 如果这些参数和种子(初值)都指定，序列也就确定下 来了。当模数M足够大时，用线性同余法产生的随 机数在区间（0，1）很密集，而且接近均匀分布， 其随机数序列具有较好的统计特性。 但是模数m取得较大，序列的周期才可能较大。容 易看出，线性同余发生器有长周期相关现象。在应 用中，我们应特别警惕和回避这种现象。 Fibonacci方法也是产生随机数的一种常用方法，它 只要两个初值和一个模数即可，其递推公式如下所 示：Fibonacci序列 从公式可以看出，用此方法产生的随机数序列周期为 3M/2，而且没有乘法运算，因此其生成速度非常快， 物理实现也十分简单。 然而此发生器存在着两个致命的缺陷：1）产生的随机数序列有着令人不能容忍的不居中现 象，即用前两个随机数得到第三个随机数不是同时大 于就是同时小于前两个而永不居中。 2）产生的序列有明显的相关性，即取小值的数后面 出现也取小值的趋势。 所有这些都说明它不是一个好 的随机数序列。 除了上面这些算法之外，还有许多其他方法来产生 随机数，如混沌映射法、逆 同余法、无理数变换法 等，当今的主流还是线性同余法、线性反馈寄存器 法、混 沌映射法和线性同余组合法这几种方法及其 改进。谢谢
