《算法設(shè)計(jì) 概率算法》由會(huì)員分享，可在線閱讀，更多相關(guān)《算法設(shè)計(jì) 概率算法（22頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn)理解產(chǎn)生偽隨機(jī)數(shù)的算法理解產(chǎn)生偽隨機(jī)數(shù)的算法掌握數(shù)值概率算法的設(shè)計(jì)思想掌握數(shù)值概率算法的設(shè)計(jì)思想 掌握蒙特卡羅算法的設(shè)計(jì)思想掌握蒙特卡羅算法的設(shè)計(jì)思想掌握拉斯維加斯算法的設(shè)計(jì)思想掌握拉斯維加斯算法的設(shè)計(jì)思想掌握舍伍德算法的設(shè)計(jì)思想掌握舍伍德算法的設(shè)計(jì)思想隨機(jī)數(shù)在概率算法設(shè)計(jì)中扮演著十分重要的角色。在現(xiàn)實(shí)計(jì)算隨機(jī)數(shù)在概率算法設(shè)計(jì)中扮演著十分重要的角色。在現(xiàn)實(shí)計(jì)算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù)，因此在概率算法中使用的隨機(jī)數(shù)機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù)，因此在概率算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，即偽隨機(jī)數(shù)。都是一定程度上隨機(jī)的，即偽隨機(jī)數(shù)。線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法。由線性

2、同余法產(chǎn)線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法。由線性同余法產(chǎn)生的隨機(jī)序列生的隨機(jī)序列a a0 0,a,a1 1,a,an n滿足滿足,2,1mod)(10nmcbaadann其中其中b b 0 0，c c 0 0，d d m m。d d稱為該隨機(jī)序列的種子。如何選取該稱為該隨機(jī)序列的種子。如何選取該方法中的常數(shù)方法中的常數(shù)b b、c c和和m m直接關(guān)系到所產(chǎn)生的隨機(jī)序列的隨機(jī)性直接關(guān)系到所產(chǎn)生的隨機(jī)序列的隨機(jī)性能。這是隨機(jī)性理論研究的內(nèi)容，能。這是隨機(jī)性理論研究的內(nèi)容，從直觀上看，從直觀上看，m m應(yīng)取得充分大，因此可取應(yīng)取得充分大，因此可取m m為機(jī)器大數(shù)，另外為機(jī)器大數(shù)，另外應(yīng)取應(yīng)取g

3、cd(m,bgcd(m,b)=1)=1，因此可取，因此可取b b為一素?cái)?shù)。為一素?cái)?shù)。設(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之比就逼近這一概率。從而4422rrnk4double Darts(int n)/用隨機(jī)投點(diǎn)法計(jì)算值 static RandomNumber dart;int k=0;for(int i=1;i=n;i+)double x=dart.fRandom();double y=dart.fRandom();if(x*x+y*y)=1)k+;re

4、turn 4*k/double(n);設(shè)f(x)是0，1上的連續(xù)函數(shù)，且0f(x)1。需要計(jì)算的積分為 ,積分I等于圖中的面積G。10)(dxxfI在圖所示單位正方形內(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)的概率 10)(010)()(xfrdxxfdydxxfyPnmI求解下面的非線性方程組0),(0),(0),(21212211nnnnxxxfxxxfxxxf其中，x1,x2,xn是實(shí)變量，fi是未知量x1,x2,xn的非線性實(shí)函數(shù)。要求確定上述方程組在指定求根范圍內(nèi)的一組解*2*1,nxxx

5、在指定求根區(qū)域D內(nèi)，選定一個(gè)隨機(jī)點(diǎn)x0作為隨機(jī)搜索的出發(fā)點(diǎn)。在算法的搜索過程中，假設(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ī)搜索過程。設(shè)A是一個(gè)確定性算法，當(dāng)它的輸入實(shí)例為x時(shí)所需的計(jì)算時(shí)間記為tA(x)。設(shè)Xn是算法A的輸入規(guī)模為n的實(shí)例的全體，則當(dāng)問題的輸入規(guī)模為n時(shí)，算法A所需的平均時(shí)間為nXxnAAXxtnt|/)()(這顯然不能排除存在xXn使得 的可能性。希望獲得一個(gè)概率算法B，使得對(duì)問題的輸入規(guī)模為n的每一個(gè)實(shí)例均有這就是舍伍德算法

6、設(shè)計(jì)的基本思想。當(dāng)s(n)與tA(n)相比可忽略時(shí)，舍伍德算法可獲得很好的平均性能。)()(ntxtAA)()()(nsntxtABSherwood算法：（1）線性時(shí)間選擇算法（2）快速排序算法有時(shí)也會(huì)遇到這樣的情況，即所給的確定性算法無法直接改造成舍伍德型算法。此時(shí)可借助于隨機(jī)預(yù)處理技術(shù)，不改變?cè)械拇_定性算法，僅對(duì)其輸入進(jìn)行隨機(jī)洗牌，同樣可收到舍伍德算法的效果。例如，對(duì)于確定性選擇算法，可以用下面的洗牌算法shuffle將數(shù)組a中元素隨機(jī)排列，然后用確定性選擇算法求解。這樣做所收到的效果與舍伍德型算法的效果是一樣的。templatevoid Shuffle(Type a,int n)/隨機(jī)

