蒙特卡洛算法思想
蒙特卡洛（Monte Carlo）法是一类随机算法的统称，提出者是大名鼎鼎的数学家冯·诺伊曼，他在20世纪40年代中期用驰名世界的赌城—摩纳哥的蒙特卡洛来命名这种方法。
通俗的解释一下蒙特卡洛算法的思想。假如篮子里有1000个苹果，让你每次闭着眼睛拿1个，挑出最大的。于是你闭着眼睛随机拿了一个，然后再随机拿一个与第一个比，留下大的，再随机拿一个，与前次留下的比较，又可以留下大的……你每拿一次，留下的苹果至少是当前最大的，循环往复这样，拿的次数越多，挑出最大苹果的可能性也就越大，但除非你把1000个苹果都挑一遍，否则你无法肯定最终挑出来的就是最大的一个。也就是说，蒙特卡洛算法是样本越多，越能找到最佳的解决办法，但只是尽量找最好的，不保证一定是最好的。
与它形成对比的是拉斯维加斯算法思想。假如有一把锁，有1000把钥匙进行选择，但只有1把是对的。于是你每次随机拿1把钥匙去试，打不开就再换1把。你试的次数越多，打开最优解的机会就越大，但在打开之前，那些错的钥匙都是没有用的。所以拉斯维加斯算法就是尽量找最好的解决办法，但是不保证能找到。假设试了999次后没有任何一把钥匙能打开锁，真正的钥匙是第1000把，但是样本并没有第1000次选择，那么拉斯维加斯算法就不能找到打开锁的钥匙。
蒙特卡洛和拉斯维加斯本身是两座著名赌城，因为赌博中体现了许多随机算法，所以借此命名。它们只是概括了随机算法的特性，算法本身可能复杂，也可能简单，在这两类随机算法之间的选择，往往受到问题的局限。如果问题要求在有限采样内，必须给出一个解，但不要求是最优解，那就要用蒙特卡罗算法。反之，如果问题要求必须给出最优解，但对采样没有限制，那就要用拉斯维加斯算法。
蒙特卡洛算法实验
这么看来蒙特卡洛方法的理论支撑其实是概率论或统计学中的大数定律。基本原理简单描述是先大量模拟，然后计算一个事件发生的次数，再通过这个发生次数除以总模拟次数，得到想要的结果。下面我们以三个经典的小实验来学习下蒙特卡洛算法思想。
1.计算圆周率pi（π）值
实验原理：在正方形内部有一个相切的圆，圆面积/正方形面积之比是(PixRxR)/(2Rx2R)= Pi/4。在这个正方形内随机产生n个点，假设点落在圆内的概率为P，那么P=圆面积/正方形面积，则P= Pi/4。如何计算点落在圆内的概率P？可以计算点与中心点的距离，判断是否落在圆的内部，若这些点均匀分布，用M表示落到圆内投点数 ， N表示总的投点数，则圆周率Pi=4P=4xM/N。
实验步骤：
（1）将圆心设在原点（0，0），以R为半径形成圆，则圆面积为PixRxR
（2）将该圆外接正方形, 坐标为（-R，-R）（R，-R）（R， R）（-R，R），则该正方形面积为R*R
（3）随即取点（X，Y），使得-R <=X<=R并且-R <=Y<=R，即点在正方形内
（4）通过公式 XxX+YxY<= RxR判断点是否在圆周内（直角三角形边长公式）。
（5）设所有点（也就是实验次数）的个数为N，落在圆内的点（满足步骤4的点）的个数为M，则P=M/N，于是Pi=4xM/N。
（6）运行结果为3.143052
def cal_pai_mc(n=1000000): r = 1.0 a, b = (0.0, 0.0) x_neg, x_pos = a - r, a + r y_neg, y_pos = b - r, b + r m = 0 for i in r<mark style="color:transparent">本文来源gaodaimacom搞#^代%!码网@</mark>ange(0, n+1): x = random.uniform(x_neg, x_pos) y = random.uniform(y_neg, y_pos) if x**2 + y**2 <= 1.0: m += 1 return (m / float(n)) * 4
转载请注明原文链接：Python实现蒙特卡洛算法小实验过程详解
