經典蒙特卡洛演算法

⑴ 蒙特卡洛演算法是什麼

是二十世紀提出的數值計算方法。

蒙特·卡羅方法（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把。我試的次數越多，打開（最優解）的機會就越大，但在打開之前，那些錯的鑰匙都是沒有用的。這個試鑰匙的演算法，就是拉斯維加斯的——盡量找最好的，但不保證能找到。​

三、結論​

•蒙特卡羅演算法   

：采樣越多，越近似最優解；

•拉斯維加斯演算法：采樣越多，越有機會找到最優解；​

這兩類隨機演算法之間的選擇，往往受到問題的局限。如果問題要求在有限采樣內，必須給出一個解，但不要求是最優解，那就要用蒙特卡羅演算法。反之，如果問題要求必須給出最優解，但對采樣沒有限制，那就要用拉斯維加斯演算法。​