算法設計 概率算法

1、1,第7章 概率算法,2,學習要點 理解產生偽隨機數的算法 掌握數值概率算法的設計思想 掌握蒙特卡羅算法的設計思想 掌握拉斯維加斯算法的設計思想 掌握舍伍德算法的設計思想,3,隨機數,隨機數在概率算法設計中扮演著十分重要的角色。在現實計算機上無法產生真正的隨機數，因此在概率算法中使用的隨機數都是一定程度上隨機的，即偽隨機數。 線性同余法是產生偽隨機數的最常用的方法。由線性同余法產生的隨機序列a0,a1,an滿足,其中b0，c0，dm。d稱為該隨機序列的種子。如何選取該方法中的常數b、c和m直接關系到所產生的隨機序列的隨機性能。這是隨機性理論研究的內容，從直觀上看，m應取得充分大，因此可取m為機

2、器大數，另外應取gcd(m,b)=1，因此可取b為一素數。,4,數值概率算法,5,用隨機投點法計算值,設有一半徑為r的圓及其外切四邊形。向該正方形隨機地投擲n個點。設落入圓內的點數為k。由于所投入的點在正方形上均勻分布，因而所投入的點落入圓內的概率為 。所以當n足夠大 時，k與n之比就逼近這一概率。從而,double 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*x+

3、y*y)=1) k+; return 4*k/double(n); ,6,計算定積分,設f(x)是0，1上的連續(xù)函數，且0f(x)1。 需要計算的積分為 ,積分I等于圖中的面積G。,在圖所示單位正方形內均勻地作投點試驗，則隨機點落在曲線下面的概率為 假設向單位正方形內隨機地投入n個點(xi,yi)。如果有m個點落入 G內，則隨機點落入G內的概率,7,解非線性方程組,求解下面的非線性方程組,其中，x1,x2,xn是實變量，fi是未知量x1,x2,xn的非線性實函數。要求確定上述方程組在指定求根范圍內的一組解,在指定求根區(qū)域D內，選定一個隨機點x0作為隨機搜索的出發(fā)點。在算法的搜索過程中，假設第j

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

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

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

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

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

9、。為了維持跳躍表的平衡性，可以事先確定一個實數0p1，并要求在跳躍表中維持在具有i級指針的結點中同時具有i+1級指針的結點所占比例約為p。為此目的，在插入一個新結點時，先將其結點級別初始化為0，然后用隨機數生成器反復地產生一個0，1間的隨機實數q。如果qp，則使新結點級別增加1，直至qp。由此產生新結點級別的過程可知，所產生的新結點的級別為0的概率為1-p，級別為1的概率為p(1-p)，級別為i的概率為pi(1-p)。如此產生的新結點的級別有可能是一個很大的數，甚至遠遠超過表中元素的個數。為了避免這種情況，用 作為新結點級別的上界。其中n是當前跳躍表中結點個數。當前跳躍表中任一結點的級別不超過

10、,14,拉斯維加斯( Las Vegas )算法,拉斯維加斯算法的一個顯著特征是它所作的隨機性決策有可能導致算法找不到所需的解。,void obstinate(Object x, Object y) / 反復調用拉斯維加斯算法LV(x,y)，直到找到問題的一個解y bool success= false; while (!success) success=lv(x,y); ,設p(x)是對輸入x調用拉斯維加斯算法獲得問題的一個解的概率。一個正確的拉斯維加斯算法應該對所有輸入x均有p(x)0。 設t(x)是算法obstinate找到具體實例x的一個解所需的平均時間 ,s(x)和e(x)分別是算法

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

12、。,16,n后問題,如果將上述隨機放置策略與回溯法相結合，可能會獲得更好的效果?？梢韵仍谄灞P的若干行中隨機地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個解或宣告失敗。隨機放置的皇后越多，后繼回溯搜索所需的時間就越少，但失敗的概率也就越大。,17,整數因子分解,設n1是一個整數。關于整數n的因子分解問題是找出n的如下形式的唯一分解式： 其中，p1p2pk是k個素數，m1,m2,mk是k個正整數。 如果n是一個合數，則n必有一個非平凡因子x，1xn，使得x可以整除n。給定一個合數n，求n的一個非平凡因子的問題稱為整數n的因子分割問題。,int Split(int n) int m = f

