計(jì)算機(jī)算法設(shè)計(jì)與分析第7章課件

1、計(jì)算機(jī)算法設(shè)計(jì)與分析第7章1第7章 概率算法計(jì)算機(jī)算法設(shè)計(jì)與分析第7章2 學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn) 理解產(chǎn)生偽隨機(jī)數(shù)的算法 掌握數(shù)值概率算法的設(shè)計(jì)思想 掌握蒙特卡羅算法的設(shè)計(jì)思想 掌握拉斯維加斯算法的設(shè)計(jì)思想 掌握舍伍德算法的設(shè)計(jì)思想計(jì)算機(jī)算法設(shè)計(jì)與分析第7章3隨機(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滿足, 2 , 1mod)(10nmcbaadann其中b0，c0，dm。d稱為該隨機(jī)序列的種子。如何選取該方法中的

2、常數(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ù)。計(jì)算機(jī)算法設(shè)計(jì)與分析第7章4數(shù)值概率算法 計(jì)算機(jī)算法設(shè)計(jì)與分析第7章5用隨機(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之比就逼近這一概率。從而4422rrnk4double Darts(int n) / 用隨機(jī)投點(diǎn)法計(jì)算值 static RandomN

3、umber 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+; return 4*k/double(n);計(jì)算機(jī)算法設(shè)計(jì)與分析第7章6計(jì)算定積分設(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)()(

4、xfrdxxfdydxxfyPnmI計(jì)算機(jī)算法設(shè)計(jì)與分析第7章7解非線性方程組求解下面的非線性方程組0),(0),(0),(21212211nnnnxxxfxxxfxxxf其中，x1,x2,xn是實(shí)變量，fi是未知量x1,x2,xn的非線性實(shí)函數(shù)。要求確定上述方程組在指定求根范圍內(nèi)的一組解*2*1,nxxx 在指定求根區(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ò)程。計(jì)算機(jī)

5、算法設(shè)計(jì)與分析第7章8舍伍德(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í)間為nXxnAAXxtnt| / )()(這顯然不能排除存在xXn使得 的可能性。希望獲得一個(gè)概率算法B，使得對(duì)問(wèn)題的輸入規(guī)模為n的每一個(gè)實(shí)例均有這就是舍伍德算法設(shè)計(jì)的基本思想。當(dāng)s(n)與tA(n)相比可忽略時(shí)，舍伍德算法可獲得很好的平均性能。)()(ntxtAA)()()(nsntxtAB計(jì)算機(jī)算法設(shè)計(jì)與分析第7章9舍伍德(Sherwood)算法復(fù)習(xí)學(xué)過(guò)的Sherwood算法：（1）

6、線性時(shí)間選擇算法（2）快速排序算法有時(shí)也會(huì)遇到這樣的情況，即所給的確定性算法無(wú)法直接改造成舍伍德型算法。此時(shí)可借助于隨機(jī)預(yù)處理技術(shù)，不改變?cè)械拇_定性算法，僅對(duì)其輸入進(jìn)行隨機(jī)洗牌，同樣可收到舍伍德算法的效果。例如，對(duì)于確定性選擇算法，可以用下面的洗牌算法shuffle將數(shù)組a中元素隨機(jī)排列，然后用確定性選擇算法求解。這樣做所收到的效果與舍伍德型算法的效果是一樣的。 templatevoid Shuffle(Type a, int n)/ 隨機(jī)洗牌算法 static RandomNumber rnd; for (int i=0;in;i+) int j=rnd.Random(n-i)+i; Sw

7、ap(ai, aj); 計(jì)算機(jī)算法設(shè)計(jì)與分析第7章10跳躍表舍伍德型算法的設(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)算。 計(jì)算機(jī)

8、算法設(shè)計(jì)與分析第7章11跳躍表在一般情況下，給定一個(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)，影響后繼元素搜索的效率。計(jì)算機(jī)算法設(shè)計(jì)與分析第7章12跳躍表為了在動(dòng)態(tài)變化中維持跳躍表中附

9、加指針的平衡性，必須使跳躍表中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)維持其平衡性。 計(jì)算機(jī)算法設(shè)計(jì)與分析第7章13跳躍表注意到，在一個(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計(jì)算機(jī)算法設(shè)計(jì)與分析第7章15n后問(wèn)題對(duì)于n后問(wèn)題的任何一個(gè)解而言，每一個(gè)皇后

11、在棋盤上的位置無(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.0465

12、13.0010.20222.11計(jì)算機(jī)算法設(shè)計(jì)與分析第7章16整數(shù)因子分解設(shè)n1是一個(gè)整數(shù)。關(guān)于整數(shù)n的因子分解問(wè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è)非平凡因子的問(wèn)題稱為整數(shù)n的因子分割問(wè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)

13、是對(duì)范圍在1x的所有整數(shù)進(jìn)行了試除而得到范圍在1x2的任一整數(shù)的因子分割。 計(jì)算機(jī)算法設(shè)計(jì)與分析第7章17Pollard算法在開(kāi)始時(shí)選取0n-1范圍內(nèi)的隨機(jī)數(shù)，然后遞歸地由產(chǎn)生無(wú)窮序列對(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計(jì)算機(jī)算法設(shè)計(jì)與分析第7章18蒙特卡羅(Monte Carlo)算法在實(shí)際應(yīng)用中常會(huì)遇到一些問(wèn)題，不

14、論采用確定性算法或概率算法都無(wú)法保證每次都能得到正確的解答。蒙特卡羅算法則在一般情況下可以保證對(duì)問(wèn)題的所有實(shí)例都以高概率給出正確解，但是通常無(wú)法判定一個(gè)具體解是否正確。設(shè)p是一個(gè)實(shí)數(shù)，且1/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, doub

15、le 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è)偏真蒙特卡羅算法，且其錯(cuò)誤概率小于。算法majorityMC所需的計(jì)算時(shí)間顯然是O(nlog(1/ )。計(jì)算機(jī)算法設(shè)計(jì)與分析第7章21素?cái)?shù)測(cè)試：對(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(

16、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 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 composi