姓名：李嘉蔚 學(xué)號(hào)16020520034

【嵌牛導(dǎo)讀】:其實(shí)人下棋也是隨機(jī)試幾步，找贏棋概率最大的走。Alphago就是用這個(gè)蒙特卡洛算法的。應(yīng)用這種思想的算法都是蒙特卡洛算法，它有很大的應(yīng)用，因?yàn)楝F(xiàn)實(shí)中有很多的問題都不需要求最優(yōu)解，也就是不用拉斯維加斯算法。蒙特卡羅方法于20世紀(jì)40年代美國(guó)在第二次世界大戰(zhàn)中研制原子彈的“曼哈頓計(jì)劃”計(jì)劃的成員S.M.烏拉姆

? 和J.馮·諾伊曼首先提出。數(shù)學(xué)家馮·諾伊曼用馳名世界的賭城—摩納哥的Monte Carlo—來(lái)命名這種方法，

? 為它蒙上了一層神秘色彩。在這之前，蒙特卡羅方法就已經(jīng)存在。

【嵌牛鼻子】：隨機(jī)數(shù)生成，大數(shù)定律，蒙特卡洛算法，近似最優(yōu)解。

【嵌牛提問】：什么是蒙特卡洛算法？有什么簡(jiǎn)單應(yīng)用？

【嵌牛正文】:什么是蒙特卡洛算法？

我們通俗的來(lái)解釋一下蒙特卡洛算法：

假如籃子里有1000個(gè)蘋果，讓你每次閉著眼睛找一個(gè)最大的，可以不限制挑選次數(shù)。于是，你可以閉著眼隨機(jī)拿了一個(gè)，然后再隨機(jī)拿一個(gè)與第一個(gè)比，留下大的，再隨機(jī)拿一個(gè)，與前次留下的比較，又可以留下大的。循環(huán)往復(fù)這樣，拿的次數(shù)越多，挑出最大蘋果的可能性也就越大，但除非你把1000個(gè)蘋果都挑一遍，否則你無(wú)法肯定最終挑出來(lái)的就是最大的一個(gè)。

也就是說(shuō)，蒙特卡洛算法是樣本越多，越能找到最佳的解決辦法 ，不過(guò)不保證是最好的，因?yàn)槿绻?0000個(gè)蘋果的話，說(shuō)不定就能找到更大的。

可以和他形成對(duì)比的是拉斯維加斯算法：

通俗的說(shuō)，假如有一把鎖，有1000把鑰匙進(jìn)行選擇，但只有1把是對(duì)的。于是每次隨機(jī)拿1把鑰匙去試，打不開就再換1把。試的次數(shù)越多，打開最優(yōu)解的機(jī)會(huì)就越大，但在打開之前，那些錯(cuò)“它們的任務(wù)在于合作‘挑選’出那些比較有前途的棋步，拋棄明顯的差棋，從而將計(jì)算量控制在計(jì)算機(jī)可以完成的范圍內(nèi)。在本質(zhì)上，這和人類棋手所做的是一樣的。 ”中國(guó)科學(xué)院自動(dòng)化研究所博士研究生劉加奇說(shuō)。的鑰匙都是沒有用的。

“它們的任務(wù)在于合作‘挑選’出那些比較有前途的棋步，拋棄明顯的差棋，從而將計(jì)算量控制在計(jì)算機(jī)可以完成的范圍內(nèi)。在本質(zhì)上，這和人類棋手所做的是一樣的。 ”中國(guó)科學(xué)院自動(dòng)化研究所博士研究生劉加奇說(shuō)。

比如算圓周率：

圖片發(fā)自簡(jiǎn)書App

用的就是先隨機(jī)再比較的方法。

import java.util.Random;

/**

* 隨機(jī)數(shù)計(jì)算圓周率π 蒙特卡洛算法的簡(jiǎn)單應(yīng)用,還可用來(lái)計(jì)算積分等信息

*

* @author admin

*

*/

public class PI {

/**

? * 判斷落點(diǎn)是否在圓內(nèi)部 勾股定理 x2 + y2 = r2 ,那么 x2 + y2 <= r2="">

? *

? * @param x

? * @param y

? * @return

? */

public boolean isInCycle(double x, double y) {

? if (x * x + y * y <= 1)="">

? return true;

? } else {

? return false;

? }

}

public double getPi(int count) {

? Random random = new Random();

? double in = 0;

? for (int i = 0; i < count;="" i++)="">

? double x = random.nextDouble();

? double y = random.nextDouble();

? if (isInCycle(x, y)) {

? ? in++;

? }

? }

? System.out.println(in + '/' + count);

? return 4 * in / count;

}

/**

? * 判斷落點(diǎn)在積分線下的區(qū)域

? *

? * @param x

? * @param y

? * @return

? */

public boolean isInRegion(double x, double y) {

? if (y <= x="" *="" x)="">

? return true;

? } else {

? return false;

? }

}

