隨機(jī)生成數(shù)算法

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

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

3、選取該方法中的常數(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ù)。, 2 , 1mod)(10nmcbaadann7.2 數(shù)值概率算法一、用隨機(jī)投點(diǎn)法計(jì)算值二、計(jì)算定積分三、解非線性方程組一、用隨機(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足夠大double Darts(int n) / 用隨機(jī)投點(diǎn)法計(jì)算值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二、計(jì)算定積分設(shè)f(x)是0，1上的連續(xù)函數(shù)，且0f(x) 1。需要計(jì)算的積分為 , 積分I等于圖中的面積G。在圖所示單位正方形內(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)(dxxfI 10)(010)(

5、)(xfrdxxfdydxxfyPnmI三、解非線性方程組 求解下面的非線性方程組 其中，x1, x2, , xn是實(shí)變量，fi是未知量x1,x2,xn的非線性實(shí)函數(shù)。要求確定上述方程組在指定求根范圍內(nèi)的一組解x1*, x2*, , xn* 。 在指定求根區(qū)域D內(nèi)，選定一個(gè)隨機(jī)點(diǎn)x0作為隨機(jī)搜索的出發(fā)點(diǎn)。在算法的搜索過程中，假設(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ī)搜索過程。0),(0),(0),(21212211nnnnxxxfxxxfxxx

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

7、直接改造成舍伍德型算法。此時(shí)可借助于隨機(jī)預(yù)處理技術(shù)，不改變原有的確定性算法，僅對(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;Swap(ai, aj);二、搜索有序表有序字典是表示有序集很有用的抽象數(shù)據(jù)類型，它支持對(duì)

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

9、在O(logn)平均時(shí)間內(nèi)支持關(guān)于有序集的搜索、插入和刪除等運(yùn)算。 在一般情況下，給定一個(gè)含有n個(gè)元素的有序鏈表，可以將它改造成一個(gè)完全跳躍表，使得每一個(gè)k級(jí)結(jié)點(diǎn)含有k+1個(gè)指針，分別跳過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)。 完全跳躍表與完全二叉搜索樹的情形非常類似。它雖然可以有效地支持成員搜索運(yùn)算，但不適應(yīng)于集合動(dòng)態(tài)變化的情況。集合元素的插入和刪除運(yùn)算會(huì)破壞完全跳躍表原有的平衡狀態(tài)，影響后繼元素搜索的效率。 為了在動(dòng)態(tài)變化中維持

10、跳躍表中附加指針的平衡性，必須使跳躍表中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)，它所跳過的結(jié)點(diǎn)數(shù)不再準(zhǔn)確地維持在2i-1。經(jīng)過這樣的修改，就可以在插入或刪除一個(gè)元素時(shí)，通過對(duì)跳躍表的局部修改來維持其平衡性。 注意到，在一個(gè)完全跳躍表中，具有i級(jí)指針的結(jié)點(diǎn)中有一半同時(shí)具有i+1級(jí)指針。為了維持跳躍表的平衡性，可以

11、事先確定一個(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一、n后問題 對(duì)于n后問題的任何一個(gè)解而言，每一個(gè)皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是

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

13、 設(shè)n1是一個(gè)整數(shù)。關(guān)于整數(shù)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è)非平凡因子的問題稱為整數(shù)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; 事實(shí)上，算法split(n)是對(duì)范圍在1x的所有整數(shù)進(jìn)行了試除而得到范圍在1x2的任一整數(shù)的因子分割。kmkmmpppn

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

15、ityMC算法重復(fù)調(diào)用log(1/)次算法Majority。它是一個(gè)偏真蒙特卡羅算法，且其錯(cuò)誤概率小于。MajorityMC算法所需的計(jì)算時(shí)間顯然是O(nlog(1/)。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, double e)/ 重復(fù)調(diào)用算法Majorityint k=ceil(log

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