概率算法的介绍与分析.docVIP

算法分析与设计课程课外学习论文 概率算法的介绍与分析 摘要： 关键词： 一、引言 二、 产生随机数的机制 随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。产生随机数最常用的方法是线性同余法。 由线性同余法产生的随机序列a1,a2,...,an满足 其中,b=0, c=0, d=m。d称为该随机序列的种子。当a，c，m确定后，随着d的不同产生不同的随机数列，为了使随机数数列的随机性能好，我们通常取m充分大的素数，而且取gcd(m，a)=1。 蒙特卡洛算法 如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。对于一个一致的p正确蒙特卡罗算法，要提高获得正确解的概率，只要执行该算法若干次，并选择出现频次最高的解即可。 例：主元素问题 设T[1:n]是一个含有n个元素的数组。当|{i|T[i]=x}|n/2时，称元素x是数组T的主元素。 判断所给数组是否含有主元素。 对于任何给定的ε0，算法majorityMC重复调用?log(1/ε)? 次算法majority。它是一个偏真蒙特卡罗算法，且其错误概率小于ε。算法majorityMC所需的计算时间显然是O(nlog(1/ ε))。 源码见附录一。 拉斯维加斯算法 拉斯维加斯算法思想： void obstinate(Object x, Object y) {// 反复调用拉斯维加斯算法LV(x,y)，直到找到问题的一个解y bool success= false; while (!success) success=lv(x,y); } 例：n 皇后问题 n 皇后问题：在n×n 格的棋盘上放置彼此不受攻击的n 个皇后．按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子．n 皇后问题等价于在n×n 格的棋盘上放置n个皇后，任何2 个皇后不放在同一行或同一列或同一斜线上． 对于n 皇后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更像是随机放置 的．由此想到可采用拉斯维加斯算法，在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n 个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止． 方法queensLV ( ) 实现在棋盘上随机放置n个皇后的拉斯维加斯算法． 通过反复调用随机放置n 个皇后的拉斯维加斯算法queensLV ( )，直至找到n 皇后问题的一个解． 源码见附录二 四、算法比较 五、学习心得和体会（黑体小四号两端对齐） 把随机性注入到算法中，使得算法设计与分析的灵活性及解决问题的能力大为改观 参考文献：（黑体小四号两端对齐） templateclass Type bool Majority(Type *T, int n) {// 判定主元素的蒙特卡罗算法 int i=rnd.Random(n)+1; Type x=T[i]; // 随机选择数组元素 int k=0; for (int j=1;j=n;j++) if (T[j]==x) k++; return (kn/2); // kn/2 时T含有主元素 } templateclass Type bool MajorityMC(Type *T, int n, double e) {// 重复调用算法Majority int k=ceil(log(1/e)/log(2)); for (int i=1;i=k;i++) if (Majority(T,n)) return true; return false; } 附录二：n皇后问题源码： private static Boolean queensLV ( ) { //随机放置n 个皇后的Las Vegas 算法 rnd=new Random ( ); int k=1; int count=1; while ((k=n) (count0)) { count=0; int j=0; for ( int i=1; i=n; i++ ) { x k =i; if (place (k)) if (rnd.random ++count) ==0) j=i; //随机位置 } if (count0) x k++ =j; } return (count0); // count0 表示放置成功 } public static void nQueen { //解n 皇后问题的Las Vegas 算法 //初始化x