蒙地卡羅模擬(Monte Carlo Simulation)也稱作蒙地卡羅方法(Monte Carlo Method),或者也有人比較直白的一點直接把它就作「統計類比法」。這個方法是 John von Neumann、Stanislaw Ulam、Nicholas Metropolis,這幾位大神聯合出品的。話說你知道不論是現今你所使用的電腦、筆電、智慧型手機、甚至嵌入式裝置用的MCU基本上都還是採用當初 Von Neumann 提出的 Architecture / Model 嗎。
回到演算法上面,那麼為什麼會叫作蒙地卡羅呢? 據說是因為 Ulam 的叔叔當時常在摩納哥的蒙地卡羅賭場輸錢而得名的xD 不過會跟賭場扯上關係也正因為,它一種以機率統計理論為基礎的數值計算方法。 不得不說蒙地卡羅這個方法真的蠻好用的,可以被應用在很多領域 e.g. 金融工程、經濟學、生醫、熱力學、空氣力學、量子力學,甚至在資工領域被應用在近幾年很夯的機械學習(Machine Learning)上。 你大概只要有一個概念就是,有機率有模型就可以用蒙地卡羅來模擬! 接下來,我們就以最常見的用蒙地卡羅方法求圓周率(π)的值,來看看蒙地卡羅方法到底是怎麼做的。 在解決實際問題的時候應用蒙地卡羅方法主要有兩部分工作:
那麼我們把這個想法套在求圓周率(π)上面,
我們可以在一個2*2的正方形裡面劃出一個半徑為1的圓(此時圓的面積為π), 電腦設出去的飛鏢會命中區域內的哪一個點完全是隨機的(每一個點被射中的機率是一樣的)。 那麼根據統計與機率的理論告訴我們, 電腦射出去後中命圓的機率為:π/4,命中圓以外區域的機率為:1 - π/4。 假設我們 N=100,飛鏢射出去命中了78 發,則我們就可以預估圓周率(π) 約為:(78/100)*4 = 3.12。 當然啦~ 有背過圓周率的你一定會說 wait wait wait what 不對欸 不對 π 明明就等於3.1415926... 由於蒙地卡羅方法是基於統計跟機率,所以你也能想像其實上面範例中的N有一點太小了,答案容易在一個比較大的區間範圍內震盪,如果今天這個N 變的非常非常的大,那麼這個答案就會收斂在一個比較小的區間,算出來的答案就會非常接近正確答案了!參見下圖:
最後附上 Jason 自己用蒙地卡羅方法求解 π 值的程式碼與實作結果給你們參考。【程式碼下載】
下方是 WiKipedia 提供的使用蒙地卡羅算 π 值 , n=3000、4000、5000、6500、8500、10000、15000、18000、24000、30000 求出的 π 值以及視覺呈現的 gif 圖。
0 評論
發表回覆。 |
Jason Chen人不光是生來就擁有一切,而是靠他從學習中得到的一切來造就自己。- 歌德 文章分類
全部
封存檔
九月 2023
|