13、loor(sqrt(double(n); for (int i=2; i=m; i+) if (n%i=0) return i; return 1; ,事實上，算法split(n)是對范圍在1x的所有整數進行了試除而得到范圍在1x2的任一整數的因子分割。,18,Pollard算法,在開始時選取0n-1范圍內的隨機數，然后遞歸地由 產生無窮序列 對于i=2k，以及2kj2k+1，算法計算出xj-xi與n的最大公因子 d=gcd(xj-xi，n)。如果d是n的非平凡因子，則實現對n的一次分割，算法輸出n的因子d。,void Pollard(int n) / 求整數n因子分割的拉斯維加斯算法 Ran

14、domNumber rnd; int i=1; int x=rnd.Random(n); / 隨機整數 int y=x; int k=2; while (true) i+; x=(x*x-1)%n; / int d=gcd(y-x,n); / 求n的非平凡因子 if (d1) ,對Pollard算法更深入的分析可知，執(zhí)行算法的while循環(huán)約 次后，Pollard算法會輸出n的一個因子p。由于n的最小素因子p ，故Pollard算法可在O(n1/4)時間內找到n的一個素因子。,19,蒙特卡羅(Monte Carlo)算法,在實際應用中常會遇到一些問題，不論采用確定性算法或概率算法都無法保證每次

15、都能得到正確的解答。蒙特卡羅算法則在一般情況下可以保證對問題的所有實例都以高概率給出正確解，但是通常無法判定一個具體解是否正確。 設p是一個實數，且1/2p1。如果一個蒙特卡羅算法對于問題的任一實例得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的，且稱p-1/2是該算法的優(yōu)勢。 如果對于同一實例，蒙特卡羅算法不會給出2個不同的正確解答，則稱該蒙特卡羅算法是一致的。 有些蒙特卡羅算法除了具有描述問題實例的輸入參數外，還具有描述錯誤解可接受概率的參數。這類算法的計算時間復雜性通常由問題的實例規(guī)模以及錯誤解可接受概率的函數來描述。,20,蒙特卡羅(Monte Carlo)算法,對于一個一致的p

16、正確蒙特卡羅算法，要提高獲得正確解的概率，只要執(zhí)行該算法若干次，并選擇出現頻次最高的解即可。 如果重復調用一個一致的(1/2+)正確的蒙特卡羅算法2m-1次，得到正確解的概率至少為1-，其中，,對于一個解所給問題的蒙特卡羅算法MC(x)，如果存在問題實例的子集X使得： (1)當xX時，MC(x)返回的解是正確的； (2)當xX時，正確解是y0，但MC(x)返回的解未必是y0。 稱上述算法MC(x)是偏y0的算法。,重復調用一個一致的，p正確偏y0蒙特卡羅算法k次，可得到一個O(1-(1-p)k)正確的蒙特卡羅算法，且所得算法仍是一個一致的偏y0蒙特卡羅算法。,21,主元素問題,設T1:n是一個

17、含有n個元素的數組。當|i|Ti=x|n/2時，稱元素x是數組T的主元素。,template bool 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含有主元素 ,template bool MajorityMC(Type *T, int n, double e) / 重復調用算法Majority int k=ceil(log(1/e)/log(2); for (int i=1;i=k;i+) i

18、f (Majority(T,n) return true; return false; ,對于任何給定的0，算法majorityMC重復調用log(1/) 次算法majority。它是一個偏真蒙特卡羅算法，且其錯誤概率小于。算法majorityMC所需的計算時間顯然是O(nlog(1/ )。,22,素數測試,Wilson定理：對于給定的正整數n，判定n是一個素數的充要條件是(n-1)! -1(mod n)。 費爾馬小定理：如果p是一個素數，且0ap，則ap-1(mod p)。 二次探測定理：如果p是一個素數，且0xp，則方程x21(mod p)的解為x=1，p-1。,void power( unsigned int a, unsigned int p, unsigned int n, unsigned int ,bo