計算機博弈算法與編程 課件 5Monte Carlo算法

5MonteCarlo算法蒙特·卡羅方法（MonteCarlomethod），也稱統(tǒng)計模擬方法，是二十世紀四十年代中期由于科學技術的發(fā)展和電子計算機的發(fā)明，而被提出的一種以概率統(tǒng)計理論為指導的一類非常重要的數(shù)值計算方法。是指使用隨機數(shù)（或更常見的偽隨機數(shù)）來解決很多計算問題的方法。與它對應的是確定性算法。MonteCarlo算法提出：蒙特卡羅方法于20世紀40年代美國在第二次世界大戰(zhàn)中研制原子彈的“曼哈頓計劃”計劃的成員S.M.烏拉姆和J.馮·諾伊曼首先提出。數(shù)學家馮·諾伊曼用馳名世界的賭城—摩納哥的MonteCarlo—來命名這種方法，為它蒙上了一層神秘色彩。在這之前，蒙特卡羅方法就已經(jīng)存在。1777年，法國數(shù)學家布豐（GeorgesLouisLecleredeBuffon，1707—1788）提出用投針實驗的方法求圓周率π。這被認為是蒙特卡羅方法的起源。MonteCarlo算法基本思想：當所求解問題是某種隨機事件出現(xiàn)的概率，或者是某個隨機變量的期望值時，通過某種“實驗”的方法，以這種事件出現(xiàn)的頻率估計這一隨機事件的概率，或者得到這個隨機變量的某些數(shù)字特征，并將其作為問題的解。MonteCarlo算法工作過程：蒙特卡羅方法的解題過程可以歸結為三個主要步驟：構造或描述概率過程；實現(xiàn)從已知概率分布抽樣；建立各種估計量。蒙特卡羅方法解題過程的三個主要步驟：（1）構造或描述概率過程對于本身就具有隨機性質(zhì)的問題，如粒子輸運問題，主要是正確描述和模擬這個概率過程，對于本來不是隨機性質(zhì)的確定性問題，比如計算定積分，就必須事先構造一個人為的概率過程，它的某些參量正好是所要求問題的解。即要將不具有隨機性質(zhì)的問題轉(zhuǎn)化為隨機性質(zhì)的問題。MonteCarlo算法（2）實現(xiàn)從已知概率分布抽樣構造了概率模型以后，由于各種概率模型都可以看作是由各種各樣的概率分布構成的，因此產(chǎn)生已知概率分布的隨機變量（或隨機向量），就成為實現(xiàn)蒙特卡羅方法模擬實驗的基本手段，這也是蒙特卡羅方法被稱為隨機抽樣的原因。最簡單、最基本、最重要的一個概率分布是（0，1）上的均勻分布（或稱矩形分布）。隨機數(shù)就是具有這種均勻分布的隨機變量。隨機數(shù)序列就是具有這種分布的總體的一個簡單子樣，也就是一個具有這種分布的相互獨立的隨機變數(shù)序列。產(chǎn)生隨機數(shù)的問題，就是從這個分布的抽樣問題。在計算機上，可以用物理方法產(chǎn)生隨機數(shù)，但價格昂貴，不能重復，使用不便。另一種方法是用數(shù)學遞推公式產(chǎn)生。這樣產(chǎn)生的序列，與真正的隨機數(shù)序列不同，所以稱為偽隨機數(shù)，或偽隨機數(shù)序列。不過，經(jīng)過多種統(tǒng)計檢驗表明，它與真正的隨機數(shù)，或隨機數(shù)序列具有相近的性質(zhì)，因此可把它作為真正的隨機數(shù)來使用。由已知分布隨機抽樣有各種方法，與從(0,1)上均勻分布抽樣不同，這些方法都是借助于隨機序列來實現(xiàn)的，也就是說，都是以產(chǎn)生隨機數(shù)為前提的。由此可見，隨機數(shù)是我們實現(xiàn)蒙特卡羅模擬的基本工具。MonteCarlo算法（3）建立各種估計量一般說來，構造了概率模型并能從中抽樣后，即實現(xiàn)模擬實驗后，我們就要確定一個隨機變量，作為所要求的問題的解，我們稱它為無偏估計。建立各種估計量，相當于對模擬實驗的結果進行考察和登記，從中得到問題的解。MonteCarlo算法案例：計算PI原理：

先畫一個正方形，畫出其內(nèi)切圓，然后這個正方形內(nèi)隨機的畫點，設點落在圓內(nèi)的概為P，則P=圓面積/正方形面積。

P=Pi*R*R/2R*2R=Pi/4

即Pi=4PMonteCarlo算法PI計算示意圖MonteCarlo算法1.在一個平面直角坐標系下（暫定第一象限），在點（R,R）（R>0）處畫一個半徑為R的圓。

2.以這個圓畫一個外接正方形，其邊長為2R。

3.隨機取一點（X，Y）使得0<=X<=2R并且0<=Y<=2R，即隨機點在正方形內(nèi)。

4.判斷點是否在圓內(nèi)，通過公式(R-X)(R-X)+(R-Y)(R-Y)<R*R計算。

5.設所有點（也就是實驗次數(shù)）的個數(shù)為N，落在圓內(nèi)的點（滿足步驟4的點）的個數(shù)為M，則

P=M/N

于是Pi=4*N/MMonteCarlo算法簡化步驟：

1.將圓心設在原點，以R為半徑做圓，則第一象限的1/4圓面積為Pi*R*R/4

2.做該1/4圓的外接正方形,坐標為（0，0）（0，R）（R，0）（R，R），則該正方形面積為R*R

3.隨即取點（X，Y），使得0<=X<=R并且0<=Y<=R，即點在正方形內(nèi)

4.通過公式X*X+Y*Y<R*R判斷點是否在1/4圓周內(nèi)。

5.設所有點（也就是實驗次數(shù)）的個數(shù)為N，落在1/4圓內(nèi)的點（滿足步驟4的點）的個數(shù)為M，則

P=M/N

于是Pi=4*N/MMonte