蒙特卡罗算法理解和简单实现

1 蒙特卡罗算法简介

蒙特卡罗(Monte Carlo)算法并不是一种特定的算法&＃xff0c;而是对一类随机算法的特性的概括。它的名字来源于赌城蒙特卡罗&＃xff0c;象征概率。它的基本思想是通过大量随机样本&＃xff0c;去了解一个系统&＃xff0c;进而得到要计算的值。它非常强大灵活&＃xff0c;又相当简单易懂&＃xff0c;很容易实现。

2 蒙特卡罗算法与拉斯维加斯算法比较

随机算法分为两大类&＃xff1a;蒙特卡罗算法和拉斯维加斯算法&＃xff0c;都是以著名的赌城命名的&＃xff0c;且都是通过随机采样尽可能找到最优解。

3 蒙特卡罗算法的简单python实现

下面就用蒙特卡罗随机取样的思想近似求解圆周率π
正方形内部有一个内切的圆&＃xff0c;通过简单计算可知内切圆和正方形的面积比为π/4,因此通过在直角坐标系的第一象限随机取点&＃xff0c;统计落在圆内的点&＃xff0c;其与总取样点数的比例即为π/4&＃xff0c;将该比例乘以4即可得π。示意图和代码如下&＃xff1a;

#-*-coding:utf-8-*-
import random
def calcPi(n):count &＃61; 0for i in range(n):x &＃61; random.uniform(0,1.0) #在[0,1]区间均匀地随机取样y &＃61; random.uniform(0,1.0)if(x**2&＃43;y**2<&＃61;1):count &＃43;&＃61; 1return 4.0*count/n #注意4要写成浮点数的形式&＃xff0c;否则结果只保留整数
print calcPi(30000) #取30000个样本点

一次计算结果为3.15226666667,误差不到0.5%&＃xff0c;且取样点数越多&＃xff0c;结果越接近。

参考&＃xff1a;
1.蒙特卡罗方法入门
2.知乎&＃xff1a;蒙特卡罗算法是什么