1、隨機生成數算法第七章 概率算法學習要點 理解產生偽隨機數的算法 掌握數值概率算法的設計思想 掌握蒙特卡羅算法的設計思想 掌握拉斯維加斯算法的設計思想 掌握舍伍德算法的設計思想引言 前面幾張所討論的分治、動態規劃、貪心法、回溯和分支限界等算法的每一計算步驟都是確定的，本章所討論的概率算法允許執行過程中隨機選擇下一計算步驟。 在多數情況下，當算法在執行過程中面臨一個選擇是，隨機性選擇常比最優選擇省時，因此概率算法可在很大程度上降低算法復雜性。 概率算法的一個基本特征是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不同的效果(所需時間或計算結果)。 本章將要介紹的概率算法包括： 數值概率算

2、法 求解數值問題的近似解，精度隨計算時間增加而不斷提高 舍伍德算法 消除算法最壞情形行為與特定勢力之間的關聯性，并不提高平均性能，也不是刻意避免算法的最壞情況行為 拉斯維加斯算法 求解問題的正確解，但可能找不到解 蒙特卡羅算法 求解問題的準確解，但這個解未必正確，且一般情況下無法有效判定正確性7.1 隨機數 隨機數在概率算法設計中扮演著十分重要的角色。在現實計算機上無法產生真正的隨機數，因此在概率算法中使用的隨機數都是一定程度上隨機的，即偽隨機數。 線性同余法是產生偽隨機數的最常用的方法。由線性同余法產生的隨機序列a0, a1, , an滿足 其中b0，c0，dm。d稱為該隨機序列的種子。如何

3、選取該方法中的常數b、c和m直接關系到所產生的隨機序列的隨機性能。這是隨機性理論研究的內容，已超出本書討論的范圍。從直觀上看，m應取得充分大，因此可取m為機器大數，另外應取gcd(m,b)=1，因此可取b為一素數。, 2 , 1mod)(10nmcbaadann7.2 數值概率算法一、用隨機投點法計算值二、計算定積分三、解非線性方程組一、用隨機投點法計算值 設有一半徑為r的圓及其外切四邊形。向該正方形隨機地投擲n個點。設落入圓內的點數為k。由于所投入的點在正方形上均勻分布，因而所投入的點落入圓內的概率為。所以當n足夠大double Darts(int n) / 用隨機投點法計算值static

4、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+;return 4*k/double(n);4422rrnk4二、計算定積分設f(x)是0，1上的連續函數，且0f(x) 1。需要計算的積分為 , 積分I等于圖中的面積G。在圖所示單位正方形內均勻地作投點試驗，則隨機點落在曲線下面的概率為假設向單位正方形內隨機地投入 n個點(xi,yi)。如果有m個點落入G內，則隨機點落入G內的概率10)(dxxfI 10)(010)(

5、)(xfrdxxfdydxxfyPnmI三、解非線性方程組 求解下面的非線性方程組 其中，x1, x2, , xn是實變量，fi是未知量x1,x2,xn的非線性實函數。要求確定上述方程組在指定求根范圍內的一組解x1*, x2*, , xn* 。 在指定求根區域D內，選定一個隨機點x0作為隨機搜索的出發點。在算法的搜索過程中，假設第j步隨機搜索得到的隨機搜索點為xj。在第j+1步，計算出下一步的隨機搜索增量xj。從當前點xj依xj得到第j+1步的隨機搜索點。當x時，取為所求非線性方程組的近似解。否則進行下一步新的隨機搜索過程。0),(0),(0),(21212211nnnnxxxfxxxfxxx

6、f7.3 舍伍德(Sherwood)算法設A是一個確定性算法，當它的輸入實例為x時所需的計算時間記為tA(x)。設Xn是算法A的輸入規模為n的實例的全體，則當問題的輸入規模為n時，算法A所需的平均時間為這顯然不能排除存在xXn使得的可能性。希望獲得一個概率算法B，使得對問題的輸入規模為n的每一個實例均有這就是舍伍德算法設計的基本思想。當s(n)與tA(n)相比可忽略時，舍伍德算法可獲得很好的平均性能。nXxnAAXxtnt| / )()()()(ntxtAA)()()(nsntxtAB一、線性時間選擇算法 快速排序算法、線性時間選擇算法 P206 有時也會遇到這樣的情況，即所給的確定性算法無法

7、直接改造成舍伍德型算法。此時可借助于隨機預處理技術，不改變原有的確定性算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德算法的效果。例如，對于確定性選擇算法，可以用下面的洗牌算法Shuffle將數組a中元素隨機排列，然后用確定性選擇算法求解。這樣做所收到的效果與舍伍德型算法的效果是一樣的。 templatevoid Shuffle(Type a, int n)/ 隨機洗牌算法static RandomNumber rnd;for (int i=0;in;i+) int j=rnd.Random(n-i)+i;Swap(ai, aj);二、搜索有序表有序字典是表示有序集很有用的抽象數據類型，它支持對

8、有序集的搜索、插入、刪除、前驅、后繼等運算；有許多基本數據結構可用于實現有序字典。下面討論用數組表示有序集。P208三、跳躍表 舍伍德型算法的設計思想還可用于設計高效的數據結構。 如果用有序鏈表來表示一個含有n個元素的有序集S，則在最壞情況下，搜索S中一個元素需要(n)計算時間。 提高有序鏈表效率的一個技巧是在有序鏈表的部分結點處增設附加指針以提高其搜索性能。在增設附加指針的有序鏈表中搜索一個元素時，可借助于附加指針跳過鏈表中若干結點，加快搜索速度。這種增加了向前附加指針的有序鏈表稱為跳躍表。 應在跳躍表的哪些結點增加附加指針以及在該結點處應增加多少指針完全采用隨機化方法來確定。這使得跳躍表可

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

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

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

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

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

14、2121Pollard算法 在開始時選取0n-1范圍內的隨機數，然后遞歸地由xi=(xi-12-1)mod n產生無窮序列x1, x2, , xk, 對于i=2k，以及2k1) & (dn) coutdendl;if (i=k) y=x; k*=2;7.5 蒙特卡羅(Monte Carlo)算法 在實際應用中常會遇到一些問題，不論采用確定性算法或概率算法都無法保證每次都能得到正確的解答。蒙特卡羅算法則在一般情況下可以保證對問題的所有實例都以高概率給出正確解，但是通常無法判定一個具體解是否正確。 設p是一個實數，且1/2pn/2時，稱元素x是數組T的主元素。 對于任何給定的0，Major

15、ityMC算法重復調用log(1/)次算法Majority。它是一個偏真蒙特卡羅算法，且其錯誤概率小于。MajorityMC算法所需的計算時間顯然是O(nlog(1/)。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)/ 重復調用算法Majorityint k=ceil(log

16、(1/e)/log(2);for (int i=1;i=k;i+)if (Majority(T,n) return true;return false;三、素數測試 Wilson定理：對于給定的正整數n，判定n是一個素數的充要條件是(n-1)! -1(mod n)。 費爾馬小定理：如果p是一個素數，且0ap，則ap-11 (mod p)。 二次探測定理：如果p是一個素數，且0 xp，則方程x21(mod p)的解為x=1，p-1。 算法prime是一個偏假3/4正確的蒙特卡羅算法。通過多次重復調用錯誤概率不超過(1/4)k。這是一個很保守的估計，實際使用的效果要好得多。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;elsepower(a,p/2,n,x,composite); / 遞歸計算result=(x*x)%n; / 二次探測if (result=1)&(x!=1)&(x!=n-1)