算法设计与分析第7章概率算法

《算法设计与分析第7章概率算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章随机算法1学习要点了解随机算法的基本特征理解产生伪随机数的算法掌握数值随机化算法的设计思想掌握舍伍德算法的设计思想掌握拉斯维加斯算法的设计思想掌握蒙特卡罗算法的设计思想2概述前面各章讨论的算法的每一个步骤都是确定的，而本章讨论的随机算法允许算法在执行过程中随机地选择一下计算步骤。在许多情况下，一般算法比较复杂，性能较差，很多具有很好平均运行时间的算法，在最坏的情况下，却具有很坏的性能。由于随机性选择比最优选择省时间，因此引入随机化算法可以在很大程度上降低算法的复杂度。3很早以前就被人们所发现和

2、利用。17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。19世纪人们用投针试验的方法来决定π。高速计算机的出现，使得用数学方法在计算机上大量模拟这样的试验成为可能。4从Buffon(蒲丰)投针问题谈起56试验者时间(年)针长投针次数相交次数π的估计值Wolf18500.80500025323.15956Smith18550.60320412183.15665Fox18840.7510304893.15951Lazzarini19250.83340818083.141592927概述随机算

3、法对所求解问题的同一个实例用同一随机算法求解两次可能得到完全不同的效果。这两次求解所需要的时间，甚至所得到的结果都可能会有相当大的差别。包括数值概率算法蒙特卡罗（MonteCarlo）算法拉斯维加斯（LasVegas）算法舍伍德（Sherwood）算法8数值概率算法常用于数值问题的求解。将一个问题的计算与某个概率分布已经确定的事件联系起来，求问题的近似解。这类算法所得到的往往是近似解，且近似解的精度随计算时间的增加而不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此可以用数值随机

4、化算法得到相当满意的解。蒙特卡罗算法用于求问题的准确解，但得到的解未必是正确的。蒙特卡罗算法以正的概率给出正解，求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。一般给定执行步骤的上界，给定一个输入，算法都是在一个固定的步数内停止的。随机算法的分类9舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可在这个确定性算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的

5、这种差别（精髓所在）。拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时可能找不到解。拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任意实例，用同一拉斯维加斯算法反复对它求解，可以使求解失效的概率任意小。随机算法的分类107.1随机数117.1随机数随机数在随机化算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在随机化算法中使用的随机数都是一定程度上随机的，即伪随机数。线性同余法是产生伪随机数的最常

6、用的方法。由线性同余法产生的随机序列a0,a1,…,an，满足：(混合同余法)其中b0，c0，dm。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容，已超出本书讨论的范围。从直观上看，m应取得充分大，因此可取m为机器大数。12d=1种子m=11b=6c=0(1,6,3,7,9,10,5,8,4,2,1,6,3)13复杂一些的生成器Multiplerecursivegenerator14算法实现许多程序语言中都自带生成随机数的

7、方法，如c中的random()函数，Matlab中的rand()函数等。但这些生成器生成的随机数效果很不一样，比如c中的函数生成的随机数性质就比较差，如果用c，最好自己再编一个程序。Matlab中的rand()函数，经过了很多优化。可以产生性质很好的随机数，可以直接利用。15下面用计算机产生的伪随机数来模拟抛硬币实验。假设抛10次硬币构成一个事件。调用Random(2)返回一个二值结果。返回0表示抛硬币得到反面，返回1表示得到正面。下面的算法TossCoins模拟抛10次硬币这一事件50000次。用

8、head[i](0i10)记录这50000此模拟恰好得到i次正面的次数。最终输出模拟抛硬币事件得到正面事件的频率图，如下图所示：160*1*2*3*4*5*6*7*8*9*10*模拟抛硬币得到的正面事件频率图17voidmain(void){//模拟随机抛硬币事件constintNCOINS=10;constlongNTOSSES=50000L;//heads[i]是得到i次正面的次数longi,heads[NCOINS+1];intj,position;//初始