随机算法(数值概率舍伍德)

《随机算法(数值概率舍伍德)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章随机算法学习要点了解随机算法的基本特征理解产生伪随机数的算法掌握数值随机化算法的设计思想掌握舍伍德算法的设计思想掌握拉斯维加斯算法的设计思想掌握蒙特卡罗算法的设计思想随机算法的基本特征前面各章讨论的算法的每一个步骤都是确定的，而本章讨论的随机算法允许算法在执行过程中随机地选择一下计算步骤。在许多情况下，一般算法比较复杂，性能较差，很多具有很好平均运行时间的算法，在最坏的情况下，却具有很坏的性能。由于随机性选择比最优选择省时间，因此引入随机化算法可以在很大程度上降低算法的复杂度。随机算法的基本特征随机算法对所求解问题的同一个实例用同一随机算法求解两次可能得到完全不同的效

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

3、间。算法所用的时间越多，得到正确解的概率就越高。一般给定执行步骤的上界，给定一个输入，算法都是在一个固定的步数内停止的。随机算法的分类舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可在这个确定性算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别（精髓所在）。拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时可能找不到解。拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任意实例，用同

4、一拉斯维加斯算法反复对它求解，可以使求解失效的概率任意小。随机算法的分类7.1随机数7.1随机数随机数在随机化算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在随机化算法中使用的随机数都是一定程度上随机的，即伪随机数。线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,…,an，满足：其中b0，c0，dm。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容，已超出本书讨论的范围。从直观上看，m应取得充分大，因此可取m为机器大数。为了在设计概率算法时便于

5、产生所需的随机数，建立一个随机数类RandomNumber。该类包含一个需有用户初始化的种子randseed。给定初始种子后，即可产生与之相应的随机序列。种子seed是一个无符号长整型数，可由用户选定也可用系统时间自动产生。函数Random的输入参数n65536是一个无符号整形数，返回[0，n-1]范围内的一个随机整数。函数fRandom()返回[0，1]内的一个随机实数。//随机数类Constunsignedlongmaxshort=64436L;Constunsignedlongmultiplier=1194211693L;Constunsignedlongadder

6、=12345L;classRandomNumber{private://当前种子unsignedlongrandSeed;public://构造函数，默认值0表示由系统自动产生种子RandomNumber(unsignedlongs=0);//产生0到n-1之间的随机整数unsignedshortRandom(unsignedlongn);//产生[0,1)之间的随机实数doublefRandom(void);}函数Random在每次计算时，用线性同余式计算新的种子randSeed。它的高16位的随机性较好。将randSeed右移16位得到一个0~65535间的随机整数，然

7、后再将此随机整数映射到0~（n-1）范围内。对于函数fRandom，先用函数Random(maxshort)产生一个0~（maxshort-1）之间的整形随机序列，将每个整型随机数除以maxshort，就得到[0,1）区间中的随机实数。//产生种子RandomNumber::RandomNumber(unsignedlongs){if(s==0)randSeed=time(0);//用系统时间产生种子elserandSeed=s;//由用户提供种子}//产生0~n-1之间的随机数UnsignedshortRando