10_概率算法

10_概率算法null回顾算法的重要特征回顾算法的重要特征确定性、能行性、输入、输出、有穷性/有限性确定性：算法对所有可能的输入，都必须能够得到正确的答案。但是有很多确定性的算法，其性能很坏。特别是有很多具有很好的平均运行时间的算法，在最坏的情况下，却具有很坏的性能。“算法对所有可能的输入都必须给出正确的答案”这一条件可否放宽？概率算法或随机算法，允许在某些方面它可能是不正确的，但是由于出现这种不正确的可能性很小，以致可以安全地不予理睬。null概率算法概率算法概率算法1 概述 2 伪随机数的产生 3 数值概率算法 4 图搜...

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

                    本文档为【10_概率算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

10_概率算法

你可能还喜欢