蒙特卡洛演算法每次計算不一樣

① (六) 概率演算法

前面所討論演算法的每一計算步驟都是確定的，而本次所討論的概率演算法允許演算法在執行過程中隨機地選擇下一個計算步驟。在許多情況下，當演算法在執行過程中面臨一個選擇時，隨機性選擇常比最優選擇省時。因此概率演算法可在很大程度上降低演算法的復雜度。

概率演算法的一個基本特徵是對所求解問題的同一實例用同一概率演算法求解兩次可能得到完全不同的效果。這兩次求解所需的時間甚至所得到的結果可能會有相當大的差別。一般情況下， 可將概率演算法大致分為四類：數值概率演算法、蒙特卡羅(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? "))