Algorithm之MC：Monte Carlo method蒙特·卡罗方法的简介、实现、应用

Algorithm之MC：Monte Carlo method蒙特·卡罗方法的简介、实现、应用

---

随机算法

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

(1)、这两类随机算法之间的选择，往往受到问题的局限。
          如果问题要求在有限采样内，必须给出一个解，但不要求是最优解，那就要用蒙特卡罗算法。
          反之，如果问题要求必须给出最优解，但对采样没有限制，那就要用拉斯维加斯算法。
          比如，机器围棋程序，因为每一步棋的运算时间、堆栈空间都是有限的，而且不要求最优解，所以ZEN涉及的随机算法，肯定是蒙特卡罗式的。

MC的简介

Monte Carlo method，也称随机抽样法、统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。与它对应的是确定性算法。

MC思想：当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。

它的基本思想是通过大量随机样本，去了解一个系统，进而得到要计算的值。它非常强大灵活，又相当简单易懂，很容易实现。

MC三步骤：蒙特卡罗方法的解题过程可以归结为三个主要步骤：构造或描述概率过程；实现从已知概率分布抽样；建立各种估计量。

MC的应用

1、正方形内部有一个内切的圆，通过简单计算可知内切圆和正方形的面积比为π/4π/4,因此通过在直角坐标系的第一象限随机取点，统计落在圆内的点，其与总取样点数的比例即为π/4π/4，将该比例乘以4即可得π。示意图和代码如下：

#-*-coding:utf-8-*-
import random
def calcPi(n):
        count = 0
        for i in range(n):
                x = random.uniform(0,1.0) #在[0,1]区间均匀地随机取样
                y = random.uniform(0,1.0)
                if(x**2+y**2<=1):  #if判断每当随机点落在半圆内,就统计一次
                        count += 1
                if(count%3000)==0:     #每3000个点，输出一次
                    print(4.0*count/n )

        return 4.0*count/n #注意4要写成浮点数的形式，否则结果只保留整数
print(calcPi(30000)) #取30000个样本点

0.4
0.8
0.8
1.2
1.6
2.0
2.0
2.4
2.8
3.134533333333333

2、Matlab之Monte Carlo：基于Matlab实现通过蒙特卡洛方法模拟二维布朗运动