1946年，美國(guó)拉斯阿莫斯國(guó)家實(shí)驗(yàn)室的三位科學(xué)家John von Neumann,Stan Ulam 和 Nick Metropolis共同發(fā)明，被稱為蒙特卡洛方法。
它的具體定義是：
在廣場(chǎng)上畫一個(gè)邊長(zhǎng)一米的正方形，在正方形內(nèi)部隨意用粉筆畫一個(gè)不規(guī)則的形狀，現(xiàn)在要計(jì)算這個(gè)不規(guī)則圖形的面積，怎么計(jì)算列?蒙特卡洛(Monte Carlo)方法告訴我們，均勻的向該正方形內(nèi)撒N（N 是一個(gè)很大的自然數(shù)）個(gè)黃豆，隨后數(shù)數(shù)有多少個(gè)黃豆在這個(gè)不規(guī)則幾何形狀內(nèi)部，比如說(shuō)有M個(gè)，那么，這個(gè)奇怪形狀的面積便近似于M/N，N越大，算出來(lái)的 值便越精確。在這里我們要假定豆子都在一個(gè)平面上，相互之間沒有重疊。
蒙特卡洛方法可用于近似計(jì)算圓周率：讓計(jì)算機(jī)每次隨機(jī)生成兩 個(gè)0到1之間的數(shù)，看這兩個(gè)實(shí)數(shù)是否在單位圓內(nèi)。生成一系列隨機(jī)點(diǎn)，統(tǒng)計(jì)單位圓內(nèi)的點(diǎn)數(shù)與總點(diǎn)數(shù)，（圓面積和正方形面積之比為PI:1，PI為圓周率）， 當(dāng)隨機(jī)點(diǎn)取得越多（但即使取10的9次方個(gè)隨機(jī)點(diǎn)時(shí)，其結(jié)果也僅在前4位與圓周率吻合）時(shí)，其結(jié)果越接近于圓周率。
（以上摘自《20世紀(jì)最偉大的10個(gè)算法》）
讓我們來(lái)看一下這個(gè)圖：
圖中黃色區(qū)域?yàn)橐粏挝粓A，半徑r=1。其外接正方形邊長(zhǎng)為2。我們可以看到，外接正方形與坐標(biāo)軸將該單位圓切成四等分，而每個(gè)小正方形的面積為1*1=1。這樣，為了求出小正方形里的扇形面積，我們利用計(jì)算機(jī)強(qiáng)大的計(jì)算能力，往小正方形里投入無(wú)數(shù)個(gè)隨機(jī)點(diǎn)。假設(shè)投進(jìn)扇形里的點(diǎn)總數(shù)為c_sum，投進(jìn)小正方形里的點(diǎn)（包含投進(jìn)扇形的點(diǎn)）總數(shù)為sum，那么根據(jù)公式c_sum / sum = area / 1，即可計(jì)算出該扇形的面積 = c_sum / sum。由此可得到圓的面積area = c_sum / sum * 4。
我們知道，單位圓的半徑r=1，所以實(shí)際上求單位圓的面積就是求出PI的數(shù)值。隨機(jī)點(diǎn)數(shù)量取值越大，那么PI值就越精確。
1 /**
2 * 利用蒙特卡洛算法（Mente Carlo Method）計(jì)算單位圓面積
3 *
4 */
5
6 import java.util.Random;
7
8 public class MonteCarloMethodTest
9 {
10 public static void main(String[] args)
11 {
12 int sum = 0;
13 int c_sum = 0;
14 double x;
15 double y;
16 Random ra = new Random();
17
18 int i = 0;
19 while (i != 100000000)
20 {
21 x = ra.nextDouble();
22 y = ra.nextDouble();
23
24 if (x * x + y * y <= 1)
25 ++c_sum;
26 ++sum;
27 ++i;
28 }
29
30 double area = (double)c_sum / sum * 4;
31 System.out.println("area = " + area);
32 }
33 }
在這個(gè)程序中，總共在小正方形里生成了
100000000個(gè)隨機(jī)點(diǎn)。通過判斷生成的隨機(jī)點(diǎn)距離圓心點(diǎn)的距離來(lái)判斷生成的點(diǎn)是否在單位圓內(nèi)。
運(yùn)行10次，結(jié)果如下：
area = 3.14172004
area = 3.14182308
area = 3.14190064
area = 3.14139992
area = 3.14176768
area = 3.14177084
area = 3.14142864
area = 3.14176596
area = 3.14191927
area = 3.14172096
我們知道，較為精確的PI數(shù)值為3.14159265……
所以即使計(jì)算機(jī)已經(jīng)模擬到100000000個(gè)隨機(jī)點(diǎn)，也只能大致精確到小數(shù)點(diǎn)后3位，而為了模擬這100000000個(gè)點(diǎn)，我的Y560筆記本也平均要花費(fèi)5秒的時(shí)間來(lái)進(jìn)行運(yùn)算，如果再增加幾個(gè)0……
蒙特卡洛算法是1946年提出來(lái)的，當(dāng)時(shí)沒有運(yùn)行速度如此快的現(xiàn)代計(jì)算機(jī)。不過由于現(xiàn)代計(jì)算機(jī)的運(yùn)算速度不斷提高，借助于其強(qiáng)大的計(jì)算能力，我們可以將蒙特卡洛運(yùn)用在工程中的很多需要近似求解的地方。