蒙特卡洛算法是什么？

Python050

蒙特卡洛算法是什么？,第1张

蒙特卡罗算法并不是一种算法的名称，而是对一类随机算法的特性的概括。

媒体说“蒙特卡罗算法打败武宫正树”，这个说法就好比说“我被一只脊椎动物咬了”，是比较火星的。实际上是ZEN的算法具有蒙特卡罗特性，或者说它的算法属于一种蒙特卡罗算法。

举个例子：

假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个，我每拿一次，留下的苹果都至少不比上次的小。

拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法——尽量找好的，但不保证是最好的。

一年一度的圆周率日就要到了，是的，就是3月14日，因为它与圆周率π的前几位3.14的数字一样。

我们知道，传说中祖冲之计算圆周率用的是“割圆术”的改进方法，可惜我们大多数现代人的脑子已经无法理解这种方法了。使用其他的复杂公式也有，但人的脑子更不容易理解，但有一个异想天开的方法你知道吗？任何人可以简单地去计算出Pi呢（下面我们都用Pi来代替圆周率π吧，好写好认，：p）。

这个方法源自概率论的基础，叫做蒙特卡洛法，形象一点的话我们也可以把它称为随机落点法，我们先说说它的原理：

我们先看看下面这张图

假设有图中的一个正方形和一个刚好套在它中间的圆形，可以很直观地看出：圆形的半径如果是R的话，正方形的边长就是2R。

圆形的面积根据公式是Pi乘以R的平方，也就是 Pi × R × R = PiR²

正方形的面积根据公式是边长的平方，也就是（2R）×（2R）= 4R²

把两个式子相除一下，可以很容易地推算出来，Pi = （圆形的面积 ÷ 正方形的面积）× 4

这样，就巧妙地把计算Pi值的问题转换成计算符合上面图中条件的圆形与正方形的面积之比的计算了。

这时候，概率论可以出场发挥作用了，以及有了计算机之后，我们有的“随机数”这个武器！

假设我们随机在正方形范围内画一个点，那么这个点有可能落在圆形之中，也有可能落在圆形之外；然后我们重复这个动作，从概率论上来说，如果进行无限多次，那么落在圆形中的点的个数与所有已经画的点的个数之比，就应该是圆形的面积和正方形的面积之比。看看下面这张图是不是就好理解了？

想想当里面的点数足够多的时候，就可以覆盖满整个原型和正方形。俗话说：“以点带面”，这时候就可以理解成无数多的点组成了圆形和正方形的面积。

好了，那么下面我们看看用计算机程序来实现这种方法计算圆周率的效果吧！我们这次选用Go语言（Golang）来实现这个算法，因为Go语言相对速度较快（比Python和Java等解释型语言要快得多），编写起来又比C语言更容易看懂。

这段程序的运行结果是：

可以看出来，计算出来的圆周率Pi值越来越接近于我们所熟知的数字：3.1415……

神奇吧，为什么说人也可以算出来呢？假想在地上用粉笔画一个那样的正方形和圆形，然后我们随性地往里扔沙包吧！很童真的画面吧？