算法分析與設(shè)計第7章

1、1 第7章 隨機化算法 2 學(xué)習(xí)要點學(xué)習(xí)要點 理解產(chǎn)生偽隨機數(shù)的算法 掌握數(shù)值隨機化算法的設(shè)計思想 掌握蒙特卡羅算法蒙特卡羅算法的設(shè)計思想 掌握拉斯維加斯算法拉斯維加斯算法的設(shè)計思想 掌握舍伍德算法舍伍德算法的設(shè)計思想 Sketch of Randomized algorithms nA randomized algorithm is just one that depends on random numbers for its operation nThese are randomized algorithms (important): nUsing random numbers to he

2、lp find a solution to a problem nUsing random numbers to improve a solution to a problem nThese are difficult topics: nGetting or generating “random” numbers nGenerating random data for testing (or other) purposes Advantages nOften the execution time or space requirement of a randomized algorithm is

3、 smaller than that of the best deterministic version. nAll the randomized algorithms are invariably simple to comprehend and implement. 11.1.3 隨機算法分類 隨機算法通常分成隨機算法通常分成4類：類： 數(shù)值隨機算法數(shù)值隨機算法（Numerical randomized algorithm） 蒙特卡羅算法蒙特卡羅算法（Monte Carlo） 拉斯維加斯算法（拉斯維加斯算法（Las Vegas） 舍伍德算法舍伍德算法（Sherwood） 數(shù)值隨機算法數(shù)值隨

4、機算法 用于求數(shù)值問題的用于求數(shù)值問題的近似解近似解，近似精度可隨時間，近似精度可隨時間 增加。增加。 舍伍德算法舍伍德算法（Sherwood-algorithm） 總能求得問題的正確解總能求得問題的正確解。當(dāng)一個確定性算法在最當(dāng)一個確定性算法在最 壞情況下的計算復(fù)雜度與其在平均情況下的計算復(fù)雜壞情況下的計算復(fù)雜度與其在平均情況下的計算復(fù)雜 度兩者相差較大時度兩者相差較大時，可以在這個確定算法中引入隨機，可以在這個確定算法中引入隨機 性將它改造成一個舍伍德算法，性將它改造成一個舍伍德算法，用來消除或減少問題用來消除或減少問題 的不同實例之間這種在計算時間上的差別的不同實例之間這種在計算時間上的

5、差別。舍伍德算。舍伍德算 法的精髓不是避免算法的最壞情況行為，而是設(shè)法法的精髓不是避免算法的最壞情況行為，而是設(shè)法消消 除這種最壞行為與特定實例之間的關(guān)聯(lián)性除這種最壞行為與特定實例之間的關(guān)聯(lián)性。 拉斯維加斯算法拉斯維加斯算法 求得的解總是正確的，但有時拉斯維加斯算法可能求得的解總是正確的，但有時拉斯維加斯算法可能 始終找不到解始終找不到解。使用拉斯維加斯算法求解同一問題。使用拉斯維加斯算法求解同一問題 的同一實例，能夠得到相同的結(jié)果，但算法的執(zhí)行的同一實例，能夠得到相同的結(jié)果，但算法的執(zhí)行 時間會不一樣。一般情況下，時間會不一樣。一般情況下，求得正確解的概率隨求得正確解的概率隨 計算時間的增加

6、而增大計算時間的增加而增大。因此，為了減少求解失敗。因此，為了減少求解失敗 的概率，可以使用一個拉斯維加斯算法對同一實例的概率，可以使用一個拉斯維加斯算法對同一實例 ，重復(fù)多次執(zhí)行該算法重復(fù)多次執(zhí)行該算法。 蒙特卡羅算法蒙特卡羅算法 不保證所求得的解是正確的不保證所求得的解是正確的，也就是說，蒙特，也就是說，蒙特 卡羅算法求得的解有時是錯誤的。不過，由于可以卡羅算法求得的解有時是錯誤的。不過，由于可以 設(shè)法控制這類算法得到錯誤解的概率設(shè)法控制這類算法得到錯誤解的概率，并因它的簡，并因它的簡 單高效，是很有價值的一類隨機算法。一般情況下單高效，是很有價值的一類隨機算法。一般情況下 ，蒙特卡羅算法

