经典蒙特卡洛算法

⑴ 蒙特卡洛算法是什么

是二十世纪提出的数值计算方法。

蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。

是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。与它对应的是确定性算法。蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学（如粒子输运计算、量子热力学计算、空气动力学计算）等领域应用广泛。

基本原理：

蒙特卡罗方法通过抓住事物运动的几何数量和几何特征，利用数学方法来加以模拟，即进行一种数字模拟实验。它以一个概率模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的近似解。

蒙特卡罗解题可归结为三个主要步骤。

构造或描述概率过程。

实现从已知概率分布抽样。

建立各种评估量。

⑵ 什么是蒙特卡洛分析

蒙特卡罗分析法，是一种容差分析方法，以电子电路为例，在给定元器件的值和容差范围时，对电路进行直流特性，交流小信号特性，瞬态特性分析，得出整个电路的性能的统计规律。

换言之，也就是从一个系统的组成部分的变动范围来分析整个系统的性能、动态范围的统计规律的方法。

总之，是一种利用概率统计理论的仿真方法。通过容差分析，可以断定整个系统是否满足设计要求，从而判断某些元器件是否符合要求。

在电路设计中，实际元件的参数值和标称之间总存在着随机误差，了解和掌握各个元件参数值对电路性能的影响程度，是电路设计人员所关心的。因此在电路设计时，需考虑容差问题，并进行容差分析。

所谓容差分析是为设定方案确定电路元器件的容许变化范围，即元件的容差。它可分为两类:一是分析问题，给定元器件、电路及温度的容差，计算电路特性的容差，以验证是否符合设计要求;二是设计问题，给定电路特性指标的范围，求出所用元器件及电源等的容差，验证设计方案等是否适宜。但容差设计问题没有惟一解，所以在电路模拟中要解决这一问题，往往通过容差分析问题进行反求，对电路进行容差分析。

目前，在电子电路的可靠性设计中，蒙特卡罗分析法是进行容差分析的主要方法之一。电子电路中的蒙特卡罗分析法是一种基于概率统计模拟方法，它是在给定电路元器件参数容差的统计分布规律的情况下，用一组组伪随机数求得元器件参数的随机抽样序列，对这些随机抽样的电路进行直流、交流小信号和瞬态分析，并通过多次分析结果估算出电路性能的统计分布规律，如电路性能的中心值、方差，以及电路合格率、成本等。

⑶ 蒙特卡洛树是什么算法

蒙特卡罗树搜索(MCTS)会逐渐的建立一颗不对称的树。可以分为四步并反复迭代：

(1)选择
从根节点，也就是要做决策的局面R出发向下选择一个最急迫需要被拓展的节点T；局面R是第一个被检查的节点，被检查的节点如果存在一个没有被评价过的招式m，那么被检查的节点在执行m后得到的新局面就是我们所需要展开的T；如果被检查的局面所有可行的招式已经都被评价过了，那么利用ucb公式得到一个拥有最大ucb值的可行招式，并且对这个招式产生的新局面再次进行检查；如果被检查的局面是一个游戏已经结束的游戏局面，那么直接执行步骤4；通过反复的进行检查，最终得到一个在树的最底层的最后一次被检查的局面c和它的一个没有被评价过的招式m，执行步骤2。

(2)拓展
对于此时存在于内存中的局面c，添加一个它的子节点。这个子节点由局面c执行招式m而得到，也就是T。

(3)模拟
从局面T出发，双方开始随机的落子。最终得到一个结果(win/lost)，以此更新T节点的胜利率。

(4)反向传播
在T模拟结束之后，它的父节点c以及其所有的祖先节点依次更新胜利率。一个节点的胜利率为这个节点所有的子节点的平均胜利率。并从T开始，一直反向传播到根节点R，因此路径上所有的节点的胜利率都会被更新。

⑷ 什么是蒙特卡洛分析

蒙特卡罗分析法（统计模拟法），是一种采用随机抽样统计来估算结果的计算方法，可用于估算圆周率，由约翰·冯·诺伊曼提出。由于计算结果的精确度很大程度上取决于抽取样本的数量，一般需要大量的样本数据，因此在没有计算机的时代并没有受到重视。

利用蒙特卡罗分析法可用于估算圆周率，如图，在边长为 2 的正方形内作一个半径为 1 的圆，正方形的面积等于 2×2=4，圆的面积等于 π×1×1=π，由此可得出，正方形的面积与圆形的面积的比值为 4:π。

