第7章概率算法

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

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

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

4、d long n);/產(chǎn)生0：1)之間的隨機(jī)實(shí)數(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之間的隨機(jī)整數(shù)unsigned short RandomNumber:Random(unsigned long n)randSeed = multiplier*randSeed+adder;return (unsigned short)(randSeed16)%n);Random每次計(jì)算時(shí)，用線性同余計(jì)算新的種子

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

6、所投入的點(diǎn)在正方形上均勻分布，因而所投入的點(diǎn)落入圓內(nèi)的概率為 。所以當(dāng)n足夠大時(shí)，k與n之比就逼近這一概率。從而 。4422rrnk413例：用隨機(jī)投點(diǎn)法計(jì)算值#include #include #include double random(double start, double end)return start+(end-start)*rand()/(RAND_MAX+1.0);14例：用隨機(jī)投點(diǎn)法計(jì)算值double pi(int n) / 用隨機(jī)投點(diǎn)法計(jì)算 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例：用隨機(jī)投點(diǎn)法計(jì)算值void main()int n=0;srand( (unsigned)time( NULL ) );coutPlease intput the number:n;coutpi is pi(n)n;16舍伍德(Sherwood)算法設(shè)A是一個(gè)確定性算法，當(dāng)它的輸入實(shí)例為x時(shí)所需的計(jì)算時(shí)間記為tA(x)。設(shè)Xn是算法A的輸入規(guī)模為n的實(shí)例的全體，則當(dāng)問(wèn)題的輸入規(guī)模為n時(shí)，算法A所需的平均時(shí)間為這顯然不能排除存在xXn使得 的可能性。nXxnAAXxtnt| / )()(希

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

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

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

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

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

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

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