蒙地卡羅方法

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

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

基本流程

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

1. 定義個系統嘅輸入嘅可能數值（定義域；domain）；
2. 用一個表示輸入數值、受定義域限制嘅概率分佈隨機噉產生一個輸入；
3. 對個輸入做決定型嘅運算；
4. 將步驟 2 同 3 重複 ${\displaystyle n}$ 咁多次，得到 ${\displaystyle n}$ 個輸出，再結合數據（aggregate）－例如計嗰 ${\displaystyle n}$ 個輸出嘅平均值。

例子

蒙地卡羅方法可以用嚟估計圓周率（${\displaystyle \pi }$）嘅數值^[2]：

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

   ${\displaystyle {\frac {m}{n}}={\frac {\pi }{4}}}$

用蒙地卡羅方法估計 ${\displaystyle \pi }$ 數值嘅圖解；圖上高嘅字顯示計出嚟個 ${\displaystyle \pi }$ 數值同 ${\displaystyle n}$ 之間嘅關係－${\displaystyle n}$ 愈大，計到出嚟嘅 ${\displaystyle \pi }$ 就愈近真嘅圓周率。

睇埋

• 蒙地卡羅樹搜尋
• 複雜系統
• 蒙地卡羅