姓名：李嘉蔚 學(xué)號16020520034
【嵌牛導(dǎo)讀】:其實(shí)人下棋也是隨機(jī)試幾步，找贏棋概率最大的走。Alphago就是用這個蒙特卡洛算法的。應(yīng)用這種思想的算法都是蒙特卡洛算法，它有很大的應(yīng)用，因?yàn)楝F(xiàn)實(shí)中有很多的問題都不需要求最優(yōu)解，也就是不用拉斯維加斯算法。蒙特卡羅方法于20世紀(jì)40年代美國在第二次世界大戰(zhàn)中研制原子彈的“曼哈頓計劃”計劃的成員S.M.烏拉姆
? 和J.馮·諾伊曼首先提出。數(shù)學(xué)家馮·諾伊曼用馳名世界的賭城—摩納哥的Monte Carlo—來命名這種方法，
? 為它蒙上了一層神秘色彩。在這之前，蒙特卡羅方法就已經(jīng)存在。
【嵌牛鼻子】：隨機(jī)數(shù)生成，大數(shù)定律，蒙特卡洛算法，近似最優(yōu)解。
【嵌牛提問】：什么是蒙特卡洛算法？有什么簡單應(yīng)用？
【嵌牛正文】:什么是蒙特卡洛算法？
我們通俗的來解釋一下蒙特卡洛算法：
假如籃子里有1000個蘋果，讓你每次閉著眼睛找一個最大的，可以不限制挑選次數(shù)。于是，你可以閉著眼隨機(jī)拿了一個，然后再隨機(jī)拿一個與第一個比，留下大的，再隨機(jī)拿一個，與前次留下的比較，又可以留下大的。循環(huán)往復(fù)這樣，拿的次數(shù)越多，挑出最大蘋果的可能性也就越大，但除非你把1000個蘋果都挑一遍，否則你無法肯定最終挑出來的就是最大的一個。
也就是說，蒙特卡洛算法是樣本越多，越能找到最佳的解決辦法 ，不過不保證是最好的，因?yàn)槿绻?0000個蘋果的話，說不定就能找到更大的。
可以和他形成對比的是拉斯維加斯算法：
通俗的說，假如有一把鎖，有1000把鑰匙進(jìn)行選擇，但只有1把是對的。于是每次隨機(jī)拿1把鑰匙去試，打不開就再換1把。試的次數(shù)越多，打開最優(yōu)解的機(jī)會就越大，但在打開之前，那些錯“它們的任務(wù)在于合作‘挑選’出那些比較有前途的棋步，拋棄明顯的差棋，從而將計算量控制在計算機(jī)可以完成的范圍內(nèi)。在本質(zhì)上，這和人類棋手所做的是一樣的。 ”中國科學(xué)院自動化研究所博士研究生劉加奇說。的鑰匙都是沒有用的。
“它們的任務(wù)在于合作‘挑選’出那些比較有前途的棋步，拋棄明顯的差棋，從而將計算量控制在計算機(jī)可以完成的范圍內(nèi)。在本質(zhì)上，這和人類棋手所做的是一樣的。 ”中國科學(xué)院自動化研究所博士研究生劉加奇說。
比如算圓周率：
用的就是先隨機(jī)再比較的方法。
import java.util.Random;
/**
* 隨機(jī)數(shù)計算圓周率π 蒙特卡洛算法的簡單應(yīng)用,還可用來計算積分等信息
*
* @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ī)組員的過程或系統(tǒng)的仿真都需要一種產(chǎn)生或獲得隨機(jī)數(shù)的方法。這種仿真的例子在中子隨機(jī)碰撞，數(shù)值統(tǒng)計，隊列模型，戰(zhàn)略游戲，以及其它競賽活動中都會出現(xiàn)。Monte Carlo 計算方法需要有可得的、服從特定概率分布的、隨機(jī)選取的數(shù)值序列。
其中較為普遍應(yīng)用的產(chǎn)生隨機(jī)數(shù)的方法是選取一個函數(shù)，使其將整數(shù)變換為隨機(jī)數(shù)。以某種方法選取，并按照產(chǎn)生下一個隨機(jī)數(shù)。
? 1777年，法國數(shù)學(xué)家布豐提出用投針實(shí)驗(yàn)
? 的方法求圓周率，這被認(rèn)為是蒙特卡羅方法的起源。
用擬蒙特卡羅方法求解問題的關(guān)鍵是如何找到一個均勻散布的點(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ù)這個定律知道
? 樣本數(shù)量越多，其平均就越趨近于真實(shí)值。
? 接下來用蒙特卡洛積分求自然常數(shù)。這是2015年阿里的一道筆試題。
? 首先考慮如下積分
接下來分別用蒙特卡洛積分和牛頓萊布尼茲公式計算，在蒙特卡洛方法中樣本很多時，它們的值應(yīng)該相等。
? 利用蒙特卡洛方法，圖像大致如下
上述積分的目的是求陰影部分的面積，所以先在所標(biāo)矩形內(nèi)取對隨機(jī)點(diǎn)，
? ? 對于每一對，考察是否滿足如下條件
假設(shè)滿足上述條件的點(diǎn)有個，而全部的點(diǎn)有個，所以得到近似公式為
而依據(jù)牛頓萊布尼茲公式可以得到
這兩種方法結(jié)果應(yīng)該是相等的，即有
? ? 接下來寫寫代碼吧！
代碼：
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é)果，效果還是不錯的。如下圖
