跳去內容

蒙地卡羅方法

出自維基百科,自由嘅百科全書

蒙地卡羅方法英文Monte Carlo method)係一柞用隨機性嘅做法嚟應付決定性(deterministic)系統嘅演算法:如果話一個系統係「決定性」嘅,意思係指個系統冇隨機喺裏面,但就算一個系統係決定性嘅,個系統依然有可能會係複雜到難以用決定嘅方法解決[1]

蒙地卡羅方法源於 1940 年代。

基本流程

[編輯]

蒙地卡羅方法最基本嘅流程如下[2]

  1. 定義個系統嘅輸入嘅可能數值(定義域;domain);
  2. 用一個表示輸入數值、受定義域限制嘅概率分佈隨機噉產生一個輸入;
  3. 對個輸入做決定性嘅運算
  4. 將步驟 2 同 3 重複 咁多次,得到 個輸出,再結合數據(aggregate)-例如計嗰 個輸出嘅平均值

例子

[編輯]
用蒙地卡羅方法估計 數值嘅圖解;圖上高嘅字顯示計出嚟個 數值同 之間嘅關係- 愈大,計到出嚟嘅 就愈近真嘅圓周率。

蒙地卡羅方法可以用嚟估計圓周率)嘅數值(睇附圖)[2]

  1. 畫一個正方形,再喺個正方形入面畫個 90° 嘅扇形,任何嘅輸入坐標 都實會喺個正方形裏面(定義域);
  2. 用一個均勻分佈(uniform distribution)產生一個輸入坐標數值,「均勻分佈」意思係指每個坐標可能數值出現嘅機會率都完全一樣(睇埋隨機數生成);
  3. 喺產生咗出嚟輸入坐標數值嘅位置嗰度畫一點(做運算);
  4. 將步驟 2 同 3 重複 咁多次,然後數吓有幾多點點係喺個扇形裏面(同原點距離細過 1)嘅,設呢個數值做 ,如果 嘅數值大到接近無限大嘅話,以下呢樣嘢會成立:

睇埋

[編輯]

參考

[編輯]
  1. Kroese, D. P.; Brereton, T.; Taimre, T.; Botev, Z. I. (2014). "Why the Monte Carlo method is so important today". WIREs Comput Stat. 6 (6): 386–392.
  2. 2.0 2.1 Kalos, Malvin H.; Whitlock, Paula A. (2008). Monte Carlo Methods. Wiley-VCH.