现在让我们用电脑或轮盘生成若干组均匀分布于 0-2 之间的随机数，作为某一点的坐标散布于正方形内，那么落在正方形内的点数 N 与落在圆形内的点数 K 的比值接近于正方形的面积与圆的面积的比值，即，N:K ≈ 4:π，因此，π ≈ 4K/N 。

用此方法求圆周率，需要大量的均匀分布的随机数才能获得比较准确的数值，这也是蒙特卡罗分析法的不足之处。

(4)经典蒙特卡洛算法扩展阅读：

使用蒙特·卡罗方法进行分子模拟计算是按照以下步骤进行的：

1． 使用随机数发生器产生一个随机的分子构型。

2． 对此分子构型的其中粒子坐标做无规则的改变，产生一个新的分子构型。

3． 计算新的分子构型的能量。

4． 比较新的分子构型于改变前的分子构型的能量变化，判断是否接受该构型。

若新的分子构型能量低于原分子构型的能量，则接受新的构型，使用这个构型重复再做下一次迭代。 若新的分子构型能量高于原分子构型的能量，则计算玻尔兹曼因子，并产生一个随机数。

若这个随机数大于所计算出的玻尔兹曼因子，则放弃这个构型，重新计算。 若这个随机数小于所计算出的玻尔兹曼因子，则接受这个构型，使用这个构型重复再做下一次迭代。

5． 如此进行迭代计算，直至最后搜索出低于所给能量条件的分子构型结束。

项目管理中蒙特·卡罗模拟方法的一般步骤是：

1．对每一项活动，输入最小、最大和最可能估计数据，并为其选择一种合适的先验分布模型；

2．计算机根据上述输入，利用给定的某种规则，快速实施充分大量的随机抽样

3．对随机抽样的数据进行必要的数学计算，求出结果

4．对求出的结果进行统计学处理，求出最小值、最大值以及数学期望值和单位标准偏差

5．根据求出的统计学处理数据，让计算机自动生成概率分布曲线和累积概率曲线(通常是基于正态分布的概率累积S曲线)

6．依据累积概率曲线进行项目风险分析。

⑸ 蒙特卡罗算法是什么

蒙特卡罗（MonteCarlo）方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第二次世界大战进行研制原子弹的“曼哈顿计划”。

该计划的主持人之一、数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的MonteCarlo—来命名这种方法，为它蒙上了一层神秘色彩。

主要是：

使用随机数（ 或更常见的伪随机数）来解决很多计算问题的方法。 将所求解的问题同一定的概率模型相联系， 用电子计算机实现统计模拟或 抽样 ，以获得问题的近似解。 为象征性地表明这一方法的概率统计特征， 故借用赌城蒙特卡罗命名。

⑹ 蒙特卡洛算法和拉斯维加斯算法

一、定义：

特卡罗是一类随机方法的统称。这类方法的特点是，可以在随机采样上计算得到近似结果，随着采样的增多，得到的结果是正确结果的概率逐渐加大，但在（放弃随机采样，而采用类似全采样这样的确定性方法）获得真正的结果之前，无法知道目前得到的结果是不是真正的结果。​

拉斯维加斯方法是另一类随机方法的统称。这类方法的特点是，随着采样次数的增多，得到的正确结果的概率逐渐加大，如果随机采样过程中已经找到了正确结果，该方法可以判别并报告，但在但在放弃随机采样，而采用渣竖类似全采样这样的确定性方法之前，不保证能找到任何结果（包括近似结果）​

二、场景举例​

假如筐里有100个苹果，让我每次闭备梁银眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比仿宴，留下大的，再随机拿1个……我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法——尽量找好的，但不保证是最好的。

而拉斯维加斯算法，则是另一种情况。假如有一把锁，给我100把钥匙，只有1把是对的。于是我每次随机拿1把钥匙去试，打不开就再换1把。我试的次数越多，打开（最优解）的机会就越大，但在打开之前，那些错的钥匙都是没有用的。这个试钥匙的算法，就是拉斯维加斯的——尽量找最好的，但不保证能找到。​

三、结论​

•蒙特卡罗算法   

：采样越多，越近似最优解；

•拉斯维加斯算法：采样越多，越有机会找到最优解；​

这两类随机算法之间的选择，往往受到问题的局限。如果问题要求在有限采样内，必须给出一个解，但不要求是最优解，那就要用蒙特卡罗算法。反之，如果问题要求必须给出最优解，但对采样没有限制，那就要用拉斯维加斯算法。​