1、第第7章概率算法章概率算法2 數(shù)值隨機化算法 常用于數(shù)值問題的求解，所得到的往往是近似解，且近似解的精度隨著計算時間的增加而不斷提高。 舍伍德算法 當一個確定算法的最壞情況計算復雜性與平均情況計算復雜性相差加大時，引入隨機性將其改造為伍舍德算法，消除或減少好壞實例的差異。所求的解總是正確的。3 拉斯維加斯算法 用拉斯維加斯算法求解一個問題，一旦找到一個解，則這個解一定是正確的。但是用拉斯維加斯算法有時會找不到解，其找到解的概率隨著它所用的計算時間的增加而提高。 蒙特卡羅算法 用蒙特卡羅算法求解一個問題，得到一個解，但這個解未必是正確的，其求得正確解的概率隨著算法所用時間的增加而提高。4隨機數(shù)在

2、概率算法設計中扮演著十分重要的角色。在現(xiàn)實計算機上無法產(chǎn)生真正的隨機數(shù)，因此在概率算法中使用的隨機數(shù)都是一定程度上隨機的，即偽隨機數(shù)。線性同余法是產(chǎn)生偽隨機數(shù)的最常用的方法。由線性同余法產(chǎn)生的隨機序列a0,a1,an滿足, 2 , 1mod)(10nmcbaadann其中b0，c0，dm。d稱為該隨機序列的種子。如何選取該方法中的常數(shù)b、c和m直接關系到所產(chǎn)生的隨機序列的隨機性能。這是隨機性理論研究的內(nèi)容，已超出本書討論的范圍。從直觀上看，m應取得充分大，因此可取m為機器大數(shù)，另外應取gcd(m,b)=1，因此可取b為一素數(shù)。56設有一半徑為r的圓及其外切四邊形。向該正方形隨機地投擲n個點。設

3、落入圓內(nèi)的點數(shù)為k。由于所投入的點在正方形上均勻分布，因而所投入的點落入圓內(nèi)的概率為 。所以當n足夠大時，k與n之比就逼近這一概率。從而 。4422rrnk4public static double darts(int n) / 用隨機投點法計算值 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; 7設f(x)是0，1上的連續(xù)函數(shù)，且0f(x)1。需要計算的積分為 ,積分I等于圖中的面積G。10)(d

4、xxfI在圖所示單位正方形內(nèi)均勻地作投點試驗，則隨機點落在曲線下面的概率為假設向單位正方形內(nèi)隨機地投入n個點(xi,yi)。如果有m個點落入G內(nèi)，則隨機點落入G內(nèi)的概率 10)(010)()(xfrdxxfdydxxfyPnmI8求解下面的非線性方程組0),(0),(0),(21212211nnnnxxxfxxxfxxxf其中，x1,x2,xn是實變量，fi是未知量x1,x2,xn的非線性實函數(shù)。要求確定上述方程組在指定求根范圍內(nèi)的一組解*2*1,nxxx 在指定求根區(qū)域D內(nèi)，選定一個隨機點x0作為隨機搜索的出發(fā)點。在算法的搜索過程中，假設第j步隨機搜索得到的隨機搜索點為xj。在第j+1步，計

5、算出下一步的隨機搜索增量xj。從當前點xj依xj得到第j+1步的隨機搜索點。當x時，取為所求非線性方程組的近似解。否則進行下一步新的隨機搜索過程。9設A是一個確定性算法，當它的輸入實例為x時所需的計算時間記為tA(x)。設Xn是算法A的輸入規(guī)模為n的實例的全體，則當問題的輸入規(guī)模為n時，算法A所需的平均時間為nXxnAAXxtnt| / )()(這顯然不能排除存在xXn使得 的可能性。希望獲得一個概率算法B，使得對問題的輸入規(guī)模為n的每一個實例均有這就是舍伍德算法設計的基本思想。當s(n)與tA(n)相比可忽略時，舍伍德算法可獲得很好的平均性能。)()(ntxtAA)()()(nsntxtAB

6、10復習學過的Sherwood算法：（1）線性時間選擇算法（2）快速排序算法有時也會遇到這樣的情況，即所給的確定性算法無法直接改造成舍伍德型算法。此時可借助于隨機預處理技術，不改變原有的確定性算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德算法的效果。例如，對于確定性選擇算法，可以用下面的洗牌算法shuffle將數(shù)組a中元素隨機排列，然后用確定性選擇算法求解。這樣做所收到的效果與舍伍德型算法的效果是一樣的。public static void shuffle(Comparable a, int n) / 隨機洗牌算法 rnd = new Random(); for (int i=1;in;i+)

7、 int j=rnd.random(n-i+1)+i; MyMath.swap(a, i, j); 11舍伍德型算法的設計思想還可用于設計高效的數(shù)據(jù)結構。如果用有序鏈表來表示一個含有n個元素的有序集S，則在最壞情況下，搜索S中一個元素需要(n)計算時間。提高有序鏈表效率的一個技巧是在有序鏈表的部分結點處增設附加指針以提高其搜索性能。在增設附加指針的有序鏈表中搜索一個元素時，可借助于附加指針跳過鏈表中若干結點，加快搜索速度。這種增加了向前附加指針的有序鏈表稱為跳躍表。應在跳躍表的哪些結點增加附加指針以及在該結點處應增加多少指針完全采用隨機化方法來確定。這使得跳躍表可在O(logn)平均時間內(nèi)支持

8、關于有序集的搜索、插入和刪除等運算。 12在一般情況下，給定一個含有n個元素的有序鏈表，可以將它改造成一個完全跳躍表，使得每一個k級結點含有k+1個指針，分別跳過2k-1，2k-1-1，20-1個中間結點。第i個k級結點安排在跳躍表的位置i2k處，i0。這樣就可以在時間O(logn)內(nèi)完成集合成員的搜索運算。在一個完全跳躍表中，最高級的結點是logn級結點。完全跳躍表與完全二叉搜索樹的情形非常類似。它雖然可以有效地支持成員搜索運算，但不適應于集合動態(tài)變化的情況。集合元素的插入和刪除運算會破壞完全跳躍表原有的平衡狀態(tài)，影響后繼元素搜索的效率。13為了在動態(tài)變化中維持跳躍表中附加指針的平衡性，必須

9、使跳躍表中k級結點數(shù)維持在總結點數(shù)的一定比例范圍內(nèi)。注意到在一個完全跳躍表中，50%的指針是0級指針；25%的指針是1級指針；(100/2k+1)%的指針是k級指針。因此，在插入一個元素時，以概率1/2引入一個0級結點，以概率1/4引入一個1級結點，以概率1/2k+1引入一個k級結點。另一方面，一個i級結點指向下一個同級或更高級的結點，它所跳過的結點數(shù)不再準確地維持在2i-1。經(jīng)過這樣的修改，就可以在插入或刪除一個元素時，通過對跳躍表的局部修改來維持其平衡性。 14注意到，在一個完全跳躍表中，具有i級指針的結點中有一半同時具有i+1級指針。為了維持跳躍表的平衡性，可以事先確定一個實數(shù)0p1，并

10、要求在跳躍表中維持在具有i級指針的結點中同時具有i+1級指針的結點所占比例約為p。為此目的，在插入一個新結點時，先將其結點級別初始化為0，然后用隨機數(shù)生成器反復地產(chǎn)生一個0，1間的隨機實數(shù)q。如果q0。設t(x)是算法obstinate找到具體實例x的一個解所需的平均時間 ,s(x)和e(x)分別是算法對于具體實例x求解成功或求解失敗所需的平均時間，則有：解此方程可得： )()()(1 ()()()(xtxexpxsxpxt)()()(1)()(xexpxpxsxt16對于n后問題的任何一個解而言，每一個皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機放置的。由此容易想到下面的拉斯維加

11、斯算法。 在棋盤上相繼的各行中隨機地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至n個皇后均已相容地放置好，或已沒有下一個皇后的可放置位置時為止。如果將上述隨機放置策略與回溯法相結合，可能會獲得更好的效果。可以先在棋盤的若干行中隨機地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個解或宣告失敗。隨機放置的皇后越多，后繼回溯搜索所需的時間就越少，但失敗的概率也就越大。 stopVegaspset01.0000262.00-262.0050.503933.8847.2380.39120.046513.0010.20222.1117設n1是一個整數(shù)。關于整數(shù)n的因子分解問題是找出n

12、的如下形式的惟一分解式：其中，p1p2pk是k個素數(shù)，m1,m2,mk是k個正整數(shù)。如果n是一個合數(shù)，則n必有一個非平凡因子x，1xn，使得x可以整除n。給定一個合數(shù)n，求n的一個非平凡因子的問題稱為整數(shù)n的因子分割問題。kmkmmpppn2121private static int split(int n) int m = (int) Math.floor(Math.sqrt(double)n); for (int i=2; i=m; i+) if (n%i=0) return i; return 1; 事實上，算法split(n)是對范圍在1x的所有整數(shù)進行了試除而得到范圍在1x2的任一整

13、數(shù)的因子分割。 18在開始時選取0n-1范圍內(nèi)的隨機數(shù)，然后遞歸地由產(chǎn)生無窮序列對于i=2k，以及2k1) & (dn) System.out.println(d); if (i=k) y=x; k*=2; 對Pollard算法更深入的分析可知，執(zhí)行算法的while循環(huán)約 次后，Pollard算法會輸出n的一個因子p。由于n的最小素因子p ，故Pollard算法可在O(n1/4)時間內(nèi)找到n的一個素因子。np19在實際應用中常會遇到一些問題，不論采用確定性算法或概率算法都無法保證每次都能得到正確的解答。蒙特卡羅算法則在一般情況下可以保證對問題的所有實例都以高概率給出正確解，但是通常無法

14、判定一個具體解是否正確。設p是一個實數(shù)，且1/2pn/2時，稱元素x是數(shù)組T的主元素。 public static boolean majority(intt, int n) / 判定主元素的蒙特卡羅算法 rnd = new Random(); int i=rnd.random(n)+1; int x=ti; / 隨機選擇數(shù)組元素 int k=0; for (int j=1;jn/2); / kn/2 時t含有主元素 public static boolean majorityMC(intt, int n, double e) / 重復log(1/)次調(diào)用算法majority int k= (

15、int) Math.ceil(Math.log(1/e)/Math.log(2); for (int i=1;i0，算法majorityMC重復調(diào)用log(1/) 次算法majority。它是一個偏真蒙特卡羅算法，且其錯誤概率小于。算法majorityMC所需的計算時間顯然是O(nlog(1/ )。21：對于給定的正整數(shù)n，判定n是一個素數(shù)的充要條件是(n-1)! -1(mod n)。：如果p是一個素數(shù)，且0ap，則ap-1(mod p)。 ：如果p是一個素數(shù)，且0 xp，則方程x21(mod p)的解為x=1，p-1。private static int power(int a, int p, int n) / 計算 ap mod n，并實施對n的二次探測 int x, result; if (p=0) result=1; else x=power(a,p/2,n); / 遞歸計算 result=(x*x)%n; / 二次探測 if (result=1)&(x!=1)&(x!=n-1) composite=true; if (p%2)=1) / p是奇數(shù) result=(result*a)%n; return result;public static boolean