蒙特卡罗算法

来自计算思维百科
跳转至: 导航搜索
蒙特卡罗算法1.png

蒙特卡洛方法(Monte Carlo method),也称统计模拟方法,是一种以概率统计理论为指导的一类非常重要的数值计算方法。

基本概念

蒙特卡洛为摩洛哥王国之首都,该国位于法国与义大利国境,以赌博闻名。蒙特卡洛算法的基本原理是为以乱数配合面积公式来进行解题,这种以机率来解题的方式带有赌博的意味,虽在精确度上有所疑虑,但其解题的思考方向却是个值得学习的方式。

通常蒙特卡洛方法中的一类是所求解的问题本身具有内在的随机性,借助计算机的运算能力可以直接模拟这种随机的过程。例如在核物理研究中,分析中子在反应堆中的传输过程。中子与原子核作用受到量子力学规律的制约,人们只能知道它们相互作用发生的概率,却无法准确获得中子与原子核作用时的位置以及裂变产生的新中子的行进速率和方向。科学家依据其概率进行随机抽样得到裂变位置、速度和方向,这样模拟大量中子的行为后,经过统计就能获得中子传输的范围,作为反应堆设计的依据。

假设我们要计算一个不规则图形的面积,蒙特卡洛方法基于这样的思想:假想你有一袋豆子,把豆子均匀地朝这个图形上撒,然后数这个图形之中有多少颗豆子,这个豆子的数目就是图形的面积。当你的豆子越小,撒的越多的时候,结果就越精确。借助计算机程序可以生成大量均匀分布坐标点,然后统计出图形内的点数,通过它们占总点数的比例和坐标点生成范围的面积就可以求出图形面积。

应用范围

蒙特卡洛方法在金融工程学,宏观经济学,生物医学,计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。在某些计算机模拟过程中,可以随机产生噪声,比如说水中花粉随机行走之类的问题,可以用来随机产生外界水分子的作用力,用来模拟现实情况。当然也可以用这种方式来近似某些科学计算,最简单的例子就是近似计算积分。对于某些计算机无法完全枚举的优化问题,也可以用蒙特卡洛方法得到较好的解,常见的比如模拟退火,量子退火等优化方法,都用到了蒙特卡洛算法。

应用案例

应用1-蒙特卡洛算法求π

案例:正方形边长为1,左下顶点与原点重合,两边分别与x,y轴重合。曲线为1/4圆弧,圆心位于原点,与正方形左下定点重合,半径为1。正方形面积S1=1,圆弧内面积S2=1/4πr2=1/4π。利用蒙特卡洛算法的思想模拟大量点随机落在此正方形区域内,落在圆弧内的点的数量(n2)与点的总数(n1)的比例与面积成正比关系。即

蒙特卡罗算法2.png
则有
蒙特卡罗算法3.png

因此,只要计算出落在圆弧内的点的数量在点总数中所占的比例,就能求出π的值。

应用2-市场服务

案例:超市有两个出口的收款台,服务分别为收款和装袋;两名职工在出口工作。有两种方案:开一个出口,一人收款,一人装袋;开两个出口,每个人即收款又装袋。问该商场经理应该选择哪一种方案可以使收款台的效率更高且不浪费劳动力成本?其中,顾客到达的时间是随机的。

解决方法:在这个案例中,我们并不知道顾客什么时候到达,即顾客的到达时间是个不确定量。在这样的情况下,就可以利用蒙特卡洛法产生的随机数来模拟顾客到达收款台的实际情况,从而帮助经理做出更好的选择。

可以体现的计算思维

蒙特卡洛方法是一种通过随机数来模拟实际情况的方法,通过模拟真实情境判断问题解决方案是否合理,这正是计算思维中的仿真思想的体现。