第6章隨機化算法

1、第六章隨機化算法,教學目標理解產(chǎn)生偽隨機數(shù)的線性同余法掌握數(shù)值隨機化算法的特點及應(yīng)用掌握蒙特卡羅算法的特點及應(yīng)用掌握拉斯維加斯算法的特點及應(yīng)用掌握舍伍德算法的特點及應(yīng)用,6.1概述,6.1.1隨機化算法的類型及特點類型數(shù)值隨機化算法蒙特卡羅算法拉斯維加斯算法舍伍德算法特點數(shù)值隨機化算法常用于數(shù)值問題的求解，所得到的解往往都是近似解，而且近似解的精度隨計算時間的增加不斷提高。,蒙特卡羅算法每次均能求得問題的一個準確解，但這個解未必是正確的。求得正確解的概率依賴于算法執(zhí)行時所用的時間，所用的時間越多得到正確解的概率就越高。一般情況下，蒙特卡羅算法不能有效地確定求得的解是否正確。拉斯維加斯算法不會得

2、到不正確的解，一旦找到一個解，那么這個解肯定是正確的。但是有時候拉斯維加斯算法可能找不到解。拉斯維加斯算法得到正確解的概率隨著算法執(zhí)行時間的增加而提高。舍伍德算法不會改變對應(yīng)確定性算法的求解結(jié)果，每次運行都能夠得到問題的解，并且所得到的解是正確的,6.1.2隨機數(shù)發(fā)生器,隨機數(shù)發(fā)生器產(chǎn)生隨機數(shù)的方法偽隨機數(shù)發(fā)生器通過一個固定的、可以重復(fù)的計算方法產(chǎn)生隨機數(shù)的發(fā)生器線性同余法,d為種子；b為系數(shù)，滿足b0；c為增量，滿足c0；m為模數(shù)，滿足m0。b、c和m越大且b與m互質(zhì)可使隨機函數(shù)的隨機性能更好思考：如何產(chǎn)生0-1之間的隨機數(shù)？,/建立隨機數(shù)類RandomNumber#definem65536

3、L#defineb1194211693L#definec12345LclassRandomNumberprivate:unsignedlongd;/d為當前種子public:RandomNumber(unsignedlongs=0);/缺省值0表示由系統(tǒng)自動產(chǎn)生種子unsignedshortrandom(unsignedlongn);/產(chǎn)生0：n-1之間的隨機整數(shù)doublefRandom();/產(chǎn)生0,1)之間的隨機實數(shù);,RandomNumber:RandomNumber(unsignedlongs)if(s=0)d=time(0);/用系統(tǒng)時間產(chǎn)生種子elsed=s;/由用戶提供種子un

4、signedshortRandomNumber:random(unsignedlongn)d=b*d+c;/用線性同余計算新的種子return(unsignedshort)(d16)%n);/把d的高16位映射到0(n-1)范圍內(nèi)doubleRandomNumber:fRandom()/產(chǎn)生0,1)之間的隨機實數(shù)returnrandom(m)/double(m);,6.2數(shù)值隨機化算法,6.2.1計算的值將n個點隨機投向一個正方形，設(shè)落入此正方形內(nèi)切圓（半徑為r）中的點的數(shù)目為k，如圖6-1a）所示。,假設(shè)所投入的點落入正方形的任一點的概率相等，則所投入的點落入圓內(nèi)的概為。當n足夠大時，k與n

5、之比就逼近這一概率，從而在具體實現(xiàn)時只以第一象限為樣本且r取值為1，建立直角坐標系，如圖6-1b）所示,doubleDarts(intn)staticRandomNumberdarts;intk=0,i;doublex,y;for(i=1;i=n;i+)x=darts.fRandom();/產(chǎn)生一個0,1)之間的實數(shù)，賦給xy=darts.fRandom();/產(chǎn)生一個0,1)之間的實數(shù)，賦給yif(x*x+y*y)=1)k+;return4*k/double(n);,6.2.2計算定積分,設(shè)f(x)是0,1上的連續(xù)函數(shù)且0f(x)1，需要計算積分值。假設(shè)向單位正方形內(nèi)隨機投入n個點，如果有m