7、洗牌算法 static RandomNumber rnd;for(int i=0;in;i+)int j=rnd.Random(n-i)+i;Swap(ai,aj);舍伍德型算法的設(shè)計(jì)思想還可用于設(shè)計(jì)高效的數(shù)據(jù)結(jié)構(gòu)。如果用有序鏈表來表示一個(gè)含有n個(gè)元素的有序集S，則在最壞情況下，搜索S中一個(gè)元素需要(n)計(jì)算時(shí)間。提高有序鏈表效率的一個(gè)技巧是在有序鏈表的部分結(jié)點(diǎn)處增設(shè)附加指針以提高其搜索性能。在增設(shè)附加指針的有序鏈表中搜索一個(gè)元素時(shí)，可借助于附加指針跳過鏈表中若干結(jié)點(diǎn)，加快搜索速度。這種增加了向前附加指針的有序鏈表稱為跳躍表。應(yīng)在跳躍表的哪些結(jié)點(diǎn)增加附加指針以及在該結(jié)點(diǎn)處應(yīng)增加多少指針完全采用

8、隨機(jī)化方法來確定。這使得跳躍表可在O(logn)平均時(shí)間內(nèi)支持關(guān)于有序集的搜索、插入和刪除等運(yùn)算。在一般情況下，給定一個(gè)含有n個(gè)元素的有序鏈表，可以將它改造成一個(gè)完全跳躍表，使得每一個(gè)k級(jí)結(jié)點(diǎn)含有k+1個(gè)指針，分別跳過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)。完全跳躍表與完全二叉搜索樹的情形非常類似。它雖然可以有效地支持成員搜索運(yùn)算，但不適應(yīng)于集合動(dòng)態(tài)變化的情況。集合元素的插入和刪除運(yùn)算會(huì)破壞完全跳躍表原有的平衡狀態(tài)，影響后繼元素搜索的效率

9、。為了在動(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)，它所跳過的結(jié)點(diǎn)數(shù)不再準(zhǔn)確地維持在2i-1。經(jīng)過這樣的修改，就可以在插入或刪除一個(gè)元素時(shí)，通過對(duì)跳躍表的局部修改來維持其平衡性。注意到，在一個(gè)完全跳躍表中，具有i級(jí)指針的結(jié)點(diǎn)中有一半同時(shí)具有i+1級(jí)指針。為了維持

