基于Mapreduce的蒙特卡洛算法 李小兵组

  蒙特卡洛算法

 

                                  组员  李小兵 周立 冯俊 李继华 艾海提

 

算法简介

　　，也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。蒙特·卡洛方法的名字来源于的一个城市，该城市以赌博业闻名，而蒙特·卡罗方法正是以概率为基础的方法。

　　与它对应的是确定性算法。

蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。

 

背景知识

　　　　1946年，拉斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis共同发明，被称为方法。它的具体定义是：在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，现在要计算这个不规则图形的面积，怎么计算列?蒙特卡洛(Monte Carlo)方法告诉我们，均匀的向该正方形内撒N（N 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个，那么，这个奇怪形状的面积便近似于M/N，N越大，算出来的值便越精确。在这里我们要假定豆子都在一个平面上，相互之间没有重叠。蒙特卡洛方法可用于近似计算圆周率：让计算机每次随机生成两个0到1之间的数，看这两个实数是否在单位圆内。生成一系列随机点，统计单位圆内的点数与总点数，（圆面积和正方形面积之比为PI:1，PI为圆周率），当随机点取得越多（但即使取10的9次方个随机点时，其结果也仅在前4位与圆周率吻合）时，其结果越接近于圆周率。

算法描述

以概率和统计理论方法为基础的一种计算方法。将所求解的问题同一定的概率模型相联系，用计算机实现统计模拟或抽样，以获得问题的近似解。比如，给定x=a，和x=b，你要求某一f和这两竖线，及x轴围成的面积，你可以起定y轴一横线 y=c 其中c>=f(x)max，很简单的，你可以求出 y=c,x=a,x=b,及 x轴围成的矩形面积，然后利用随机产生大量在这个矩形范围之内的点，统计出现在曲线上部点数和出现在曲线下部点的数目，记为：doteUpCount,nodeDownCount,然后所要求的面积可以近似为 doteDownCounts所占比例*矩形面积。

 

小结：

蒙特卡洛算法是以概率和统计理论方法为基础的一种计算方法，它的结果是近似的，但是在很大甚至无限多的数据下，结果是无限接近于正确值的，利用此方法可以测试出很多的参数，比如圆周率的值。所以众多的数据是它的基础，利用Mapreduce的方法能有效的结合更多的计算资源，凑齐尽可能多的有效数据，让测试测值更准确，这也是我们努力的方向。