6、個點落入G內(nèi)，則I近似等于隨機點落入G內(nèi)的概率，即Im/n,doubleDarts(intn)staticRandomNumberdart;intk=0,i;doublex,y;for(i=1;i=n;i+)x=dart.fRandom();/產(chǎn)生一個0,1)之間的實數(shù)，賦給xy=dart.fRandom();/產(chǎn)生一個0,1)之間的實數(shù)，賦給yif(y=f(x)k+;returnk/double(n);,6.3蒙特卡羅算法,設(shè)p是一個實數(shù)，且0.5p1。如果蒙特卡羅算法對于問題的任一實例得到正確解的概率不小于p，則稱該算法是p正確的。對于同一實例，蒙特卡羅算法不會給出兩個不同的正確解，則稱該

7、算法是一致的。而對于一個一致的p正確的蒙特卡羅算法，要想提高獲得正確解的概率，只需執(zhí)行該算法若干次，從中選擇出現(xiàn)頻率最高的解即可。設(shè)蒙特卡羅算法是一致的p正確的。那么至少調(diào)用多少次蒙特卡羅算法，可以使得蒙特卡羅算法得到正確解的概率不低于？,問題描述設(shè)T1:n是一個含有n個元素的數(shù)組。當|i|Ti=x|n/2時，稱元素x是數(shù)組T的主元素算法描述Templateboolmajority(TypeT,intn)/判定主元素的蒙特卡羅算法RandomNumberrnd;inti=rnd.random(n)+1;/產(chǎn)生1n之間的隨機下標Typex=Ti;/隨機選擇數(shù)組元素intk=0;for(intj=

8、1;jn/2);/當kn/2時，T含有主元素,6.3.1主元素問題,boolmajorityMC(TypeT,intn,double)/重復(fù)次調(diào)用多次算法majorityintk=(int)ceil(log()/log(1-p);for(inti=1;i=k;i+)if(majority(T,n)returntrue;returnfalse;,6.3.2素數(shù)測試,試除法用2,3,去除n，判斷是否能被整除，如果能，則為合數(shù)，否則為素數(shù)。算法描述boolPrime(unsignedintn)intm=floor(sqrt(double(n);for(inti=2;i=m;i+)if(n%i=0)r

9、eturnfalse;returntrue;,Wilson定理對于給定的正整數(shù)n，判定n是一個素數(shù)的充要條件是(n-1)!-1(modn)。費爾馬小定理如果p是一個素數(shù)且a是整數(shù)，則apa(modp)。特別地，若a不能被p整除，則ap-11(modp)。二次探測定理如果p是一個素數(shù)，x是整數(shù)且0xp，則方程x21(modp)的解為x=1，p-1。,6.4拉斯維加斯算法,設(shè)p(x)是對輸入x調(diào)用拉斯維加斯算法獲得問題的一個解的概率。一個正確的拉斯維加斯算法應(yīng)該對所有輸入x均有p(x)0。在更強意義下，要求存在一個常數(shù)0，使得對問題的每一個實例x均有p(x)。思考：給定一個拉斯維加斯算法，設(shè)p(x

10、)是對輸入x調(diào)用它獲得問題的一個解的概率，s(x)和e(x)分別是算法對于具體實例x求解成功或失敗所需的平均時間，算法找到具體實例x的一個解所需的平均時間是多少？,6.4.1整數(shù)因子分解,整數(shù)因子分解將大于1的整數(shù)n分解為的形式p1,p2,pk是k個素數(shù)且p1p2pk，m1,m2,mk是k個正整數(shù)如果n是一個合數(shù)，則n必有一個非平凡因子x，1xn，使得x可以整除n。給定一個合數(shù)n，求n的一個非平凡因子的問題稱為整數(shù)n的因子分割問題。結(jié)合上節(jié)的素數(shù)測試問題，整數(shù)因子分解問題實質(zhì)上可以轉(zhuǎn)化為整數(shù)的因子分割問題,試除法進行因子分割intSplit(intn)intk=floor(sqrt(doubl

11、e(n);for(inti=2;i=k;i+)if(n%i=0)returni;return1;思考：該算法有什么不足？能否設(shè)計一個隨機算法進行因子分割？,Pollard(n)算法進行因子分割（提高概率）產(chǎn)生0n-1范圍內(nèi)的一個隨機數(shù)x，令y=x;按照產(chǎn)生一系列的xi對于k=2j（j=0,1,2,），以及，計算xi-xk與n的最大公因子d=gcd(xi-xk,n)，如果，則實現(xiàn)對n的一次分割，輸出d。,intPollard(intn)RandomNumberrnd;inti=1;intx=rnd.Random(n);/隨機整數(shù)inty=x;intk=2;,while(true)i+;x=(x*

12、x-1)%n;intd=gcd(y-x,n);if(d1)/endwhile(),6.4.2n皇后問題,問題描述n皇后問題要求將n個皇后放在nn棋盤的不同行、不同列、不同斜線的位置，找出相應(yīng)的放置方案隨機化措施對某行放置皇后的有效位置進行隨機對某行所有列位置進行隨機,關(guān)鍵代碼分析boolQueen:QueensLV()RandomNumberrnd;/隨機數(shù)產(chǎn)生器intk=1;/下一個放置的皇后編號intcount=1;/記錄當前要放置的第k個皇后在第k行的有效位置數(shù)while(k0)count=0;for(inti=1;i0)xk+=yrnd.Random(count);return(cou

13、nt0);/count0表示放置成功,boolQueen:QueensLV1(void)/棋盤上隨機放置n個皇后拉斯維加斯算法RandomNumberrnd;/隨機數(shù)產(chǎn)生器intk=1;/下一個放置的皇后編號intcount=maxcout;/嘗試產(chǎn)生隨機位置的最大次數(shù)，用戶根據(jù)需要設(shè)置while(kn);/kn表示放置成功,6.5舍伍德算法,隨機快速排序在3.5節(jié)確定性算法的基礎(chǔ)上，引入隨機性操作。隨機操作隨機選擇基準元素關(guān)鍵代碼分析intRandPartition(inta,intlow,inthigh)/隨機劃分RandomNumberrandom;inti=random(high-lo

14、w+1)+low;swap(alow,ai);intj=Partition(a,low,high);returnj;,voidrqs(inta,intleft,intright)/隨機快速排序if(leftright)intp=RandPartition(a,left,right);rqs(a,left,p-1);rqs(a,p+1,right);,6.5.2線性時間選擇,確定性算法中，首先分組，然后取每一組的中位數(shù)，再取每組中位數(shù)的中位數(shù)，最后以該中位數(shù)為基準元素對n個元素進行劃分引入隨機性成分隨機選擇一個元素作為基準元素關(guān)鍵代碼分析,templateTypeselect(Typea,intleft,intright,intk)RandomNumberrnd;if(left=right)returnaleft;inti=left,j=rnd.Random(right-left+1)+left；swap(ai,aj);j=Partition(a,left