算法設計概率算法

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

2、同余法產線性同余法是產生偽隨機數的最常用的方法。由線性同余法產生的隨機序列生的隨機序列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稱為該隨機序列的種子。如何選取該稱為該隨機序列的種子。如何選取該方法中的常數方法中的常數b b、c c和和m m直接關系到所產生的隨機序列的隨機性直接關系到所產生的隨機序列的隨機性能。這是隨機性理論研究的內容，能。這是隨機性理論研究的內容，從直觀上看，從直觀上看，m m應取得充分大，因此可取應取得充分大，因此可取m m為機器大數，另外為機器大數，另外

3、應取應取gcd(m,bgcd(m,b)=1)=1，因此可取，因此可取b b為一素數。為一素數。設有一半徑為r的圓及其外切四邊形。向該正方形隨機地投擲n個點。設落入圓內的點數為k。由于所投入的點在正方形上均勻分布，因而所投入的點落入圓內的概率為 。所以當n足夠大時，k與n之比就逼近這一概率。從而4422rrnk4double Darts(int n) / 用隨機投點法計算值 static RandomNumber dart; int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if (x

4、*x+y*y)=1) k+; return 4*k/double(n);設f(x)是0，1上的連續(xù)函數，且0f(x)1。需要計算的積分為 ,積分I等于圖中的面積G。10)(dxxfI在圖所示單位正方形內均勻地作投點試驗，則隨機點落在曲線下面的概率為假設向單位正方形內隨機地投入n個點(xi,yi)。如果有m個點落入G內，則隨機點落入G內的概率 10)(010)()(xfrdxxfdydxxfyPnmI求解下面的非線性方程組0),(0),(0),(21212211nnnnxxxfxxxfxxxf其中，x1,x2,xn是實變量，fi是未知量x1,x2,xn的非線性實函數。要求確定上述方程組在指定求根

5、范圍內的一組解*2*1,nxxx 在指定求根區(qū)域D內，選定一個隨機點x0作為隨機搜索的出發(fā)點。在算法的搜索過程中，假設第j步隨機搜索得到的隨機搜索點為xj。在第j+1步，計算出下一步的隨機搜索增量xj。從當前點xj依xj得到第j+1步的隨機搜索點。當x時，取為所求非線性方程組的近似解。否則進行下一步新的隨機搜索過程。設A是一個確定性算法，當它的輸入實例為x時所需的計算時間記為tA(x)。設Xn是算法A的輸入規(guī)模為n的實例的全體，則當問題的輸入規(guī)模為n時，算法A所需的平均時間為nXxnAAXxtnt| / )()(這顯然不能排除存在xXn使得 的可能性。希望獲得一個概率算法B，使得對問題的輸入規(guī)

6、模為n的每一個實例均有這就是舍伍德算法設計的基本思想。當s(n)與tA(n)相比可忽略時，舍伍德算法可獲得很好的平均性能。)()(ntxtAA)()()(nsntxtABSherwood算法：（1）線性時間選擇算法（2）快速排序算法有時也會遇到這樣的情況，即所給的確定性算法無法直接改造成舍伍德型算法。此時可借助于隨機預處理技術，不改變原有的確定性算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德算法的效果。例如，對于確定性選擇算法，可以用下面的洗牌算法shuffle將數組a中元素隨機排列，然后用確定性選擇算法求解。這樣做所收到的效果與舍伍德型算法的效果是一樣的。 templatevoid Shuf

7、fle(Type a, int n)/ 隨機洗牌算法 static RandomNumber rnd; for (int i=0;in;i+) int j=rnd.Random(n-i)+i; Swap(ai, aj); 舍伍德型算法的設計思想還可用于設計高效的數據結構。如果用有序鏈表來表示一個含有n個元素的有序集S，則在最壞情況下，搜索S中一個元素需要(n)計算時間。提高有序鏈表效率的一個技巧是在有序鏈表的部分結點處增設附加指針以提高其搜索性能。在增設附加指針的有序鏈表中搜索一個元素時，可借助于附加指針跳過鏈表中若干結點，加快搜索速度。這種增加了向前附加指針的有序鏈表稱為跳躍表。應在跳躍表的

8、哪些結點增加附加指針以及在該結點處應增加多少指針完全采用隨機化方法來確定。這使得跳躍表可在O(logn)平均時間內支持關于有序集的搜索、插入和刪除等運算。 在一般情況下，給定一個含有n個元素的有序鏈表，可以將它改造成一個完全跳躍表，使得每一個k級結點含有k+1個指針，分別跳過2k-1，2k-1-1，20-1個中間結點。第i個k級結點安排在跳躍表的位置i2k處，i0。這樣就可以在時間O(logn)內完成集合成員的搜索運算。在一個完全跳躍表中，最高級的結點是logn級結點。完全跳躍表與完全二叉搜索樹的情形非常類似。它雖然可以有效地支持成員搜索運算，但不適應于集合動態(tài)變化的情況。集合元素的插入和刪除

9、運算會破壞完全跳躍表原有的平衡狀態(tài)，影響后繼元素搜索的效率。為了在動態(tài)變化中維持跳躍表中附加指針的平衡性，必須使跳躍表中k級結點數維持在總結點數的一定比例范圍內。注意到在一個完全跳躍表中，50%的指針是0級指針；25%的指針是1級指針；(100/2k+1)%的指針是k級指針。因此，在插入一個元素時，以概率1/2引入一個0級結點，以概率1/4引入一個1級結點，以概率1/2k+1引入一個k級結點。另一方面，一個i級結點指向下一個同級或更高級的結點，它所跳過的結點數不再準確地維持在2i-1。經過這樣的修改，就可以在插入或刪除一個元素時，通過對跳躍表的局部修改來維持其平衡性。 注意到，在一個完全跳躍表

10、中，具有i級指針的結點中有一半同時具有i+1級指針。為了維持跳躍表的平衡性，可以事先確定一個實數0p1，并要求在跳躍表中維持在具有i級指針的結點中同時具有i+1級指針的結點所占比例約為p。為此目的，在插入一個新結點時，先將其結點級別初始化為0，然后用隨機數生成器反復地產生一個0，1間的隨機實數q。如果q0。設t(x)是算法obstinate找到具體實例x的一個解所需的平均時間 ,s(x)和e(x)分別是算法對于具體實例x求解成功或求解失敗所需的平均時間，則有：解此方程可得： )()()(1 ()()()(xtxexpxsxpxt)()()(1)()(xexpxpxsxt對于n后問題的任何一個解

11、而言，每一個皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機放置的。由此容易想到下面的拉斯維加斯算法。 在棋盤上相繼的各行中隨機地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至n個皇后均已相容地放置好，或已沒有下一個皇后的可放置位置時為止。如果將上述隨機放置策略與回溯法相結合，可能會獲得更好的效果。可以先在棋盤的若干行中隨機地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個解或宣告失敗。隨機放置的皇后越多，后繼回溯搜索所需的時間就越少，但失敗的概率也就越大。 如果將上述隨機放置策略與回溯法相結合，可能會獲得更好的效果。可以先在棋盤的若干行中隨機地放置皇后，然后在后繼行

12、中用回溯法繼續(xù)放置，直至找到一個解或宣告失敗。隨機放置的皇后越多，后繼回溯搜索所需的時間就越少，但失敗的概率也就越大。 設n1是一個整數。關于整數n的因子分解問題是找出n的如下形式的唯一分解式：其中，p1p2pk是k個素數，m1,m2,mk是k個正整數。如果n是一個合數，則n必有一個非平凡因子x，1xn，使得x可以整除n。給定一個合數n，求n的一個非平凡因子的問題稱為整數n的因子分割問題。kmkmmpppn2121int Split(int n) int m = floor(sqrt(double(n); for (int i=2; i=m; i+) if (n%i=0) return i;

13、return 1;事實上，算法split(n)是對范圍在1x的所有整數進行了試除而得到范圍在1x2的任一整數的因子分割。 在開始時選取0n-1范圍內的隨機數，然后遞歸地由產生無窮序列對于i=2k，以及2k1) & (dn) coutdendl; if (i=k) y=x; k*=2; 對Pollard算法更深入的分析可知，執(zhí)行算法的while循環(huán)約 次后，Pollard算法會輸出n的一個因子p。由于n的最小素因子p ，故Pollard算法可在O(n1/4)時間內找到n的一個素因子。np在實際應用中常會遇到一些問題，不論采用確定性算法或概率算法都無法保證每次都能得到正確的解答。蒙特卡羅算法則在一

14、般情況下可以保證對問題的所有實例都以高概率給出正確解，但是通常無法判定一個具體解是否正確。設p是一個實數，且1/2pn/2時，稱元素x是數組T的主元素。 templatebool Majority(Type *T, int n)/ 判定主元素的蒙特卡羅算法 int i=rnd.Random(n)+1; Type x=Ti; / 隨機選擇數組元素 int k=0; for (int j=1;jn/2); / kn/2 時T含有主元素templatebool MajorityMC(Type *T, int n, double e)/ 重復調用算法Majority int k=ceil(log(1/

15、e)/log(2); for (int i=1;i0，算法majorityMC重復調用log(1/) 次算法majority。它是一個偏真蒙特卡羅算法，且其錯誤概率小于。算法majorityMC所需的計算時間顯然是O(nlog(1/ )。：對于給定的正整數n，判定n是一個素數的充要條件是(n-1)! -1(mod n)。：如果p是一個素數，且0ap，則ap-1(mod p)。 ：如果p是一個素數，且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)/ 計算mod n，并實施對n的二次探測 unsigned int x; if (p=0) result=1; else power(a,p/2,n,x,composite); / 遞歸計算 result=(x*x)%n; / 二次探測 if (result=1)&(x!=1)&(x!=n-1) composite=true; if (p%2)=1) / p是奇數 result=(result*a)%n; bool Prime(unsigned int n)/ 素數測試的蒙特