10_概率算法.ppt

回顾算法的重要特征 确定性、能行性、输入、输出、有穷性/有限性 概率算法 1 概述 前面描述算法的每一计算步骤都是确定的。有时面临选择时需要按照策略进行取舍。 1 概述 数值概率算法 得到近似解；精度随着计算时间增加而提高。 1 概述 蒙特卡罗算法 用于求问题的准确解。对于很多问题来说，近似解毫无意义。例如对判定问题，或“是”或“否”，必居其一。 缺点：用该算法能求得问题的一个解，但这个解未必是正确的。无法有效地判定所得到的解是否肯定正确。 2 伪随机数的产生 随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。 3 数值概率算法-求pi 设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 。所以当n足够大时，k与n之比就逼近这一概率。从而 3 数值概率算法-计算定积分 设f(x)是[0,1]上的连续函数，且0 ? f(x) ? 1。 需要计算的积分为 ,积分I等于图中的面积G。 3 数值概率算法-计算定积分 double Darts(int n) { // 用随机投点法计算定积分 staic RandomNumber dart; int k=0; for (int i=1;i =n;i++) { double x=dart.fRandom(); double y=dart.fRandom(); if (y=f(x)) k++; } return k/double(n); } 4 图有哪些信誉好的足球投注网站的概率算法 对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。由此容易想到下面的Las Vegas算法。 4 图有哪些信誉好的足球投注网站的概率算法 stopVegas：随机摆放的皇后的个数； p：随机摆放的皇后无冲突的概率； s：一次成功有哪些信誉好的足球投注网站访问的结点的平均数； e：一次不成功有哪些信誉好的足球投注网站访问的结点的平均数； t：反复调用算法使得最终找到一个解所访问的结点数平均值t = s+e*(1-p)/p。 5 蒙特卡罗算法 蒙特卡罗算法在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。 5 蒙特卡罗算法-素数测试 Wilson定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)!? -1(mod n)。 费尔马小定理：如果p是一个素数，且0ap，则ap-1 ?1(mod p)。 二次探测定理：如果p是一个素数，且0xp，则方程x2?1(mod p)的解为x=1，p-1。 * * 确定性：算法对所有可能的输入，都必须能够得到正确的答案。 但是有很多确定性的算法，其性能很坏。特别是有很多具有很好的平均运行时间的算法，在最坏的情况下，却具有很坏的性能。 “算法对所有可能的输入都必须给出正确的答案”这一条件可否放宽？ 概率算法或随机算法，允许在某些方面它可能是不正确的，但是由于出现这种不正确的可能性很小，以致可以安全地不予理睬。 概率算法 1 概述 2 伪随机数的产生 3 数值概率算法 4 图有哪些信誉好的足球投注网站的概率算法 5 蒙特卡罗算法 概率算法特征：对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。 概率算法：允许算法在面临选择时“随机”选择下一步计算。 随机选择的好处？ 降低复杂度。 不存在近似解的问题 算法确定返回一个解，但不保证是正确解。 不一定找到解，但一旦找到、保证是正确的。 确定得到正确解。 拉斯维加斯算法 不会得到不正确的解。有时会找不到解，一旦用这类算法找到一个解，这个解就一定是正确解。 舍伍德(Sherwood)算法 总能求得问题的一个解，且所求得的解总是正确的。 其中b=0，c=0，d=m。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。 m应取得充分大，应取gcd(m,b)=1，可取b为一素数。 线性同余法是产生伪随机数的最常用方法。由线性同余法产生的随机序列a0,a1,…,an满足： double Darts(int n) { // 用随机投点法计算pi值 staic RandomNumber dart; int k=0; for (int i=1;i =n;i++) { double x=dart.fRandom(); double y=dart.fRandom(); if ((x*x+y*y)=1)