神经网络-一篇入门

【算法】一篇入门之-蒙特卡罗算法(MC)

作者 : 老饼 发表日期 : 2023-05-22 13:25:07 更新日期 : 2024-10-17 23:45:05
本站原创文章,转载请说明来自《老饼讲解-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 







联系老饼