計(jì)算機(jī)算法概率算法

計(jì)算機(jī)算法概率算法1第一頁(yè)，共二十三頁(yè)，編輯于2023年，星期五學(xué)習(xí)要點(diǎn)理解產(chǎn)生偽隨機(jī)數(shù)的算法掌握數(shù)值概率算法的設(shè)計(jì)思想掌握蒙特卡羅算法的設(shè)計(jì)思想掌握拉斯維加斯算法的設(shè)計(jì)思想掌握舍伍德算法的設(shè)計(jì)思想2第二頁(yè)，共二十三頁(yè)，編輯于2023年，星期五隨機(jī)數(shù)隨機(jī)數(shù)在概率算法設(shè)計(jì)中扮演著十分重要的角色。在現(xiàn)實(shí)計(jì)算機(jī)上無(wú)法產(chǎn)生真正的隨機(jī)數(shù)，因此在概率算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，即偽隨機(jī)數(shù)。線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法。由線性同余法產(chǎn)生的隨機(jī)序列a0,a1,…,an滿足其中b0，c0，dm。d稱為該隨機(jī)序列的種子。如何選取該方法中的常數(shù)b、c和m直接關(guān)系到所產(chǎn)生的隨機(jī)序列的隨機(jī)性能。這是隨機(jī)性理論研究的內(nèi)容，已超出本書討論的范圍。從直觀上看，m應(yīng)取得充分大，因此可取m為機(jī)器大數(shù)，另外應(yīng)取gcd(m,b)=1，因此可取b為一素?cái)?shù)。3第三頁(yè)，共二十三頁(yè)，編輯于2023年，星期五數(shù)值概率算法

4第四頁(yè)，共二十三頁(yè)，編輯于2023年，星期五用隨機(jī)投點(diǎn)法計(jì)算值

設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨機(jī)地投擲n個(gè)點(diǎn)。設(shè)落入圓內(nèi)的點(diǎn)數(shù)為k。由于所投入的點(diǎn)在正方形上均勻分布，因而所投入的點(diǎn)落入圓內(nèi)的概率為。所以當(dāng)n足夠大時(shí)，k與n之比就逼近這一概率。從而doubleDarts(intn){//用隨機(jī)投點(diǎn)法計(jì)算值

staticRandomNumberdart;intk=0;for(inti=1;i<=n;i++){doublex=dart.fRandom();doubley=dart.fRandom();if((x*x+y*y)<=1)k++;}return4*k/double(n);}5第五頁(yè)，共二十三頁(yè)，編輯于2023年，星期五計(jì)算定積分設(shè)f(x)是[0，1]上的連續(xù)函數(shù)，且0f(x)1。需要計(jì)算的積分為,積分I等于圖中的面積G。在圖所示單位正方形內(nèi)均勻地作投點(diǎn)試驗(yàn)，則隨機(jī)點(diǎn)落在曲線下面的概率為假設(shè)向單位正方形內(nèi)隨機(jī)地投入n個(gè)點(diǎn)(xi,yi)。如果有m個(gè)點(diǎn)落入G內(nèi)，則隨機(jī)點(diǎn)落入G內(nèi)的概率6第六頁(yè)，共二十三頁(yè)，編輯于2023年，星期五解非線性方程組求解下面的非線性方程組其中，x1,x2,…,xn是實(shí)變量，fi是未知量x1,x2,…,xn的非線性實(shí)函數(shù)。要求確定上述方程組在指定求根范圍內(nèi)的一組解

