蒙特卡洛算法每次计算不一样

① (六) 概率算法

前面所讨论算法的每一计算步骤都是确定的，而本次所讨论的概率算法允许算法在执行过程中随机地选择下一个计算步骤。在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。

概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下， 可将概率算法大致分为四类：数值概率算法、蒙特卡罗(MonteCarlo) 算法、拉斯羡孝陵维加斯(Las Vegas) 算法和舍伍德(Sherwood) 算法。

随机数在随机化算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在随机化算法中使用的随机数都是一定程度上随机的，即伪随机数。
线性同余法 是产生伪随机数的最常用的方法。由线性同余法产生的随机序列 满足

其中 。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容，已超出本书讨论的范围。从直观上看，m应取得充分大，因此可取m为机器大数，另外应取 ，因此可取b为一素数。

为了在设计概率算法时便于产生所需的随机数，建立一个随机数类RandomNumber：该类包含一个需由用户初始化的种子randSeed。给定初始种子后，即可产生与之相应的随机序列。种子randSeed是一个无符号长整型数， 可由用户选定也可用系统时间自动产生。函数Random的输入参数 是一个无符号长整型数，它返回 范围内的一个随机整数。函数fRandom返回[0，1) 内的一个随机实数。

数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。且近似解的精度随计算时间的增加而不断提高。在许多情况下，要计算出问题的精确解是不可能的或没有必要的，因此用数值概率算法可得到相当满意的解。

当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时

舍伍德算法就是一种利用随机算法改造确定性算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏情形行为与特定实例之间的关联性。

思想：利用随机算法改造已有算法，使得算法的性能尽量与输入数据无关，即平滑算法的性能。它总能求得问兄戚题的一个解，且求得的解总是正确的。

算法的性能 =平均性能 + 一个很小的随机值。 舍伍德算法是为了得到好的平均性能。

一个算法，对于不同的输入数据，其算法的性能是不一样的。比如快排算法，每次选择第一个元素作为基准，慎带对序列从小到大排序：

拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法会找不到解。

与蒙特卡罗算法类似，拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。

蒙特卡罗算法用于求问题的准确解。对于许多问题来说，近似解毫无意义。例如，一个判定问题其解为“是”或“否”，二者必居其一，不存在任何近似解答。又如，我们要求一个整数的因子时所给出的解答必须是准确的，一个整数的近似因子没有任何意义。

用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点也在于此。一般情况下，无法有效地判定所得到的解是否肯定正确。

在实际应用中常会遇到一些问题，不论采用确定性算法或随机化算法都无法保证每次都能得到正确的解答。蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。

有些蒙特卡罗算法除了具有描述问题实例的输入参数外，还具有描述错误解可接受概率的参数。这类算法的计算时间复杂性通常由问题的实例规模以及错误解可接受概率的函数来描述。

参考链接： http://www.ruanyifeng.com/blog/2015/07/monte-carlo-method.html

数值概率算法的应用

舍伍德算法的应用

拉斯维加斯算法的应用

蒙特卡罗算法的应用

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

一、定义：

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

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

二、场景举例​

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

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

三、结论​

•蒙特卡罗算法   

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

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

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

③ 蒙特卡洛方法

蒙特卡罗方法又称统计模拟法、随机抽样技术，是一种随机模拟方法，以概率和统计理论方法为基础的一种计算方法，是使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。

应用领域：

蒙特卡罗方法在金融工程学，宏观经济学，生物医学，计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算、核工程)等领域应用广泛。

④ 请问 Python程序蒙特卡罗方法求Pi怎样让每次运行结果相同

guess = input("What's yer guess? ")

改为
guess = int(input("What's yer guess? "))