主元素问题的蒙特卡罗算法分析、设计与Python实战。
蒙特卡罗算法的基本思想:设p是一个实数,且0.5<p<1。若蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p,则称该算法是p正确的;对于同一实例,蒙特卡罗算法不会给出两个不同的正确解,就称该算法是一致的; 而对于一个一致的p正确的蒙特卡罗算法,要想提高获得正确解的概率,只需执行该算法若干次,从中选择出现频率最高的解即可。
在一般情况下,如果设蒙特卡罗算法是一致的p正确的。那么至少调用多少次蒙特卡罗算法,可以使得蒙特卡罗算法得到正确解的概率不低于1-ε(0<ε≤1-p)?
。由此可见,无论ε的取值多么小,都可以通过多次调用的方法使得蒙特卡罗算法的优势增强,最终得到一个具有可接受错误概率的算法。
设T[1:n]是一个含有n个元素的数组。当|{i|T[i]=x}|>n/2时,称元素x是数组T的主元素。例如,T=[1,1,1,2,5,5,1,1,1,1],T中有10个元素,其中元素1出现了7次,超过了总元素个数的一半,所以元素1是T的主元素。再如T=[1,1,2,2,5,5,1,2,2,1],元素1出现4次,元素2出现4次,元素5出现2次,元素1、2、5出现的次数都不超过总元素个数的一半,所以T中不存在主元素。
由此可知,T中要么有主元素,且只有一个元素为主元素,要么没有主元素。主元素问题为要求确定给定的T中是否有主元素。
对于给定的含有n个元素的数组T,设计确定数组T中是否存在主元素的蒙特卡罗算法如下:
由主元素的定义可知,如果T中含有主元素,那么上述蒙特卡罗算法返回True的概率大于1/2;如果T中不含有主元素,那么肯定返回False。
在实际使用过程中,蒙特卡罗算法得到的解的可信度至少为50%,这是无法让人接受的。为此,可通过重复调用该算法的方法来提高算法的可信度,使其错误概率降低到可接受的范围内。
对于任意给定的ε>0,重复调用蒙特卡罗算法
次,可使得算法的可信度大于1-ε,即错误概率小于ε。算法如下:
显然,算法majorityMC所需的计算时间是
首先引入需要类包random、math。其代码如下:
定义majority函数,用于判定T中是否有主元素。若有主元素,则返回True;否则,返回False。其代码如下:
定义majorityMC函数,用于执行若干次,使得主元素问题的蒙特卡罗算法得到正确解的概率不小于1-ε。majorityMC函数中,首先调用一次majority函数,如果有主元素,就直接返回True;否则,最多循环执行k次,提高蒙特卡罗算法得到正确解的概率,使之不小于1-ε。其代码如下:
定义Python入口——main函数,在main函数中,给出两个实例,分别调用majorityMC函数,得到结果,该结果的可信度不低于1-ε。最后将算法结果打印输出到显示器上。其代码如下:
输出结果为(不同次的执行,结果可能不同)
T中是否有主元素?,结果为:True
T1中是否有主元素?,结果为:False
算法设计与分析(Python版)
选第二大元素的分治算法
快速排序算法中的分治思想
动态规范算法的基本思想
0-1背包问题的动态规划改进算法——跳跃点算法
子集树模型——0-1背包问题的回溯算法
满m叉树模型——图的m可着色问题的回溯算法
排列树模型——旅行商问题的分支限界法
最大网络流的增广路算法
-
微信小程序游戏开发│猜数字小游戏(附源码+视频)
-
Flink编程基础│Scala编程初级实践
-
数 据分析实战│客户价值分析
-
数据分析实战│价格预测挑战
-
数据分析实战│时间序列预测