文档介绍：第7章概率算法概述概率算法,允许算法在执行的过程中随机选择下一个计算步骤。许多情况下,当算法在执行过程中面临一个选择时,随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。数值概率算法舍伍德算法拉斯维加斯算法蒙特卡罗算法(近似解)(总能求到正确的解)(可能得不到解,但是得到的解一定是正确的)(能求到问题的解,但求到的解未必正确)所谓概率算法,就是在算法的过程中引入随机数,使得算法在执行的过程中随机选择下一个计算步骤。不确定性随机数随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数,因此在概率算法中使用的随机数都是一定程度上随机的,即伪随机数。伪随机数是指用数学递推公式所产生的随机数。线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,…,an满足其中b0,c0,dm。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。从直观上看,m应取得充分大,因此可取m为机器大数,另外应取gcd(m,b)=1,因此可取b为一素数。数值概率算法数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下,要计算出问题的精确解是不可能或没有必要的,因此用数值概率算法可得到相当满意的解。用随机投点法计算∏值设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布,因而所投入的点落入圆内的概率为。所以当n足够大时,k与n之比就逼近这一概率。从而。