美赛常用六种算法第一期:蒙特卡罗算法

算法概述

蒙特卡罗算法是以概率和统计理论方法为基础的一种计算方法。将所求解的问题同一定的概率模型相联系，用电子计算机实现统计模拟或抽样，以获得问题的近似解。为象征性地表明这一方法的概率统计特征，故借用赌城蒙特卡罗命名。又称统计模拟法、随机抽样技术。由S.M.乌拉姆和J.冯·诺伊曼在20世纪40年代为研制核武器而首先提出。

它的基本思想是，为了求解数学、物理、工程技术以及管理等方面的问题 ，首先建立一个概率模型或随机过程，使它们的参数，如概率分布或数学期望等问题的解；然后通过对模型或过程的观察或抽样试验来计算所求参数的统计特征，并用算术平均值作为所求解的近似值。对于随机性问题，有时还可以根据实际物理背景的概率法则，用电子计算机直接进行抽样试验，从而求得问题的解答。简单来讲即采样越多越接近最优解。

02 算法特点

直接追踪粒子，物理思路清晰，易于理解。

采用随机抽样的方法，较真切的模拟粒子输运的过程，反映了统计涨落的规律。

不受系统多维、多因素等复杂性的限制，是解决复杂系统粒子输运问题的好方法。

MC程序结构清晰简单。

研究人员采用MC方法编写程序来解决粒子输运问题，比较容易得到自己想得到的任意中间结果，应用灵活性强。

03 算法原理

以面积计算的问题讲解蒙特卡洛算法的实现步骤如下：

1

画出图像

求要计算图像的基本形状。此处以y1=3x；y2=8-x为例，画出图像如下：

2

确定边界

通常为矩形，要求矩形必须完整包括所求图像。

如上图，因为图像交点为（2,6），因此，确定边界如红框所示：（0,0），（8,0），（8,6），（0,6）

3

随机统计

在（矩形）边界范围内随机产生点，并统计落在所求图像中的点。所用到的函数为unifrnd函数。本例子以10^7（7次方在保证运行速度的情况下，基本可以满足准确度）为例。

4

确定面积

用比值法求面积，即落在图像上的点：整个范围内的点=所求图像面积：矩形边界面积。

即所有图像I面积=矩形边界面积*落在图像上的点/整个范围内的点。

04 算法相关

本例中使用到的unifrnd函数的相关知识。

R = unifrnd(A,B,M,N,...) or R = unifrnd(A,B,[M,N,...])

即产生m*n阶［a，b］均匀分布U（a，b）的随机数矩阵：unifrnd (a,b,m, n)

如y=(0,8,[1,10000000])，即产生1*10000000阶位于（0,8）之间的数。

1

代码实现

%画函数图像
x=0:0.25:10;
y1=3*x;
y2=8-x;
plot(x,y1,x,y2)
axis([0 10 0 10]);
legend('y1=3x','y2=8-x');
title('蒙特卡洛算法');
text(2,6,'交点');
grid on
%产生随机点
x=unifrnd(0,8,[1,10000000]);
y=unifrnd(0,6,[1,10000000]);
%统计所在所求图形中的点
frequency=sum(y<3*x & x<=2)+sum(y<8-x & x>2);
%计算面积area=6*8*frequency/10^7;

2

结果测验

由函数图像可知，所求区域面积为：24单位。

算法运行结果如下：

由结果可知，算法每次运行结果都不一样，这是有概率统计的特性所致。但是结果都稳定在24左右，这与理论值是一样的。

2023年MCM/ICM美国大学生数学建模竞赛正在报名中

保研加分、综测评奖

由于报名参加美赛的同学不具备Visa或国际支付方式，以及缺乏一定的参赛经验，为了更好的提升参赛者的获奖率，数模乐园继续推出2023年美赛辅助报名及证书打印并邮寄的服务。 2022年 通过数模乐园辅助报名中， 4支 队伍斩获2021 Outstanding Winner奖（其中一支获得SIAM Award冠名奖；另外3支获得Outstanding Winner奖），O奖获奖率同比增长 50% ，整体参赛获奖率达99.3%， 2021年 助力1支队伍获得 1万美元 奖学金。数模乐园已累计为 8.5万 多人以上同学完成了美赛辅助报名服务！已成为 国内最大的美赛辅助报名平台！

竞赛报名

或复制下方报名官网进行报名：http://www.nmmcm.org.cn/match_detail/23

进群领取历年美赛真题及培训资料，进群备注：学校+专业