|
姓名：李嘉蔚 學(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é)院自動化研究所博士研究生劉加奇說。 比如算圓周率：  圖片發(fā)自簡書App 用的就是先隨機(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)計，隊(duì)列模型，戰(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年阿里的一道筆試題。 ? 首先考慮如下積分  圖片發(fā)自簡書App 接下來分別用蒙特卡洛積分和牛頓萊布尼茲公式計算，在蒙特卡洛方法中樣本很多時，它們的值應(yīng)該相等。 ? 利用蒙特卡洛方法，圖像大致如下  圖片發(fā)自簡書App 上述積分的目的是求陰影部分的面積，所以先在所標(biāo)矩形內(nèi)取對隨機(jī)點(diǎn)， ? ? 對于每一對，考察是否滿足如下條件  圖片發(fā)自簡書App 假設(shè)滿足上述條件的點(diǎn)有個，而全部的點(diǎn)有個，所以得到近似公式為  圖片發(fā)自簡書App 而依據(jù)牛頓萊布尼茲公式可以得到  圖片發(fā)自簡書App 這兩種方法結(jié)果應(yīng)該是相等的，即有  圖片發(fā)自簡書App ? ? 接下來寫寫代碼吧！ 代碼： 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é)果，效果還是不錯的。如下圖  圖片發(fā)自簡書App |
|
|
