《理解产生伪随机数的算法掌握数值概率算法的设计思想掌握舍.ppt》由会员分享，可在线阅读，更多相关《理解产生伪随机数的算法掌握数值概率算法的设计思想掌握舍.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、理解产生伪随机数的算法掌握数值概率算法的设计思想掌握舍 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望理解产生伪随机数的算法理解产生伪随机数的算法掌握数值概率算法的设计思想掌握数值概率算法的设计思想掌握舍伍德算法的设计思想掌握舍伍德算法的设计思想掌握拉斯维加斯算法的设计思想掌握拉斯维加斯算法的设计思想掌握蒙特卡罗算法的设计思想掌握蒙特卡罗算法的设计思想学习要点2概率算法的特点1.当当算算法法执执行行过过程程中中面面临临选选择择时时，概概率率算算法法通通常比最优选择
2、算法省时。常比最优选择算法省时。2.对对所所求求问问题题的的同同一一实实例例用用同同一一概概率率算算法法求求解解两两次次，两两次次求求解解所所需需的的时时间间甚甚至至所所得得的的结结果果可能有相当大的差别。可能有相当大的差别。3.设计思想简单，易于实现。设计思想简单，易于实现。3概率算法的分类数值概率算数值概率算法法A A蒙特卡罗算法蒙特卡罗算法B B舍伍德算法舍伍德算法D D 拉斯维加斯算法拉斯维加斯算法C C4随机数随随机机数数在在概概率率算算法法设设计计中中扮扮演演着着十十分分重重要要的的角色。角色。在在现现实实计计算算机机上上无无法法产产生生真真正正的的随随机机数数，因因此此在在概概率
3、率算算法法中中使使用用的的随随机机数数都都是是一一定定程程度度上上随随机的，即机的，即伪随机数伪随机数。5随机数线线性性同同余余法法是是产产生生伪伪随随机机数数的的最最常常用用的的方方法法。由由线性同余法产生的随机序列线性同余法产生的随机序列a0,a1,an满足满足:其其中中b 0，c 0，d m。d称称为为该该随随机机序序列列的的种种子子。m应应取取充充分分大大，因因此此可可取取m为为机机器器大大数数，另另外外应应取取gcd(m,b)=1，因此可取，因此可取b为一素数。为一素数。6数值概率算法 7计算值 设设有有一一半半径径为为r的的圆圆及及其其外外切切四四边边形形。向向该该正正方方形形随随
4、机机地地投投掷掷n个个点点。设设落落入入圆圆内内的的点点数数为为k。由由于于所所投投入入的的点点在在正正方方形形上上均均匀匀分分布布，因因而而所所投投入入的的点点落落入入圆圆内内的的概概率率为为 。当当n足够大时，足够大时，k与与n之比就逼近这一概率：之比就逼近这一概率：8计算值 程序代码如下：程序代码如下：double Darts(int n)/用随机投点法计算用随机投点法计算 值值 static RandomNumber dart;int k=0;for(int i=1;i=n;i+)double x=dart.fRandom();double y=dart.fRandom();if(x*
5、x+y*y)=1)k+;return 4*k/double(n);9计算定积分设设f(x)是是0，1上的连续函数，且上的连续函数，且0 f(x)1。需需要要计计算算的的积积分分为为 ,积积分分I等等于于图图中中的的绿绿色色面积面积G。10计算定积分在在图图所所示示单单位位正正方方形形内内均均匀匀地地作作投投点点试试验验，则则随机点落在曲线下面的概率为随机点落在曲线下面的概率为 假假设设向向单单位位正正方方形形内内随随机机地地投投入入n个个点点(xi,yi)。如如果果有有m个个点点落落入入G内内，则则随随机机点点落落入入G内的概率内的概率11计算定积分 程序代码如下：程序代码如下：double
6、Darts(int n)/用随机投点法计算用随机投点法计算定积分定积分 static 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);12解非线性方程组求解下面的非线性方程组求解下面的非线性方程组其其中中，x1,x2,xn是是实实变变量量，fi是是未未知知量量x1,x2,xn的的非非线线性性实实函函数数。要要求求确确定定上上述述方方程程组组在在指指定定求求根范围内的一组解根范围内的一组解13注：一
7、般而言，概率算法费时，但设计思注：一般而言，概率算法费时，但设计思想简单，易实现。对于精度要求高的问题，想简单，易实现。对于精度要求高的问题，可以提供较好的初值。可以提供较好的初值。解非线性方程组 n线性化方法线性化方法n求函数极小值方法求函数极小值方法14解非线性方程组 在求根区域在求根区域D内，选定随机点内，选定随机点x0作为随机搜索的出发点。作为随机搜索的出发点。1.按按照照预预先先选选定定的的分分布布（正正态态分分布布、均均匀匀分分布布等等），逐逐个个选选取取随随机机点点xj，计计算算目目标标函函数数，满满足足精精度度要要求求的的随随机机点点就就是是近似解。近似解。2.在在算算法法的的
8、搜搜索索过过程程中中，假假设设第第j步步随随机机搜搜索索得得到到的的随随机机搜搜索索点点为为xj。在在第第j+1步步，生生成成随随机机搜搜索索方方向向和和步步长长，计计算算出出下下一一步步的的增增量量 xj。从从当当前前点点xj依依 xj得得到到第第j+1步步的的随随机机搜搜索索点点。当当(x)epsilon)&(j Steps)/计算随机搜索步长因子计算随机搜索步长因子 if(fx M)a/=k;success=false;for(int i=1;i n;i+)/计算随机搜索方向和增量计算随机搜索方向和增量 ri=2.0*rnd.fRandom()1;if(success)for(int i
9、=1;i=n;i+)dxi=a*ri;else for(int i=1;i=n;i+)dxi=a*ri;16解非线性方程组/计算下一个搜索点计算下一个搜索点 for(int i=1;i=n;i+)xi+=dxi;/计算目标函数值计算目标函数值 fx=f(x,n);if(fx tA(n)的可能性。的可能性。19舍伍德(Sherwood)算法注：当注：当s(n)与与tA(n)相比可忽略时，舍伍德算相比可忽略时，舍伍德算法可获得很好的平均性能法可获得很好的平均性能。舍伍德算法设计的基本思想舍伍德算法设计的基本思想 希望获得一个概率算法希望获得一个概率算法B B，用该算法，用该算法处理问题的输入，使得
10、对问题的输入规模处理问题的输入，使得对问题的输入规模为为n n的每一个实例均有的每一个实例均有20舍伍德(Sherwood)算法 这这两两种种算算法法的的核核心心都都在在于于选选择择合合适适的的划划分分基基准准。舍舍伍伍德德算算法法随随机机地地选选择择一一个个数数组组元元素素作作为划分基准。为划分基准。线性时间选择算法线性时间选择算法 快速排序算法快速排序算法21舍伍德(Sherwood)算法如如果果所所给给的的确确定定性性算算法法无无法法直直接接改改造造成成舍舍伍伍德德型型算算法法。此此时时可可借借助助于于随随机机预预处处理理技技术术，不不改改变变原原有有的的确确定定性性算算法法，仅仅对对其
11、其输输入入进进行行随随机机洗洗牌牌，同同样可收到舍伍德算法的效果。样可收到舍伍德算法的效果。如如，对对于于确确定定性性选选择择算算法法，可可以以用用下下面面的的洗洗牌牌算算法法shuffle将将数数组组a中中元元素素随随机机排排列列，然然后后用用确确定定性性选选择择算算法法求求解解。这这样样做做所所收收到到的的效效果果与与舍舍伍伍德德型型算法的效果是一样的。算法的效果是一样的。22舍伍德(Sherwood)算法Shuffle函数的代码：函数的代码：templatevoid Shuffle(Type a,int n)/随机洗牌算法随机洗牌算法 static RandomNumber rnd;fo
12、r(int i=0;i0。设。设t(x)是算法是算法obstinate找到找到具体实例具体实例x的一个解所需的平均时间的一个解所需的平均时间,s(x)和和e(x)分别分别是算法对于具体实例是算法对于具体实例x求解成功或求解失败所需的平求解成功或求解失败所需的平均时间，则有：均时间，则有：。解此方程可得：解此方程可得：31n后问题对对于于n后后问问题题的的任任何何一一个个解解而而言言，每每一一个个皇皇后后在在棋棋盘盘上上的的位位置置无无任任何何规规律律，不不具具有有系系统统性性，而而更更象象是是随随机机放放置置的的。由由此此容容易易想想到到拉拉斯斯维加斯算法维加斯算法。如如果果将将上上述述随随机
13、机放放置置策策略略与与回回溯溯法法相相结合，可能会获得更好的效果结合，可能会获得更好的效果。32n后问题可可以以先先在在棋棋盘盘的的若若干干行行中中随随机机地地放放置置皇皇后后，然然后后在在后后继继行行中中用用回回溯溯法法继继续续放放置置，直直至至找找到到一一个个解解或或宣宣告告失失败败。随随机机放放置置的的皇皇后后越越多多，后后继继回回溯溯搜搜索所需的时间就越少，但失败的概率也就越大。索所需的时间就越少，但失败的概率也就越大。stopVegaspset01.0000262.00-262.0050.503933.8847.2380.39120.046513.0010.20222.1133 给定
14、一个合数给定一个合数n n，求，求n n的一个非平凡因子的问题称为整的一个非平凡因子的问题称为整数数n n的因子分割问题。的因子分割问题。整数因子分解设设n1是是一一个个整整数数。关关于于整整数数n的的因因子子分分解解问问题题是是找出找出n的如下形式的唯一分解式：的如下形式的唯一分解式：。其其中中，p1p2pk是是k个个素素数数，m1,m2,mk是是k个个正正整整数数。如如果果n是是一一个个合合数数，则则n必必有有一一个个非非平平凡凡因子因子x，1xn，使得，使得x可以整除可以整除n。34整数因子分解int Split(int n)int m=floor(sqrt(double(n);for(
15、int i=2;i=m;i+)if(n%i=0)return i;return 1;事实上，算法事实上，算法split(n)split(n)是对范围在是对范围在1 1x x的所有整数进行的所有整数进行了试除而得到范围在了试除而得到范围在1 1x x2 2的任一整数的的任一整数的因子分割。因子分割。35Pollard算法 在在开开始始时时选选取取0n-1范范围围内内的的随随机机数数，然然后后递递归地由归地由 产生无穷序列产生无穷序列 对对于于i=2k，以以及及2k1)&(dn)coutdendl;if(i=k)y=x;k*=2;对对Pollard算算法法更更深深入入的的分分析析可可知知，执执行行
16、算算法法的的while循循 环环 约约 次次 后后，Pollard算算法法会会输输出出n的的一一个个因因子子p。由由于于n的的最最小小素素因因子子p ，故故Pollard算算法法可可在在O(n1/4)时时间间内内找到找到n的一个素因子。的一个素因子。37蒙特卡罗(Monte Carlo)算法设设p是是一一个个实实数数，且且1/2pn/2时，称元素x是数组T的主元素。templatebool Majority(Type*T,int n)/判定主元素的蒙特卡罗算法 int i=rnd.Random(n)+1;Type x=Ti;/随机选择数组元素 int k=0;for(int j=1;jn/2)
17、;/kn/2 时T含有主元素templatebool MajorityMC(Type*T,int n,double e)/重复调用算法Majority int k=ceil(log(1/e)/log(2);for(int i=1;i0，算法majorityMC重复调用log(1/)次算法majority。它是一个偏真蒙特卡罗算法，且其错误概率小于。算法majorityMC所需的计算时间显然是O(nlog(1/)。43素数测试WilsonWilson定理定理定理定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)!-1(mod n)。void power(unsigned int a
18、,unsigned int p,unsigned int n,unsigned int&result,bool&composite)/计算mod n，并实施对n的二次探测 unsigned int x;if(p=0)result=1;else power(a,p/2,n,x,composite);/递归计算 result=(x*x)%n;/二次探测 if(result=1)&(x!=1)&(x!=n-1)composite=true;if(p%2)=1)/p是奇数 result=(result*a)%n;费尔马小定理费尔马小定理费尔马小定理费尔马小定理：如果p是一个素数，且0ap，则ap-1(
19、mod p)。二次探测定理二次探测定理二次探测定理二次探测定理：如果p是一个素数，且0 xp，则方程x21(mod p)的解为x=1，p-1。44bool Prime(unsigned int n)/素数测试的蒙特卡罗算法 RandomNumber rnd;unsigned int a,result;bool composite=false;a=rnd.Random(n-3)+2;power(a,n-1,n,result,composite);if(composite|(result!=1)return false;else return true;算法prime是一个偏假3/4正确的蒙特卡罗算法。通过多次重复调用错误概率不超过(1/4)k。这是一个很保守的估计，实际使用的效果要好得多。45