第6章隨機(jī)化算法

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

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

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

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

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

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

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

8、1;jn/2);/當(dāng)kn/2時(shí)，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素?cái)?shù)測試,試除法用2,3,去除n，判斷是否能被整除，如果能，則為合數(shù)，否則為素?cái)?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是一個(gè)素?cái)?shù)的充要條件是(n-1)!-1(modn)。費(fèi)爾馬小定理如果p是一個(gè)素?cái)?shù)且a是整數(shù)，則apa(modp)。特別地，若a不能被p整除，則ap-11(modp)。二次探測定理如果p是一個(gè)素?cái)?shù)，x是整數(shù)且0xp，則方程x21(modp)的解為x=1，p-1。,6.4拉斯維加斯算法,設(shè)p(x)是對輸入x調(diào)用拉斯維加斯算法獲得問題的一個(gè)解的概率。一個(gè)正確的拉斯維加斯算法應(yīng)該對所有輸入x均有p(x)0。在更強(qiáng)意義下，要求存在一個(gè)常數(shù)0，使得對問題的每一個(gè)實(shí)例x均有p(x)。思考：給定一個(gè)拉斯維加斯算法，設(shè)p(x

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

11、e(n);for(inti=2;i=k;i+)if(n%i=0)returni;return1;思考：該算法有什么不足？能否設(shè)計(jì)一個(gè)隨機(jī)算法進(jìn)行因子分割？,Pollard(n)算法進(jìn)行因子分割（提高概率）產(chǎn)生0n-1范圍內(nèi)的一個(gè)隨機(jī)數(shù)x，令y=x;按照產(chǎn)生一系列的xi對于k=2j（j=0,1,2,），以及，計(jì)算xi-xk與n的最大公因子d=gcd(xi-xk,n)，如果，則實(shí)現(xiàn)對n的一次分割，輸出d。,intPollard(intn)RandomNumberrnd;inti=1;intx=rnd.Random(n);/隨機(jī)整數(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個(gè)皇后放在nn棋盤的不同行、不同列、不同斜線的位置，找出相應(yīng)的放置方案隨機(jī)化措施對某行放置皇后的有效位置進(jìn)行隨機(jī)對某行所有列位置進(jìn)行隨機(jī),關(guān)鍵代碼分析boolQueen:QueensLV()RandomNumberrnd;/隨機(jī)數(shù)產(chǎn)生器intk=1;/下一個(gè)放置的皇后編號intcount=1;/記錄當(dāng)前要放置的第k個(gè)皇后在第k行的有效位置數(shù)while(k0)count=0;for(inti=1;i0)xk+=yrnd.Random(count);return(cou

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

14、w+1)+low;swap(alow,ai);intj=Partition(a,low,high);returnj;,voidrqs(inta,intleft,intright)/隨機(jī)快速排序if(leftright)intp=RandPartition(a,left,right);rqs(a,left,p-1);rqs(a,p+1,right);,6.5.2線性時(shí)間選擇,確定性算法中，首先分組，然后取每一組的中位數(shù)，再取每組中位數(shù)的中位數(shù)，最后以該中位數(shù)為基準(zhǔn)元素對n個(gè)元素進(jìn)行劃分引入隨機(jī)性成分隨機(jī)選擇一個(gè)元素作為基準(zhǔ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