中国数学建模-编程交流-概率算法简介

《中国数学建模-编程交流-概率算法简介》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中国数学建模-编程交流-概率算法简介.txt﹃根网线''尽赚了多少人的青春い有时候感动的就是身边微不足道的小事。﹎破碎不是最残酷的最残酷的是踩着这些碎片却假装不疼痛固执的寻找﹎将来就算我遇见再怎么完美的人,都有一个缺点,他不是你,_____下辈子要做男生，娶一个像我这样的女生。中国数学建模-编程交流-概率算法简介├数学思想├编程交流├学术杂谈├EnglishFans登录注册搜索风格论坛状态论坛展区社区服务社区休闲网站首页我能做什么>>VC++,C,Perl,Asp...编程学习,算法介绍.中国数学建模→学术区→编程交流→概率算法简介您是本帖的第10

2、10个阅读者*贴子主题：概率算法简介b等级：职业侠客文章：470积分：956门派：黑客帝国注册：2003-8-28鲜花(0)鸡蛋(0)楼主概率算法简介很多算法的每一个计算步骤都是固定的，而在下面我们要讨论的概率算法，允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下，可将

3、概率算法大致分为四类:数值概率算法，蒙特卡罗（MonteCarlo）算法，拉斯维加斯（LasVegas）算法和舍伍德（Sherwood）算法。数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到相当满意的解。蒙特卡罗算法用于求问题的准确解。对于许多问题来说，近似解毫无意义。例如，一个判定问题其解为“是”或“否”，二者必居其一，不存在任何近似解答。又如，我们要求一个整数的因子时所给出的解答必须是准确的，一个整数的近似因

4、子没有任何意义。用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点就在于此。一般情况下，无法有效判断得到的解是否肯定正确。拉斯维加斯算法不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似。拉斯维加斯算法得到正确解的概率随着它用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。舍伍德算法总

5、能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。本文简要的介绍一下数值概率算法和舍伍德算法。首先来谈谈随机数。随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。产生随机数最常用的方法是线性同余法。由线

6、性同余法产生的随机序列a1,a2,...,an满足a0=dan=(ban-1+c)modmn=1,2.......其中,b>=0,c>=0,d>=m。d称为该随机序列的种子。下面我们建立一个随机数类RadomNumber，该类包含一个由用户初始化的种子randSeed。给定种子之后，既可产生与之相应的随机数序列。randseed是一个无符号长整型数，既可由用户指定也可由系统时间自动产生。constunsignedlongmaxshort=65536L;constunsignedlongmultiplier=1194211693L;constunsi

7、gnedlongadder=12345L;classRandomNumber{private://当前种子unsignedlongrandseed;public://构造函数，缺省值0表示由系统自动产生种子RandomNumber(unsignedlongs=0);//产生0-n-1之间的随机整数unsignedshortRandom(unsignedlongn);//产生[0，1)之间的随机实数doublefRandom(void);};RandomNumber::RandomNumber(unsignedlongs){if(s==0)rands

8、eed=time(0);elserandseed=s;}unsignedshortRandomNumber::Random