第7章概率算法

1、1第7章 概率算法2概述o概率算法允許算法在執(zhí)行過程中隨機地選擇下一個計算步驟。o概率算法的一個基本特征是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不同的效果。o概率算法分為四類：數(shù)值概率算法、蒙特卡羅算法、拉斯維加斯(Las Vegas)算法和舍伍德(Sherwood)算法。 3o數(shù)值概率算法數(shù)值概率算法常用于求解數(shù)值問題的近似解。近似解的精度隨著計算時間的增加而不斷提高。o蒙特卡羅方法蒙特卡羅方法用于求解問題的準確解，但這個解未必是正確的。算法所用的時間越多，得到正確解的概率就越高。4o拉斯維加斯算法拉斯維加斯算法不會得到不正確的解，但有時會找不到解。拉斯維加斯算法找到正確解

2、的概率隨著它所用的計算時間的增加而提高。o舍伍德算法舍伍德算法總能求得問題的一個解，且所求得的解總是正確的。5隨機數(shù) 隨機數(shù)在概率算法設(shè)計中扮演著十分重要的角色。 在現(xiàn)實計算機上無法產(chǎn)生真正的隨機數(shù)，因此在概率算法中使用的隨機數(shù)都是一定程度上隨機的，即偽隨機數(shù)。6線性同余法是產(chǎn)生偽隨機數(shù)的最常用的方法。由線性同余法產(chǎn)生的隨機序列a0,a1,an滿足, 2 , 1mod)(10nmcbaadann其中b0，c0，dm。d稱為該隨機序列的種子。如何選取該方法中的常數(shù)b、c和m直接關(guān)系到所產(chǎn)生的隨機序列的隨機性能。從直觀上看，m應(yīng)取得充分大，因此可取m為大數(shù)65536，另外應(yīng)取gcd(m,b)=1，

3、因此可取b為一素數(shù)。7例：隨機數(shù)類RandomNumberconst unsigned long maxshort=65536L;const unsigned long multiplier=1194211693L;const unsigned long adder=12345L;class RandomNumberprivate:unsigned long randSeed; /當前種子public:/構(gòu)造函數(shù)，缺省值0表示由系統(tǒng)自動產(chǎn)生種子RandomNumber(unsigned long s=0);/產(chǎn)生0：n-1之間的隨機整數(shù)unsigned short Random(unsigne

4、d long n);/產(chǎn)生0：1)之間的隨機實數(shù)double fRandom(void);8/產(chǎn)生種子RandomNumber:RandomNumber(unsigned long s);if (s=0)randSeed=time(0);elserandSeed=s;9/產(chǎn)生0：n-1之間的隨機整數(shù)unsigned short RandomNumber:Random(unsigned long n)randSeed = multiplier*randSeed+adder;return (unsigned short)(randSeed16)%n);Random每次計算時，用線性同余計算新的種子

5、ranSeed。然后將randSeed右移16位得到一個0-65535之間的隨機整數(shù)，然后再將此整數(shù)映射到0(n-1)范圍內(nèi)。10/產(chǎn)生0：1)之間的隨機實數(shù)double RandomNumber: fRandom(void)return Random(maxshort)/double(maxshort);首先用函數(shù)Random(maxshort)產(chǎn)生一個0-(maxshort-1)之間的整型隨機序列，將每個整型隨機數(shù)除以maxshort，得到0,1)區(qū)間的隨機數(shù)。11數(shù)值概率算法12例：用隨機投點法計算值設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨機地投擲n個點。設(shè)落入圓內(nèi)的點數(shù)為k。由于

6、所投入的點在正方形上均勻分布，因而所投入的點落入圓內(nèi)的概率為 。所以當n足夠大時，k與n之比就逼近這一概率。從而 。4422rrnk413例：用隨機投點法計算值#include #include #include double random(double start, double end)return start+(end-start)*rand()/(RAND_MAX+1.0);14例：用隨機投點法計算值double pi(int n) / 用隨機投點法計算 int k=0; for (int i=1;i =n;i+) double x=random(0,1); double y=rand