在指定求根區(qū)域D內(nèi)，選定一個(gè)隨機(jī)點(diǎn)x0作為隨機(jī)搜索的出發(fā)點(diǎn)。在算法的搜索過(guò)程中，假設(shè)第j步隨機(jī)搜索得到的隨機(jī)搜索點(diǎn)為xj。在第j+1步，計(jì)算出下一步的隨機(jī)搜索增量xj。從當(dāng)前點(diǎn)xj依xj得到第j+1步的隨機(jī)搜索點(diǎn)。當(dāng)x<時(shí)，取為所求非線性方程組的近似解。否則進(jìn)行下一步新的隨機(jī)搜索過(guò)程。7第七頁(yè)，共二十三頁(yè)，編輯于2023年，星期五舍伍德(Sherwood)算法設(shè)A是一個(gè)確定性算法，當(dāng)它的輸入實(shí)例為x時(shí)所需的計(jì)算時(shí)間記為tA(x)。設(shè)Xn是算法A的輸入規(guī)模為n的實(shí)例的全體，則當(dāng)問(wèn)題的輸入規(guī)模為n時(shí)，算法A所需的平均時(shí)間為這顯然不能排除存在x∈Xn使得的可能性。希望獲得一個(gè)概率算法B，使得對(duì)問(wèn)題的輸入規(guī)模為n的每一個(gè)實(shí)例均有這就是舍伍德算法設(shè)計(jì)的基本思想。當(dāng)s(n)與tA(n)相比可忽略時(shí)，舍伍德算法可獲得很好的平均性能。8第八頁(yè)，共二十三頁(yè)，編輯于2023年，星期五舍伍德(Sherwood)算法復(fù)習(xí)學(xué)過(guò)的Sherwood算法：（1）線性時(shí)間選擇算法（2）快速排序算法有時(shí)也會(huì)遇到這樣的情況，即所給的確定性算法無(wú)法直接改造成舍伍德型算法。此時(shí)可借助于隨機(jī)預(yù)處理技術(shù)，不改變?cè)械拇_定性算法，僅對(duì)其輸入進(jìn)行隨機(jī)洗牌，同樣可收到舍伍德算法的效果。例如，對(duì)于確定性選擇算法，可以用下面的洗牌算法shuffle將數(shù)組a中元素隨機(jī)排列，然后用確定性選擇算法求解。這樣做所收到的效果與舍伍德型算法的效果是一樣的。template<classType>voidShuffle(Typea[],intn){//隨機(jī)洗牌算法

staticRandomNumberrnd;for(inti=0;i<n;i++){intj=rnd.Random(n-i)+i;Swap(a[i],a[j]);}}9第九頁(yè)，共二十三頁(yè)，編輯于2023年，星期五跳躍表舍伍德型算法的設(shè)計(jì)思想還可用于設(shè)計(jì)高效的數(shù)據(jù)結(jié)構(gòu)。如果用有序鏈表來(lái)表示一個(gè)含有n個(gè)元素的有序集S，則在最壞情況下，搜索S中一個(gè)元素需要(n)計(jì)算時(shí)間。提高有序鏈表效率的一個(gè)技巧是在有序鏈表的部分結(jié)點(diǎn)處增設(shè)附加指針以提高其搜索性能。在增設(shè)附加指針的有序鏈表中搜索一個(gè)元素時(shí)，可借助于附加指針跳過(guò)鏈表中若干結(jié)點(diǎn)，加快搜索速度。這種增加了向前附加指針的有序鏈表稱為跳躍表。應(yīng)在跳躍表的哪些結(jié)點(diǎn)增加附加指針以及在該結(jié)點(diǎn)處應(yīng)增加多少指針完全采用隨機(jī)化方法來(lái)確定。這使得跳躍表可在O(logn)平均時(shí)間內(nèi)支持關(guān)于有序集的搜索、插入和刪除等運(yùn)算。10第十頁(yè)，共二十三頁(yè)，編輯于2023年，星期五跳躍表在一般情況下，給定一個(gè)含有n個(gè)元素的有序鏈表，可以將它改造成一個(gè)完全跳躍表，使得每一個(gè)k級(jí)結(jié)點(diǎn)含有k+1個(gè)指針，分別跳過(guò)2k-1，2k-1-1，…，20-1個(gè)中間結(jié)點(diǎn)。第i個(gè)k級(jí)結(jié)點(diǎn)安排在跳躍表的位置i2k處，i0。這樣就可以在時(shí)間O(logn)內(nèi)完成集合成員的搜索運(yùn)算。在一個(gè)完全跳躍表中，最高級(jí)的結(jié)點(diǎn)是logn級(jí)結(jié)點(diǎn)。完全跳躍表與完全二叉搜索樹(shù)的情形非常類似。它雖然可以有效地支持成員搜索運(yùn)算，但不適應(yīng)于集合動(dòng)態(tài)變化的情況。集合元素的插入和刪除運(yùn)算會(huì)破壞完全跳躍表原有的平衡狀態(tài)，影響后繼元素搜索的效率。11第十一頁(yè)，共二十三頁(yè)，編輯于2023年，星期五跳躍表為了在動(dòng)態(tài)變化中維持跳躍表中附加指針的平衡性，必須使跳躍表中k級(jí)結(jié)點(diǎn)數(shù)維持在總結(jié)點(diǎn)數(shù)的一定比例范圍內(nèi)。注意到在一個(gè)完全跳躍表中，50%的指針是0級(jí)指針；25%的指針是1級(jí)指針；…；(100/2k+1)%的指針是k級(jí)指針。因此，在插入一個(gè)元素時(shí)，以概率1/2引入一個(gè)0級(jí)結(jié)點(diǎn)，以概率1/4引入一個(gè)1級(jí)結(jié)點(diǎn)，…，以概率1/2k+1引入一個(gè)k級(jí)結(jié)點(diǎn)。另一方面，一個(gè)i級(jí)結(jié)點(diǎn)指向下一個(gè)同級(jí)或更高級(jí)的結(jié)點(diǎn)，它所跳過(guò)的結(jié)點(diǎn)數(shù)不再準(zhǔn)確地維持在2i-1。經(jīng)過(guò)這樣的修改，就可以在插入或刪除一個(gè)元素時(shí)，通過(guò)對(duì)跳躍表的局部修改來(lái)維持其平衡性。12第十二頁(yè)，共二十三頁(yè)，編輯于2023年，星期五跳躍表注意到，在一個(gè)完全跳躍表中，具有i級(jí)指針的結(jié)點(diǎn)中有一半同時(shí)具有i+1級(jí)指針。為了維持跳躍表的平衡性，可以事先確定一個(gè)實(shí)數(shù)0<p<1，并要求在跳躍表中維持在具有i級(jí)指針的結(jié)點(diǎn)中同時(shí)具有i+1級(jí)指針的結(jié)點(diǎn)所占比例約為p。為此目的，在插入一個(gè)新結(jié)點(diǎn)時(shí)，先將其結(jié)點(diǎn)級(jí)別初始化為0，然后用隨機(jī)數(shù)生成器反復(fù)地產(chǎn)生一個(gè)[0，1]間的隨機(jī)實(shí)數(shù)q。如果q<p，則使新結(jié)點(diǎn)級(jí)別增加1，直至qp。由此產(chǎn)生新結(jié)點(diǎn)級(jí)別的過(guò)程可知，所產(chǎn)生的新結(jié)點(diǎn)的級(jí)別為0的概率為1-p，級(jí)別為1的概率為p(1-p)，…，級(jí)別為i的概率為pi(1-p)。如此產(chǎn)生的新結(jié)點(diǎn)的級(jí)別有可能是一個(gè)很大的數(shù)，甚至遠(yuǎn)遠(yuǎn)超過(guò)表中元素的個(gè)數(shù)。為了避免這種情況，用作為新結(jié)點(diǎn)級(jí)別的上界。其中n是當(dāng)前跳躍表中結(jié)點(diǎn)個(gè)數(shù)。當(dāng)前跳躍表中任一結(jié)點(diǎn)的級(jí)別不超過(guò)13第十三頁(yè)，共二十三頁(yè)，編輯于2023年，星期五拉斯維加斯(LasVegas)算法拉斯維加斯算法的一個(gè)顯著特征是它所作的隨機(jī)性決策有可能導(dǎo)致算法找不到所需的解。voidobstinate(Objectx,Objecty){//反復(fù)調(diào)用拉斯維加斯算法LV(x,y)，直到找到問(wèn)題的一個(gè)解yboolsuccess=false;while(!success)success=lv(x,y);}設(shè)p(x)是對(duì)輸入x調(diào)用拉斯維加斯算法獲得問(wèn)題的一個(gè)解的概率。一個(gè)正確的拉斯維加斯算法應(yīng)該對(duì)所有輸入x均有p(x)>0。設(shè)t(x)是算法obstinate找到具體實(shí)例x的一個(gè)解所需的平均時(shí)間,s(x)和e(x)分別是算法對(duì)于具體實(shí)例x求解成功或求解失敗所需的平均時(shí)間，則有：解此方程可得：14第十四頁(yè)，共二十三頁(yè)，編輯于2023年，星期五n后問(wèn)題對(duì)于n后問(wèn)題的任何一個(gè)解而言，每一個(gè)皇后在棋盤上的位置無(wú)任何規(guī)律，不具有系統(tǒng)性，而更象是隨機(jī)放置的。由此容易想到下面的拉斯維加斯算法。在棋盤上相繼的各行中隨機(jī)地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至n個(gè)皇后均已相容地放置好，或已沒(méi)有下一個(gè)皇后的可放置位置時(shí)為止。如果將上述隨機(jī)放置策略與回溯法相結(jié)合，可能會(huì)獲得更好的效果。可以先在棋盤的若干行中隨機(jī)地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個(gè)解或宣告失敗。隨機(jī)放置的皇后越多，后繼回溯搜索所需的時(shí)間就越少，但失敗的概率也就越大。stopVegaspset01.0000262.00--262.0050.503933.8847.2380.39120.046513.0010.20222.1115第十五頁(yè)，共二十三頁(yè)，編輯于2023年，星期五整數(shù)因子分解設(shè)n>1是一個(gè)整數(shù)。關(guān)于整數(shù)n的因子分解問(wèn)題是找出n的如下形式的唯一分解式：其中，p1<p2<…<pk是k個(gè)素?cái)?shù)，m1,m2,…,mk是k個(gè)正整數(shù)。如果n是一個(gè)合數(shù)，則n必有一個(gè)非平凡因子x，1<x<n，使得x可以整除n。給定一個(gè)合數(shù)n，求n的一個(gè)非平凡因子的問(wèn)題稱為整數(shù)n的因子分割問(wèn)題。intSplit(intn){intm=floor(sqrt(double(n)));for(inti=2;i<=m;i++)if(n%i==0)returni;return1;}事實(shí)上，算法split(n)是對(duì)范圍在1～x的所有整數(shù)進(jìn)行了試除而得到范圍在1～x2的任一整數(shù)的因子分割。16第十六頁(yè)，共二十三頁(yè)，編輯于2023年，星期五Pollard算法在開(kāi)始時(shí)選取0～n-1范圍內(nèi)的隨機(jī)數(shù)，然后遞歸地由產(chǎn)生無(wú)窮序列對(duì)于i=2k，以及2k<j2k+1，算法計(jì)算出xj-xi與n的最大公因子d=gcd(xj-xi，n)。如果d是n的非平凡因子，則實(shí)現(xiàn)對(duì)n的一次分割，算法輸出n的因子d。voidPollard(intn){//求整數(shù)n因子分割的拉斯維加斯算法

RandomNumberrnd;inti=1;intx=rnd.Random(n);//隨機(jī)整數(shù)

inty=x;intk=2;while(true){i++;x=(x*x-1)%n;//intd=gcd(y-x,n);//求n的非平凡因子

if((d>1)&&(d<n))cout<<d<<endl;if(i==k){y=x;k*=2;}}}對(duì)Pollard算法更深入的分析可知，執(zhí)行算法的while循環(huán)約次后，Pollard算法會(huì)輸出n的一個(gè)因子p。由于n的最小素因子p，故Pollard算法可在O(n1/4)時(shí)間內(nèi)找到n的一個(gè)素因子。17第十七頁(yè)，共二十三頁(yè)，編輯于2023年，星期五蒙特卡羅(MonteCarlo)算法在實(shí)際應(yīng)用中常會(huì)遇到一些問(wèn)題，不論采用確定性算法或概率算法都無(wú)法保證每次都能得到正確的解答。蒙特卡羅算法則在一般情況下可以保證對(duì)問(wèn)題的所有實(shí)例都以高概率給出正確解，但是通常無(wú)法判定一個(gè)具體解是否正確。設(shè)p是一個(gè)實(shí)數(shù)，且1/2<p<1。如果一個(gè)蒙特卡羅算法對(duì)于問(wèn)題的任一實(shí)例得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的，且稱p-1/2是該算法的優(yōu)勢(shì)。如果對(duì)于同一實(shí)例，蒙特卡羅算法不會(huì)給出2個(gè)不同的正確解答，則稱該蒙特卡羅算法是一致的。有些蒙特卡羅算法除了具有描述問(wèn)題實(shí)例的輸入?yún)?shù)外，還具有描述錯(cuò)誤解可接受概率的參數(shù)。這類算法的計(jì)算時(shí)間復(fù)雜性通常由問(wèn)題的實(shí)例規(guī)模以及錯(cuò)誤解可接受概率的函數(shù)來(lái)描述。18第十八頁(yè)，共二十三頁(yè)，編輯于2023年，星期五蒙特卡羅(MonteCarlo)算法對(duì)于一個(gè)一致的p正確蒙特卡羅算法，要提高獲得正確解的概率，只要執(zhí)行該算法若干次，并選擇出現(xiàn)頻次最高的解即可。如果重復(fù)調(diào)用一個(gè)一致的(1/2+)正確的蒙特卡羅算法2m-1次，得到正確解的概率至少為1-，其中，對(duì)于一個(gè)解所給問(wèn)題的蒙特卡羅算法MC(x)，如果存在問(wèn)題實(shí)例的子集X使得：(1)當(dāng)xX時(shí)，MC(x)返回的解是正確的；(2)當(dāng)xX時(shí)，正確解是y0，但MC(x)返回的解未必是y0。稱上述算法MC(x)是偏y0的算法。重復(fù)調(diào)用一個(gè)一致的，p正確偏y0蒙特卡羅算法k次，可得到一個(gè)O(1-(1-p)k)正確的蒙特卡羅算法，且所得算法仍是一個(gè)一致的偏y0蒙特卡羅算法。19第十九頁(yè)，共二十三頁(yè)，編輯于2023年，星期五主元素問(wèn)題設(shè)T[1:n]是一個(gè)含有n個(gè)元素的數(shù)組。當(dāng)|{i|T[i]=x}|>n/2時(shí)，稱元素x是數(shù)組T的主元素。template<classType>boolMajority(Type*T,intn){//判定主元素的蒙特卡羅算法

inti=rnd.Random(n)+1;Typex=T[i];//隨機(jī)選擇數(shù)組元素

intk=0;for(intj=1;j<=n;j++)if(T[j]==x)k++;return(k>n/2);//k>n/2時(shí)T含有主元素}template<classType>boolMajorityMC(Type*T,intn,doublee){//重復(fù)調(diào)用算法Majorityintk=ceil(log(1/e)/log(2));for(inti=1;i<=k;i++)if(Majority(T,n))returntrue;returnfalse;}對(duì)于任何給定的>0，算法majorityMC重復(fù)調(diào)用log(1/)

次算法majority。它是一個(gè)偏真蒙特卡羅算法，且其錯(cuò)誤概率小于。算法majorityMC所需的計(jì)算時(shí)間顯然是O(nlog(1/))。20第二十頁(yè)，共二十三頁(yè)，編輯于2023年，星期五素?cái)?shù)測(cè)試Wilson定理：對(duì)于給定的正整數(shù)n，判定n是一個(gè)素?cái)?shù)的充要條件是(n-1)!-1(modn)。費(fèi)爾馬小定理：如果p是一個(gè)素?cái)?shù)，且0<a<p，則ap-1(modp)。二次探測(cè)定理：如果p是一個(gè)素?cái)?shù)，且0<x<p，則方程x21(modp)的解為x=1，p-1。voidpower(unsignedinta,unsignedintp,unsignedintn,unsignedin