7、，蒙特卡羅算法求得正確解的概率隨計算時間的增求得正確解的概率隨計算時間的增 加而增大加而增大。但無論如何不能確保解的正確性，而且。但無論如何不能確保解的正確性，而且 通常無法有效地判斷所求得的解究竟是否正確，這通常無法有效地判斷所求得的解究竟是否正確，這 是蒙特卡羅算法的缺陷。是蒙特卡羅算法的缺陷。 隨機算法有時也稱隨機算法有時也稱（probabilistic algorithm），），但也有人對兩者這樣區(qū)分：但也有人對兩者這樣區(qū)分： 如果取得結(jié)果的途徑是隨機的，則稱為隨機算如果取得結(jié)果的途徑是隨機的，則稱為隨機算 法，如拉斯維加斯算法；法，如拉斯維加斯算法； 如果取得的解是否正確存在隨機性，

8、稱為概率如果取得的解是否正確存在隨機性，稱為概率 算法，如蒙特卡羅算法。算法，如蒙特卡羅算法。 本書中統(tǒng)一稱為隨機算法。本書中統(tǒng)一稱為隨機算法。 10 隨機數(shù) 隨機數(shù)在隨機化算法設(shè)計中扮演著十分重要的角色。在現(xiàn)實計算 機上無法產(chǎn)生真正的隨機數(shù)，因此在隨機化算法中使用的隨機數(shù) 都是一定程度上隨機的，即偽隨機數(shù)偽隨機數(shù)。 線性同余法是產(chǎn)生偽隨機數(shù)的最常用的方法。由線性同余法產(chǎn)生 的隨機序列a0,a1,an滿足 , 2 , 1mod)( 1 0 nmcbaa da nn 其中b0，c0，dm。d稱為該隨機序列的種子。如何選取該 方法中的常數(shù)b、c和m直接關(guān)系到所產(chǎn)生的隨機序列的隨機性 能。這是隨機性

9、理論研究的內(nèi)容，已超出本書討論的范圍。從 直觀上看，m應(yīng)取得充分大，因此可取m為機器大數(shù)，另外應(yīng) 取gcd(m,b)=1，因此可取b為一素數(shù)。 設(shè)設(shè)a=3,c=7m=127,d=2,則有則有 (13,46,18,61,63,69,87,14,49,27,88,17,) 11 數(shù)值隨機化算法 12 用隨機投點法計算值 設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨機地投擲n個 點。設(shè)落入圓內(nèi)的點數(shù)為k。由于所投入的點在正方形上均勻分 布，因而所投入的點落入圓內(nèi)的概率為 。所以當(dāng)n足夠大 時，k與n之比就逼近這一概率。從而 44 2 2 r r n k4 double Darts(int n) /

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

11、內(nèi)，則隨機點落入G內(nèi)的概率 1 0 )( 0 1 0 )()( xf r dxxfdydxxfyP n m I 14 計算定積分 設(shè)f(x)是0，1上的連續(xù)函數(shù)，且0f(x)1。 需要計算的積分為 , 積分I等于圖中的面積G。 1 0 )(dxxfI 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 (yf(x) k+; return k/double(n);

12、 15 舍伍德(Sherwood)算法 設(shè)A是一個確定性算法，當(dāng)它的輸入實例為x時所需的計算時間記 為tA(x)。設(shè)Xn是算法A的輸入規(guī)模為n的實例的全體，則當(dāng)問題的 輸入規(guī)模為n時，算法A所需的平均時間為 n Xx nA AXxtnt| / )()( 這顯然不能排除存在xXn使得 的可能性。希望 獲得一個隨機化算法B，使得對問題的輸入規(guī)模為n的每一個實 例均有 這就是舍伍德算法設(shè)計的基本思想。當(dāng)s(n)與tA(n)相比可忽略時， 舍伍德算法可獲得很好的平均性能。 )()(ntxt A A )()()(nsntxt A B ( )( )/ | n B Bn x X tntxX template

13、 int RandomizedPartition (Type a, int p, int r) int i = Random(p,r); Swap(ai, ap); return Partition (a, p, r); 快速排序算法的性能取決于劃分的對稱性劃分的對稱性。通過修改 算法partition，可以設(shè)計出采用隨機選擇策略隨機選擇策略的快速排 序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被 劃分時，可以在ap:r中隨機選出一個元素作為劃分基準(zhǔn)， 這樣可以使劃分基準(zhǔn)的選擇是隨機的，從而可以期望劃 分是較對稱的。sherwood算法 QuickSort (a,p,q-1); /對左半段排

14、序 QuickSort (a,q+1,r); /對右半段排序 RandomizedPartition(a,p,r） 給定線性序集中n個元素和一個整數(shù)k，1kn，要求找出這n個 元素中第k小的元素 template Type RandomizedSelect(Type a,int p,int r,int k) if (p=r) return ap; int i=RandomizedPartition(a,p,r), j=i-p+1; if (k=j) return RandomizedSelect(a,p,i,k); else return RandomizedSelect(a,i+1,r,k-

15、j); 在最壞情況下，算法randomizedSelect需要O(n2)計算時間 但可以證明，算法randomizedSelect可以在O(n)平均時間內(nèi) 找出n個輸入元素中的第k小元素。 19 舍伍德(Sherwood)算法 復(fù)習(xí)學(xué)過的Sherwood算法： （1）線性時間選擇算法 （2）快速排序算法 有時也會遇到這樣的情況，即所給的確定性算法無法直接改造 成舍伍德型算法。此時可借助于隨機預(yù)處理技術(shù)隨機預(yù)處理技術(shù)，不改變原有不改變原有 的確定性算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德的確定性算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德 算法的效果算法的效果。例如，對于確定性選擇算法，

16、可以用下面的洗牌 算法shuffle將數(shù)組a中元素隨機排列，然后用確定性選擇算法 求解。這樣做所收到的效果與舍伍德型算法的效果是一樣的。 template void Shuffle(Type a, int n) /隨機洗牌算法 static RandomNumber rnd; for (int i=0;in;i+) int j=rnd.Random(n-i)+i; Swap(ai, aj); 20 舍伍德(Sherwood)算法 復(fù)習(xí)學(xué)過的Sherwood算法： （1）線性時間選擇算法 （2）快速排序算法 有時也會遇到這樣的情況，即所給的確定性算法無法直接改造 成舍伍德型算法。此時可借助于隨機

17、預(yù)處理技術(shù)隨機預(yù)處理技術(shù)，不改變原有不改變原有 的確定性算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德的確定性算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德 算法的效果算法的效果。例如，對于確定性選擇算法，可以用下面的洗牌 算法shuffle將數(shù)組a中元素隨機排列，然后用確定性選擇算法 求解。這樣做所收到的效果與舍伍德型算法的效果是一樣的。 template void Shuffle(Type a, int n) /隨機洗牌算法 static RandomNumber rnd; for (int i=0;in;i+) int j=rnd.Random(n-i)+i; Swap(ai, aj);

18、 21 如果用有序鏈表來表示一個含有如果用有序鏈表來表示一個含有n n個元素的有序集個元素的有序集S S，則在最，則在最 壞情況下，搜索壞情況下，搜索S S中一個元素需要中一個元素需要 (n)(n)計算時間。計算時間。 隨機化搜索算法：隨機抽取數(shù)組元素若干次，從最接近搜索隨機化搜索算法：隨機抽取數(shù)組元素若干次，從最接近搜索 元素元素x x的位置開始做順序搜索。的位置開始做順序搜索。 隨機抽取數(shù)組元素隨機抽取數(shù)組元素k k次，順序搜索平均比較次數(shù)為次，順序搜索平均比較次數(shù)為O(n/(k+1)O(n/(k+1) 取取k=k=sqrt(nsqrt(n) )，算法所需平均計算時間為，算法所需平均計算時

19、間為O(sqrt(nO(sqrt(n)。 i0 1 2 34 5 6 7 valuei 2 3 13 1 5 21 8 linki4 2 5 61 7 0 3 22 i01234567 valuei23 13 15 21 8 linki42561703 Void OrderList:Search(Type x,int Type max=Small; int m=floor(sqrt(double(n); /隨機抽取數(shù)組元素次數(shù) for (int i=1;i=m;i+) int j=rnd.Random(n)+1; /隨機產(chǎn)生數(shù)組元素位置 Type y=valuej; if (maxy) ind

20、ex=j; while (valuelinkindexx) index=linkindex; return (valuelinkindex=x); 23 Void OrderList:Insert(Type k) /插入指定元素k if (n=MaxLength)|(k=TailKey) return; int index; if ( !Search(k,index) ) value+n=k; linkn=linkindex; linkindex=n; i0 1 2 3 4 5 6 7 valuei 2 3 13 1 5 21 8 linki4 2 5 6 1 7 0 3 n=7+1 k=18

21、 index=3 i0 1 2 3 4 5 6 7 8 valuei 2 3 13 1 5 21 8 18 linki4 2 5 8 1 7 0 3 6 24 i01234567 valuei23 13 15 21 8 linki42561703 int OrderList:SearchLast(void) /搜索集合中指定元素k index=0; Type x=valuen Type max=Small; int m=floor(sqrt(double(n); /隨機抽取數(shù)組元素次數(shù) for (int i=1;i=m;i+) int j=rnd.Random(n)+1; /隨機產(chǎn)生數(shù)組元素位

22、置 Type y=valuej; if (maxy) index=j; while (linkindex!=n) index=linkindex; return (index); 25 Void OrderList:Delete(Type k) /刪除集合中指定元素k if (n=0)|(k=TailKey) return; int index; if (Search(k,index) int p=linkindex; if (p=n) linkindex=linkp; else if(linkp!=n) int q=SearchLast(); linkq=p; linkindex=linkp

23、; valuep=valuen; linkp=linkn; n-; i0 1 2 3 4 5 6 7 valuei 2 3 13 1 5 21 8 linki4 2 5 6 1 7 0 3 n=7 k=3 index=1 p=2 q=5 i0 1 2 3 4 5 6 valuei 2 8 13 1 5 21 linki4 5 3 6 1 2 0 26 跳躍表跳躍表 舍伍德型算法的設(shè)計思想還可用于設(shè)計高效的數(shù)據(jù)結(jié)構(gòu)舍伍德型算法的設(shè)計思想還可用于設(shè)計高效的數(shù)據(jù)結(jié)構(gòu)。 提高有序鏈表效率的一個技巧是在有序鏈表的部分結(jié)點處增設(shè) 附加指針以提高其搜索性能。在增設(shè)附加指針的有序鏈表中搜 索一個元素時，可借助

24、于附加指針跳過鏈表中若干結(jié)點，加快 搜索速度。這種增加了向前附加指針的有序鏈表稱為增加了向前附加指針的有序鏈表稱為跳躍表跳躍表。 應(yīng)在跳躍表的哪些結(jié)點增加附加指針以及在該結(jié)點處應(yīng)增加多 少指針完全采用隨機化方法來確定。這使得跳躍表可在O(logn) 平均時間內(nèi)支持關(guān)于有序集的搜索、插入和刪除等運算。 27 跳躍表 在一般情況下，給定一個含有n個元素的有序鏈表，可以將它改 造成一個完全跳躍表，使得每一個k級結(jié)點含有k+1個指針，分 別跳過2k-1，2k-1-1，20-1個中間結(jié)點。第i個k級結(jié)點安排在 跳躍表的位置i2k處，i0。這樣就可以在時間O(logn)內(nèi)完成集合 成員的搜索運算。在一個完

25、全跳躍表中，最高級的結(jié)點是logn 級結(jié)點。 跳躍表 為了在動態(tài)變化中維持跳躍表中附加指針的平衡性，必 須使跳躍表中k級結(jié)點數(shù)維持在總結(jié)點數(shù)的一定比例范圍 內(nèi)。注意到在一個完全跳躍表中，50%的指針是0級指針； 25%的指針是1級指針；(100/2k+1)%的指針是k級指 針。 完全跳躍表與完全二叉搜索樹完全二叉搜索樹的 情形非常類似。它雖然可以有效 地支持成員搜索運算，但不適應(yīng) 于集合動態(tài)變化的情況。集合元 素的插入和刪除運算會破壞完全 跳躍表原有的平衡狀態(tài)，影響后 繼元素搜索的效率。 29 跳躍表 在插入一個元素時，以概率1/2引入一個0級結(jié)點，以概率1/4引入 一個1級結(jié)點，以概率1/2

26、k+1引入一個k級結(jié)點。另一方面，一 個i級結(jié)點指向下一個同級或更高級的結(jié)點，它所跳過的結(jié)點數(shù)不 再準(zhǔn)確地維持在2i-1。在插入或刪除一個元素時，通過對跳躍表的 局部修改來維持其平衡性。 30 Bool SkipList:Search(const KType SkipNode *p=head; for (int i=Levels;i=0;i-) while (p-nexti-data nexti; e=p-next0-data; return (e=k); 31 SkipNode * SkipList:SaveSearch(const KType for (int i=Levels;i=0;i

27、-) while (p-nexti-data nexti; lasti=p; return (p-next0); /返回找到的結(jié)點或比k大的第一個結(jié)點 32 跳躍表 在一個完全跳躍表中，具有i級指針的結(jié)點中有一半同時 具有i+1級指針。為了維持跳躍表的平衡性，可以事先確定一 個實數(shù)0p1，并要求在跳躍表中維持在具有i級指針的結(jié)點中 同時具有i+1級指針的結(jié)點所占比例約為p。為此目的，在插入 一個新結(jié)點時，先將其結(jié)點級別初始化為0，然后用隨機數(shù)生 成器反復(fù)地產(chǎn)生一個0，1間的隨機實數(shù)q。如果qp，則使新 結(jié)點級別增加1，直至qp。由此產(chǎn)生新結(jié)點級別的過程可知， 所產(chǎn)生的新結(jié)點的級別為0的概率為

28、，級別為1的概率 為 ，級別為i的概率為 。如此產(chǎn)生的新結(jié) 點的級別有可能是一個很大的數(shù)，甚至遠(yuǎn)遠(yuǎn)超過表中元素的個 數(shù)。為了避免這種情況，用 作為新結(jié)點級別的上界。其 中n是當(dāng)前跳躍表中結(jié)點個數(shù)。當(dāng)前跳躍表中任一結(jié)點的級別 不超過 n p/ 1 log n p/1 log 1-p p(1-p)pi(1-p) 33 int SkipList:Level() /產(chǎn)生不超過MaxLevel的隨機級別 int lev=0； while (rnd.fRandom()Prob) lev+; return (lev=MaxLevel)?lev:MaxLevel; 12 34 SkipList /取得元素鍵值

29、 if (k=TailKey) throw BadInput(); /元素鍵值越界 SkipNode *p=SaveSearch(k); if (p-data=e) throw BadInput(); /元素已存在 int lev=Level(); /元素不存在，確定新結(jié)點級別 if(levLevels) /調(diào)整各級別指針 for (int i=Levels+1;i=lev;i+) lasti=head; Levels=lev; SkipNode *y=new SkipNode (lev+1); y-data=e; /產(chǎn)生新結(jié)點 for (int i=0;inexti=lasti-nexti;

30、 lasti-nexti=y; return *this; 35 SkipList /元素鍵值越界 SkipNode *p=SaveSearch(k); if (p-data!=k) throw BadInput(); /元素不存在 for (int i=0;inexti=p;i+) lasti-nexti=p-nexti; while (Levels0 e=p-data; delete p; return *this; /刪除鍵值為k的元素，并將所刪元素存入e 36 拉斯維加斯( Las Vegas )算法 拉斯維加斯算法的一個顯著特征是它所作的隨機性決策有可能拉斯維加斯算法的一個顯著特征是

31、它所作的隨機性決策有可能 導(dǎo)致算法找不到所需的解。導(dǎo)致算法找不到所需的解。 void obstinate(Object x, Object y) / 反復(fù)調(diào)用拉斯維加斯算法LV(x,y)，直到找到問題的一個解y bool success= false; while (!success) success=lv(x,y); 設(shè)p(x)是對輸入x調(diào)用拉斯維加斯算法獲得問題的一個解的概率。 一個正確的拉斯維加斯算法應(yīng)該對所有輸入x均有p(x)0。 設(shè)t(x)是算法obstinate找到具體實例x的一個解所需的平均時 間 ,s(x)和e(x)分別是算法對于具體實例x求解成功或求解失敗所 需的平均時間，則

32、有： 解此方程可得： )()()(1 ()()()(xtxexpxsxpxt )( )( )(1 )()(xe xp xp xsxt 補充例題：補充例題： 標(biāo)識重復(fù)元素算法標(biāo)識重復(fù)元素算法 （標(biāo)識重復(fù)元素問題）設(shè)有（標(biāo)識重復(fù)元素問題）設(shè)有n個元素保存在一維數(shù)組個元素保存在一維數(shù)組a中，其中，其 中有中有n/2個元素各不相同，而另外個元素各不相同，而另外n/2個元素有相同值。也就是個元素有相同值。也就是 說，總共有說，總共有(n/2)+1種不同的元素值?，F(xiàn)要求找出其中那個重種不同的元素值。現(xiàn)要求找出其中那個重 復(fù)元素。復(fù)元素。 template int Repeated Element(T a,

33、int n,Tint j=rand()% n; if (i!=j)return i; 拉斯維加斯算法在執(zhí)行中所做出的選擇依賴于隨拉斯維加斯算法在執(zhí)行中所做出的選擇依賴于隨 機數(shù)發(fā)生器，如果算法能夠得到問題的解，那么拉機數(shù)發(fā)生器，如果算法能夠得到問題的解，那么拉 斯維加斯算法求得的解是正確的。但有時，拉斯維斯維加斯算法求得的解是正確的。但有時，拉斯維 加斯算法的隨機決策有可能導(dǎo)致算法不能找到問題加斯算法的隨機決策有可能導(dǎo)致算法不能找到問題 的解。此時，需要對同一實例再次獨立調(diào)用該算法，的解。此時，需要對同一實例再次獨立調(diào)用該算法， 多次重復(fù)可以降低求解失敗的概率。多次重復(fù)可以降低求解失敗的概率。

34、 39 n后問題 對于n后問題的任何一個解而言，每一個皇后在棋盤上的位置無 任何規(guī)律，不具有系統(tǒng)性，而更象是隨機放置的。由此容易想到 下面的拉斯維加斯算法。 在棋盤上相繼的各 行中隨機地放置皇 后，并注意使新放 置的皇后與已放置 的皇后互不攻擊， 直至n個皇后均已 相容地放置好，或 已沒有下一個皇后 的可放置位置時為 止。 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Q Q Q Q ？ Q 40 n后問題 如果將上述隨機放置策略與回溯法相結(jié)合，可能會獲得更好的 效果?？梢韵仍谄灞P的若干行中隨機地放置皇后，然后在后繼 行中用回溯法繼續(xù)放置，直至找到一個解或宣告失敗。隨機放 置

35、的皇后越多，后繼回溯搜索所需的時間就越少，但失敗的概 率也就越大。 stopVegaspset 01.0000262.00-262.00 50.503933.8847.2380.39 120.046513.0010.20222.11 隨機放隨機放 置的置的Q數(shù)數(shù) 成功搜成功搜 索訪問索訪問 的平均的平均 結(jié)點數(shù)結(jié)點數(shù) 不成功不成功 訪問的訪問的 平均結(jié)平均結(jié) 點數(shù)點數(shù) 反復(fù)調(diào)用反復(fù)調(diào)用 找到解訪找到解訪 問的平均問的平均 結(jié)點數(shù)結(jié)點數(shù) 算法算法 成功成功 概率概率 41 蒙特卡羅(Monte Carlo)算法 n在實際應(yīng)用中常會遇到一些問題，不論采用確定性算法或 隨機化算法都無法保證每次都能得

36、到正確的解答。蒙特卡羅 算法則在一般情況下可以保證對問題的所有實例都以高概率 給出正確解，但是通常無法判定一個具體解是否正確。 n設(shè)p是一個實數(shù)，且1/2pn/2時， 稱元素x是數(shù)組T的主元素。 template bool Majority(Type *T, int n) / 判定主元素的蒙特卡羅算法 int i=rnd.Random(n)+1; Type x=Ti; / 隨機選擇數(shù)組元素 int k=0; for (int j=1;jn/2); / kn/2 時T含有主元素 template bool MajorityMC(Type *T, int n, double e) / 重復(fù)調(diào)用算法

37、Majority int k=ceil(log(1/e)/log(2); for (int i=1;i0，算法 majorityMC重復(fù)調(diào)用log(1/) 次 算法majority。它是一個偏真蒙特 卡羅算法，且其錯誤概率小于。算 法majorityMC所需的計算時間顯然 是O(nlog(1/ )。 43 蒙特卡羅(Monte Carlo)算法 若MC(x)是一致(1/2+)正確的蒙特卡羅算法，令： C=-2/log(1-4), e+d(1/2+)正確的蒙特卡羅算法。 -通過反復(fù)調(diào)用放大算法優(yōu)勢，得到可接受錯誤概率通過反復(fù)調(diào)用放大算法優(yōu)勢，得到可接受錯誤概率。 證明：設(shè)反復(fù)調(diào)用MC(x)次數(shù)為

38、nClog(1/d)。 p=(1/2+),q=1-p=(1/2-),m=n/2+1。出現(xiàn)頻次最高的正 確解至少，出現(xiàn)m次則出現(xiàn)錯誤的概率最多是：d （推導(dǎo) 見P262上） 實際應(yīng)用時，大多數(shù)蒙特卡羅算法重復(fù)調(diào)用后正確率提高很快。實際應(yīng)用時，大多數(shù)蒙特卡羅算法重復(fù)調(diào)用后正確率提高很快。 44 蒙特卡羅(Monte Carlo)算法 對于一個解所給問題的蒙特卡羅算法MC(x)，如果存在問 題實例的子集X使得： (1)當(dāng)xX時，MC(x)返回的解是正確的； (2)當(dāng)xX時，正確解是y0，但MC(x)返回的解未必是y0。 稱上述算法MC(x)是偏y0的算法。 重復(fù)調(diào)用一個一致的，p正確偏y0蒙特卡羅算

39、法k次，可得到一 個(1-(1-p)k)正確的蒙特卡羅算法，且所得算法仍是一個一致的 偏y0蒙特卡羅算法。 例：4次調(diào)用偏真蒙特卡羅算法，可以將正確率從55% 提高到1-(1-55%)495% ACM POJ 3318 Matrix Multiplication Time Limit: 2000MSMemory Limit: 65536K Total Submissions: 15971Accepted: 3447 Description You are given three n n matrices A, B and C. Does the equation A B = C hold tr

40、ue? Input The first line of input contains a positive integer n (n 500) followed by the the three matrices A, B and Crespectively. Each matrixs description is a block of n n integers. It guarantees that the elements of A and B are less than 100 in absolute value and elements of C are less than 10,00

41、0,000 in absolute value. Output Output YES if the equation holds true, otherwise NO. Hint Multiple inputs will be tested. So O(n3) algorithm will get TLE. Sample Input 2 1 0 2 3 5 1 0 8 5 1 10 26 Sample Output YES ACM POJ 3318 Matrix Multiplication Time Limit: 2000MSMemory Limit: 65536K Total Submissions: 15971Accepted: 3447 兩個矩陣直接相乘需要O(n3)的時間復(fù)雜度 再用O(n2)的時間進行AB與C的比較，返回 是否相等。 Sample Inp