【介绍】蒙特卡罗算法

本站原创文章，转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com

蒙特卡罗算法(Monte Carlo method)起源于1777年法国数学家蒲丰提出的投针实验方法求圆周率π实验

它是一种以概率和统计理论方法为基础，通过随机模拟来解决计算问题的计算方法

本文讲解蒙特卡罗算法的思想和设计步骤，通过本文可初步了解蒙特卡罗算法是什么

   01. 什么是蒙特卡罗算法   

本节讲解什么是蒙特卡罗算法

    什么是蒙特卡罗算法    

蒙特卡罗算法的起源
蒙特卡罗算法的思想起源于1777年法国数学家蒲丰提出的投针实验方法求圆周率π
蒲丰的投针求π实验如下：
 
蒲丰的投针求π实验简单来说就是在一个正方形上投N次针，
然后计算落在正方形内切圆上的针数与落在正方形上的针数占比，以此来估算圆周率π
蒙特卡罗算法的命名
二战期间，数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的MonteCarlo（蒙特卡罗）来命名这种方法
蒙特卡罗算法（Monte Carlo method）也称为统计模拟方法
因此，蒙特卡罗算法并不是一个具体算法，而是一种算法思想
它是指在无法算得具体值的时候，使用抽样统计的方法来估算真实值的一种算法思想

   02. 蒙特卡罗算法的设计与实现   

本节展示蒙特卡罗算法的设计步骤与实现示例

         蒙特卡罗算法的设计        

蒙特卡罗算法设计步骤主要如下：
一、定义问题                                                                  
 一般来说，蒙特卡罗往往并非直接解决一个大问题， 
    而是内嵌在问题内部解决其中一个无法直接计算的子问题
此时使用蒙特卡罗算法来解决该子问题            
二、定义抽样方式                                                           
 对于具体问题，需要确定如何抽样才能评估真实值  
大多数问题往往随机抽样就可以                  
三、定义估算真实值的方法                                             
 根据抽到的样本，定义出用样本评估真实值的方法  
有时是用平均值，有时也可以用最优值            

      投针求π实验的编程实现    

由于蒙特卡罗算法只是一种算法思想，因此针对具体的问题需要设计具体的算法流程
下面不妨以投针求π实验为例，初步了解一个蒙特卡罗算法的流程与实现
投针求π算法流程
 1. 生成m个范围在[-1,1]之间的二维随机点      
2. 检测落在圆内的点数n，即的数量        
3. 计算落在圆内的点数占比n/m,它就是pi/4的估算值       
matlab程序实现如下：

% 本代码用蒙特卡罗算法估算pi
m = 100000;                             % 实验次数
p = rand(m ,2)*2-1;                      % 生成m个随机点
in_circ = sqrt(p(:,1).^2+p(:,2).^2)<1;   % 判断各个点是否落在圆内
in_circ_num = sum(in_circ);              % 落在圆内的点数
pi = 4*sum(in_circ)/m                    % 估算pi

运行结果如下：
 
可见，经过10万次的实验，已经与较为相近

 End