11第10章概率算法?学习要点?理解产生伪随机数的算法?掌握数值概率算法的设计思想?掌握蒙特卡罗算法的设计思想?掌握拉斯维加斯算法的设计思想?掌握舍伍德算法的设计思想22引言?前面几张所讨论的分治、动态规划、贪心法、回溯和分支限界等算法的每一计算步骤都是确定的，本章所讨论的概率算法允许执行过程中随机选择下一计算步骤。?在多数情况下，当算法在执行过程中面临一个选择是，随机性选择常比最优选择省时，因此概率算法可在很大程度上降低算法复杂性。?概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果(所需时间或计算结果)。?本章将要介绍的概率算法包括：?数值概率算法求解数值问题的近似解，精度随计算时间增加而不断提高?舍伍德算法消除算法最坏情形行为与特定势力之间的关联性，并不提高平均性能，也不是刻意避免算法的最坏情况行为?拉斯维加斯算法求解问题的正确解，但可能找不到解?蒙特卡罗算法求解问题的准确解，但这个解未必正确，且一般情况下无法有效判定正确性33随机数?随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。?线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,…,an满足?其中b0，c0，dm。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容，已超出本书讨论的范围。从直观上看，m应取得充分大，因此可取m为机器大数，另外应取gcd(m,b)=1，因此可取b为一素数。?????????,2,1mod)(10nmcbaadann44数值概率算法?一、用随机投点法计算π值?二、计算定积分?三、解非线性方程组55一、用随机投点法计算π值?设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为。所以当n足够大doubleDarts(intn){//用随机投点法计算值staticRandomNumberdart;intk=0;for(inti=1;ivoidShuffle(Typea[],intn){//随机洗牌算法staticRandomNumberrnd;for(inti=0;i0。?设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有：?解此方程可得：))()())((1()()()(xtxexpxsxpxt????)()()(1)()(xexpxpxsxt???1616一、n后问题?对于n后问题的任何一个解而言，每一个皇后在棋盘上的位臵无任何规律，不具有系统性，而更象是随机放臵的。由此容易想到下面的拉斯维加斯算法。?在棋盘上相继的各行中随机地放臵皇后，并注意使新放臵的皇后与已放臵的皇后互不攻击，直至n个皇后均已相容地放臵好，或已没有下一个皇后的可放臵位臵时为止。?如果将上述随机放臵策略与回溯法相结合，可能会获得更好的效果。可以先在棋盘的若干行中随机地放臵皇后，然后在后继行中用回溯法继续放臵，直至找到一个解或宣告失败。随机放臵的皇后越多，后继回溯搜索所需的时间就越少，但失败的概率也就越大。stopVegaspset01.0000262.00--262.0050.503933.8847.2380.39120.046513.0010.20222.111717二、整数因子分解?设n>1是一个整数。关于整数n的因子分解问题是找出n的如下形式的唯一分解式：?其中，p11)&&(dn/2时，称元素x是数组T的主元素。?对于任何给定的?>0，MajorityMC算法重复调用?log(1/?)?次算法Majority。它是一个偏真蒙特卡罗算法，且其错误概率小于。MajorityMC算法所需的计算时间显然是O(nlog(1/?))。templateboolMajority(Type*T,intn){//判定主元素的蒙特卡罗算法inti=rnd.Random(n