7、om(0,1); if (x*x+y*y)=1) k+; return 4*k/(double)n;15例：用隨機投點法計算值void main()int n=0;srand( (unsigned)time( NULL ) );coutPlease intput the number:n;coutpi is pi(n)n;16舍伍德(Sherwood)算法設(shè)A是一個確定性算法，當它的輸入實例為x時所需的計算時間記為tA(x)。設(shè)Xn是算法A的輸入規(guī)模為n的實例的全體，則當問題的輸入規(guī)模為n時，算法A所需的平均時間為這顯然不能排除存在xXn使得 的可能性。nXxnAAXxtnt| / )()(希

8、望獲得一個概率算法B，使得對問題的輸入規(guī)模為n的每一個實例均有這就是舍伍德算法設(shè)計的基本思想。當s(n)與tA(n)相比可忽略時，舍伍德算法可獲得很好的平均性能。)()(ntxtAA)()()(nsntxtAB17舍伍德(Sherwood)算法有時也會遇到這樣的情況，即所給的確定性算法無法直接改造成舍伍德型算法。此時可借助于隨機預(yù)處理技術(shù)，不改變原有的確定性算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德算法的效果。舍伍德算法的優(yōu)點是其計算時間復(fù)雜性對所有實例而言相對均勻。18快速排序算法19舍伍德(Sherwood)算法對于確定性選擇算法，可以用下面的洗牌算法shuffle將數(shù)組a中元素隨機排

9、列，然后用確定性選擇算法求解。這樣做所收到的效果與舍伍德型算法的效果是一樣的。public static void shuffle(Comparable a, int n) / 隨機洗牌算法 rnd = new Random(); for (int i=1;i0。 設(shè)t(x)是算法obstinate找到具體實例x的一個解所需的平均時間 ,s(x)和e(x)分別是算法對于具體實例x求解成功或求解失敗所需的平均時間，則有：解此方程可得： )()()(1 ()()()(xtxexpxsxpxt)()()(1)()(xexpxpxsxt22例：n后問題對于n后問題的任何一個解而言，每一個皇后在棋盤上的

10、位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機放置的。由此容易想到下面的拉斯維加斯算法。 在棋盤上相繼的各行中隨機地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至n個皇后均已相容地放置好，或已沒有下一個皇后的可放置位置時為止。23 如果將上述隨機放置策略與回溯法相結(jié)合，可能會獲得更好的效果。 可以先在棋盤的若干行中隨機地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個解或宣告失敗。隨機放置的皇后越多，后繼回溯搜索所需的時間就越少，但失敗的概率也就越大。24p: 算法成功的概率 s: 一次成功搜索訪問的節(jié)點數(shù)平均值e: 一次不成功搜索訪問的節(jié)點數(shù)平均值t: 反復(fù)調(diào)用算法最終找到一個

11、解索訪問的節(jié)點平均值 t=s+(1-p)e/pstopVegaspset01.0000262.00-262.0050.503933.8847.2380.39120.046513.0010.20222.1125蒙特卡羅(Monte Carlo)算法在實際應(yīng)用中常會遇到一些問題，不論采用確定性算法或概率算法都無法保證每次都能得到正確的解答。蒙特卡羅算法則在一般情況下可以保證對問題的所有實例都以高概率給出正確解，但是通常無法判定一個具體解是否正確。26蒙特卡羅(Monte Carlo)算法設(shè)p是一個實數(shù)，且1/2p1。如果一個蒙特卡羅算法對于問題的任一實例得到正確解的概率不小于p，則稱該蒙特卡羅算法

12、是p正確的，且稱p-1/2是該算法的優(yōu)勢。如果對于同一實例，蒙特卡羅算法不會給出2個不同的正確解答，則稱該蒙特卡羅算法是一致的。對于一個一致的p正確蒙特卡羅算法，要提高獲得正確解的概率，只要執(zhí)行該算法若干次，并選擇出現(xiàn)頻次最高的解即可。27例：素數(shù)測試Wilson定理定理：對于給定的正整數(shù)n，判定n是一個素數(shù)的充要條件是(n-1)! -1(mod n)。缺點：計算量太大，無法實現(xiàn)對較大素數(shù)的測試。28例：素數(shù)測試費爾馬小定理費爾馬小定理：如果p是一個素數(shù)，且0ap，則ap-1(mod p)=1。例：67是素數(shù)，266mod 67=1。缺點：費爾馬小定理只是素數(shù)判定的一個必要條件。滿足費爾馬小定

13、理條件的整數(shù)n未必全是素數(shù)。例：561。29例：素數(shù)測試 二次探測定理二次探測定理：如果p是一個素數(shù)，且0 xp，則方程x21(mod p)的解為x=1，p-1。x21(mod p) 等價于x2-10(mod p)，于是(x+1)(x-1) 0(mod p)。故p必整除x-1或x+1。由p是素數(shù)且0 xp，于是x=1或x=p-1。利用二次探測定理，可以在利用費爾馬小定理計算an-1mod n的過程中增加對整數(shù)n的二次探測。一旦發(fā)現(xiàn)違背二次探測條件，即可得出n不是素數(shù)的結(jié)論。30例：素數(shù)測試private static int power(int a, int p, int n) / 計算 ap

14、 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 prime(int n) / 素數(shù)測試的蒙特卡羅算法 rnd = new Random(); int a, result; composite=false; a=rnd.random(n-3)+2; /費爾馬小定理ap-1(mod p)=1 result=power(a,n-1,n); if (composite|(result!=1) return false; else return true;31例：素數(shù)測試算法prime是一個偏假3/4正確的蒙特卡羅算法。通過多次重復(fù)調(diào)用錯誤概率不超過(1/4)k。這是一個很保守的估計，實際使用的效果