public double getJifen(int count) {

? Random random = new Random();

? double in = 0;

? for (int i = 0; i < count;="" i++)="">

? double x = random.nextDouble();

? double y = random.nextDouble();

? if (isInRegion(x, y)) {

? ? in++;

? }

? }

? System.out.println(in + '/' + count);

? return in / count;

}

public static void main(String[] args) {

? PI p = new PI();

? // 求π,可以增加循環(huán)次數(shù)獲取更精確結(jié)果

? System.out.println(p.getPi(1000000));

? // 求積分

? System.out.println(p.getJifen(1000000));

}

}

輸出結(jié)果:

785238.0/1000000

3.140952

332700.0/1000000

0.3327

任何本質(zhì)上屬隨機(jī)組員的過(guò)程或系統(tǒng)的仿真都需要一種產(chǎn)生或獲得隨機(jī)數(shù)的方法。這種仿真的例子在中子隨機(jī)碰撞，數(shù)值統(tǒng)計(jì)，隊(duì)列模型，戰(zhàn)略游戲，以及其它競(jìng)賽活動(dòng)中都會(huì)出現(xiàn)。Monte Carlo 計(jì)算方法需要有可得的、服從特定概率分布的、隨機(jī)選取的數(shù)值序列。

其中較為普遍應(yīng)用的產(chǎn)生隨機(jī)數(shù)的方法是選取一個(gè)函數(shù)，使其將整數(shù)變換為隨機(jī)數(shù)。以某種方法選取，并按照產(chǎn)生下一個(gè)隨機(jī)數(shù)。

? 1777年，法國(guó)數(shù)學(xué)家布豐提出用投針實(shí)驗(yàn)

? 的方法求圓周率，這被認(rèn)為是蒙特卡羅方法的起源。

用擬蒙特卡羅方法求解問題的關(guān)鍵是如何找到一個(gè)均勻散布的點(diǎn)集。目前常用的點(diǎn)集有GLP點(diǎn)集(好格

? 子點(diǎn)集，good lattice point set)、GP點(diǎn)集(好點(diǎn)集，good point set)、Halton點(diǎn)集及其變體、

? Hammersley點(diǎn)集等。

? 蒙特卡洛方法的理論基礎(chǔ)是大數(shù)定律。大數(shù)定律是描述相當(dāng)多次數(shù)重復(fù)試驗(yàn)的結(jié)果的定律，根據(jù)這個(gè)定律知道

? 樣本數(shù)量越多，其平均就越趨近于真實(shí)值。

? 接下來(lái)用蒙特卡洛積分求自然常數(shù)。這是2015年阿里的一道筆試題。

? 首先考慮如下積分

圖片發(fā)自簡(jiǎn)書App

接下來(lái)分別用蒙特卡洛積分和牛頓萊布尼茲公式計(jì)算，在蒙特卡洛方法中樣本很多時(shí)，它們的值應(yīng)該相等。

? 利用蒙特卡洛方法，圖像大致如下

圖片發(fā)自簡(jiǎn)書App

上述積分的目的是求陰影部分的面積，所以先在所標(biāo)矩形內(nèi)取對(duì)隨機(jī)點(diǎn)，

? ? 對(duì)于每一對(duì)，考察是否滿足如下條件

圖片發(fā)自簡(jiǎn)書App

假設(shè)滿足上述條件的點(diǎn)有個(gè)，而全部的點(diǎn)有個(gè)，所以得到近似公式為

圖片發(fā)自簡(jiǎn)書App

而依據(jù)牛頓萊布尼茲公式可以得到

圖片發(fā)自簡(jiǎn)書App

這兩種方法結(jié)果應(yīng)該是相等的，即有

圖片發(fā)自簡(jiǎn)書App

? ? 接下來(lái)寫寫代碼吧！

代碼：

1 #include? 2 3#define MAX_ITERS 10000000

4 5usingnamespace std;

6 7struct Point

8{

9double x, y;

10};

1112double Rand(double L, double R)?

13{?

14return L + (R - L) * rand() * 1.0 / RAND_MAX;?

15}

1617Point getPoint()

18{

19? ? Point t;

20? ? t.x = Rand(1.0, 2.0);

21? ? t.y = Rand(0.0, 1.0);

22return t;

23}

2425double getResult()

26{

27int m = 0;

28int n = MAX_ITERS;

29? ? srand(time(NULL));

30for(int i = 0; i < n;="">

31? ? {

32? ? ? ? Point t = getPoint();

33double res = t.x * t.y;

34if(res <=>

35? ? ? ? ? ? m++;

36? ? }

37return pow(2.0, 1.0 * n / m);

38}

3940int main()

41{

42for(int i = 0; i < 20;="">

43? ? ? ? cout <>< setprecision(6)="">< getresult()=""><>

44return0;

45 }

觀察一下運(yùn)行結(jié)果，效果還是不錯(cuò)的。如下圖

圖片發(fā)自簡(jiǎn)書App