10、跳躍表的平衡性，可以事先確定一個(gè)實(shí)數(shù)0p1，并要求在跳躍表中維持在具有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。如果q0。設(shè)t(x)是算法obstinate找到具體實(shí)例x的一個(gè)解所需的平均時(shí)間,s(x)和e(x)分別是算法對(duì)于具體實(shí)例x求解成功或求解失敗所需的平均時(shí)間，則有：解此方程可得：)()()(1()()()(xtxexpxsxpxt)()()(1)()(xexpxpxsxt對(duì)于n后問題的任何一個(gè)解而言，每一個(gè)皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨

11、機(jī)放置的。由此容易想到下面的拉斯維加斯算法。在棋盤上相繼的各行中隨機(jī)地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至n個(gè)皇后均已相容地放置好，或已沒有下一個(gè)皇后的可放置位置時(shí)為止。如果將上述隨機(jī)放置策略與回溯法相結(jié)合，可能會(huì)獲得更好的效果?？梢韵仍谄灞P的若干行中隨機(jī)地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個(gè)解或宣告失敗。隨機(jī)放置的皇后越多，后繼回溯搜索所需的時(shí)間就越少，但失敗的概率也就越大。如果將上述隨機(jī)放置策略與回溯法相結(jié)合，可能會(huì)獲得更好的效果?？梢韵仍谄灞P的若干行中隨機(jī)地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個(gè)解或宣告失敗。隨機(jī)放置的皇后越多，后繼

12、回溯搜索所需的時(shí)間就越少，但失敗的概率也就越大。設(shè)n1是一個(gè)整數(shù)。關(guān)于整數(shù)n的因子分解問題是找出n的如下形式的唯一分解式：其中，p1p2pk是k個(gè)素?cái)?shù)，m1,m2,mk是k個(gè)正整數(shù)。如果n是一個(gè)合數(shù)，則n必有一個(gè)非平凡因子x，1xn，使得x可以整除n。給定一個(gè)合數(shù)n，求n的一個(gè)非平凡因子的問題稱為整數(shù)n的因子分割問題。kmkmmpppn2121int Split(int n)int m=floor(sqrt(double(n);for(int i=2;i=m;i+)if(n%i=0)return i;return 1;事實(shí)上，算法split(n)是對(duì)范圍在1x的所有整數(shù)進(jìn)行了試除而得到范圍在1

13、x2的任一整數(shù)的因子分割。在開始時(shí)選取0n-1范圍內(nèi)的隨機(jī)數(shù)，然后遞歸地由產(chǎn)生無窮序列對(duì)于i=2k，以及2k1)&(dn)coutdendl;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è)素因子。np在實(shí)際應(yīng)用中常會(huì)遇到一些問題，不論采用確定性算法或概率算法都無法保證每次都能得到正確的解答。蒙特卡羅算法則在一般情況下可以保證對(duì)問題的所有實(shí)例都以高概率給出正確解，但是通常無法判定一個(gè)具體解是否正確。設(shè)p是一個(gè)實(shí)數(shù)，且1/

14、2pn/2時(shí)，稱元素x是數(shù)組T的主元素。templatebool Majority(Type*T,int n)/判定主元素的蒙特卡羅算法 int i=rnd.Random(n)+1;Type x=Ti;/隨機(jī)選擇數(shù)組元素 int k=0;for(int j=1;jn/2);/kn/2 時(shí)T含有主元素templatebool MajorityMC(Type*T,int n,double e)/重復(fù)調(diào)用算法Majority int k=ceil(log(1/e)/log(2);for(int i=1;i0，算法majorityMC重復(fù)調(diào)用log(1/)次算法majority。它是一個(gè)偏真蒙特卡羅算

15、法，且其錯(cuò)誤概率小于。算法majorityMC所需的計(jì)算時(shí)間顯然是O(nlog(1/)。：對(duì)于給定的正整數(shù)n，判定n是一個(gè)素?cái)?shù)的充要條件是(n-1)!-1(mod n)。：如果p是一個(gè)素?cái)?shù)，且0ap，則ap-1(mod p)。：如果p是一個(gè)素?cái)?shù)，且0 xp，則方程x21(mod p)的解為x=1，p-1。void power(unsigned int a,unsigned int p,unsigned int n,unsigned int&result,bool&composite)/計(jì)算mod n，并實(shí)施對(duì)n的二次探測(cè) unsigned int x;if(p=0)result=1;else

16、power(a,p/2,n,x,composite);/遞歸計(jì)算 result=(x*x)%n;/二次探測(cè) if(result=1)&(x!=1)&(x!=n-1)composite=true;if(p%2)=1)/p是奇數(shù) result=(result*a)%n;bool Prime(unsigned int n)/素?cái)?shù)測(cè)試的蒙特卡羅算法 RandomNumber rnd;unsigned int a,result;bool composite=false;a=rnd.Random(n-3)+2;power(a,n-1,n,result,composite);if(composite|(result!=1)return false;else return true;算法prime是一個(gè)偏假3/4正確的蒙特卡羅算法。通過多次重復(fù)調(diào)用錯(cuò)誤概率不超過(1/4)k。這是一個(gè)很保守的估計(jì)，實(shí)際使用的效果要好得多。