算法設(shè)計與分析 課件 9.4-概率算法 - 蒙特卡羅算法

算法設(shè)計與分析概率算法-蒙特卡羅信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版思政：國防--催生新技術(shù)的源動力“曼哈頓計劃”摩納哥

蒙特卡羅馮·諾伊曼目標(biāo)：

求問題的準(zhǔn)確解特征：求得的解不一定正確，且無法判定所得解是否肯定正確。設(shè)p是0.5到1間的實數(shù)。若算法得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的，且p-1/2是該算法的優(yōu)勢。求得正確解的概率依賴于算法所用時間，時間越多，得到正確解的概率越高此外，若對于同一問題，蒙特卡羅算法不會給出不同的正確解答，則稱該蒙特卡羅算法是一致的。應(yīng)用：數(shù)值問題求解

求近似解

近似解精度隨計算時間的增加而不斷提高。例1：計算

值隨機投點法半徑為r的圓的外切四邊形內(nèi)投點

defdarts(n):k=0foriinrange(1,n+1):x=random()#在[0，1)內(nèi)隨機選擇一個數(shù)作為xy=random()#在[0，1)內(nèi)隨機選擇一個數(shù)作為yifx**2+y**2<=1:k+=1return4*k/n例1：計算

值測試判斷題：針對計算Pi值的蒙特卡羅算法實現(xiàn)代碼，當(dāng)n=1000時，獨立運行兩次程序，會得到一樣的結(jié)果。A：正確 B：錯誤例2：計算定積分

設(shè)f(x)是[0,1]上的連續(xù)函數(shù)，且0f(x)1。需要計算的積分為。

假設(shè)向單位正方形內(nèi)隨機地投入n個點(xi,yi)。如果有m個點落入積分區(qū)域內(nèi)，則defdarts(n):k=0foriinrange(1,n+1):x=random()#在[0，1)內(nèi)隨機選擇一個數(shù)作為xy=random()#在[0，1)內(nèi)隨機選擇一個數(shù)作為yify<=f(x):k+=1returnk/n例2：計算定積分例3：主元素問題

設(shè)數(shù)組T[1:n]含有n個元素。當(dāng)|{i|T[i]=x}|>n/2時，稱元素x是數(shù)組T的主元素。defmajority(t):n=len(t)-1i=randint(1,n)x=t[i]#隨機選擇數(shù)組元素k=0forjinrange(1,n+1):ift[j]==x:k+=1returnk>n/2#k>n/2時t含有主元素返回true時，一定含有主元素，但返回false時，數(shù)組未必不含主元素重復(fù)調(diào)用主元素蒙特卡羅算法boolmajority2(int[]t,intn){if(majority(t,n))returntrue;elsereturnmajority(t,n);}

設(shè)p是算法返回true的概率，則算法可將錯誤率降低到(1-p)2<(1/2)2=1/4。

對于任何的

>0，重復(fù)調(diào)用算法

log(1/

)