隨機算法課件

隨機算法2010.11.24學習要點理解產(chǎn)生偽隨機數(shù)的算法掌握數(shù)值隨機化算法的設(shè)計思想掌握蒙特卡羅算法的設(shè)計思想掌握拉斯維加斯算法的設(shè)計思想掌握舍伍德算法的設(shè)計思想隨機算法2/66一、

引言分治、動態(tài)規(guī)劃、貪心法、回溯和分支限界等算法的每一計算步驟都是確定的，本章所討論的隨機算法允許執(zhí)行過程中隨機選擇下一計算步驟。在多數(shù)情況下，當算法在執(zhí)行過程中面臨一個選擇時，隨機性選擇常比最優(yōu)選擇省時，因此隨機算法可在很大程度上降低算法復(fù)雜性。隨機算法的一個基本特征是對所求解問題的同一實例用同一隨機算法求解兩次可能得到完全不同的效果(所需時間或計算結(jié)果)。本章將要介紹的隨機算法包括：數(shù)值隨機算法求解數(shù)值問題的近似解，精度隨計算時間增加而不斷提高舍伍德算法總能求得問題的一個正確解，消除算法最壞情形行為與特定實例之間的關(guān)聯(lián)性，并不提高平均性能，也不是刻意避免算法的最壞情況行為拉斯維加斯算法求解問題的正確解，但可能找不到解蒙特卡羅算法求解問題的解，但這個解未必正確，且一般情況下無法有效判定正確性隨機算法3/66想象自己是神話故事的主人公，你有一張不易懂的地圖，上面描述了一處寶藏的藏寶地點。經(jīng)分析你能確定最有可能的兩個地點是藏寶地點，但二者相距甚遠。假設(shè)你如果已到達其中一處，就立即知道該處是否為藏寶地點。你到達兩處之一地點及從其中一處到另一處的距離是5天的行程。進一步假設(shè)有一條惡龍，每晚光顧寶藏并從中拿走一部分財寶。假設(shè)你取寶藏的方案有兩種：1、故事隨機算法4/66

方案1.花4天的時間計算出準確的藏寶地點，然后出發(fā)尋寶，一旦出發(fā)不能重新計算

方案2.有一個小精靈告訴你地圖的秘密，但你必須付給他報酬，相當于龍3晚上拿走的財寶

Prob1.1.1若忽略可能的冒險和出發(fā)尋寶的代價，你是否接受小精靈的幫助？顯然，應(yīng)該接受小精靈的幫助，因為你只需給出3晚上被盜竊的財寶量，否則你將失去4晚被盜財寶量。但是，若冒險，你可能做得更好！隨機算法5/66

設(shè)x是你決定之前當日的寶藏價值，設(shè)y是惡龍每晚盜走的寶藏價值，并設(shè)x>9y

方案1：4天計算確定地址，行程5天，你得到的寶藏價值為：x-9y

方案2：3y付給精靈，行程5天失去5y，你得到的寶藏價值為：x-8y

方案3：投硬幣決定先到一處，失敗后到另一處(冒險方案)

一次成功所得：x-5y，機會1/2

二次成功所得：x-10y，機會1/2}期望贏利：x-7.5y隨機算法6/66該故事告訴我們：當一個算法面臨某種選擇時，有時隨機選擇比耗時做最優(yōu)選擇更好，尤其是當最優(yōu)選擇所花的時間大于隨機選擇的平均時間的時侯。顯然，隨機算法只能是期望的時間更有效，但它有可能遭受到最壞的可能性。隨機算法7/66期望時間和平均時間的區(qū)別確定算法的平均執(zhí)行時間輸入規(guī)模一定的所有輸入實例是等概率出現(xiàn)時，算法的平均執(zhí)行時間。隨機算法的期望執(zhí)行時間反復(fù)解同一個輸入實例所花的平均執(zhí)行時間。 因此，對隨機算法可以討論如下兩種期望時間平均的期望時間：所有輸入實例上平均的期望執(zhí)行時間最壞的期望時間：最壞的輸入實例上的期望執(zhí)行時間隨機算法8/662、隨機數(shù)隨機數(shù)在隨機算法設(shè)計中扮演著十分重要的角色。在現(xiàn)實計算機上無法產(chǎn)生真正的隨機數(shù)，因此在隨機算法中使用的隨機數(shù)都是一定程度上隨機的，即偽隨機數(shù)。線性同余法是產(chǎn)生偽隨機數(shù)的最常用的方法。由線性同余法產(chǎn)生的隨機序列a0,a1,…,an滿足其中b≥0，c≥0，d≥m。d稱為該隨機序列的種子。如何選取該方法中的常數(shù)b、c和m直接關(guān)系到所產(chǎn)生的隨機序列的隨機性能。這是隨機性理論研究的內(nèi)容，已超出本書討論的范圍。從直觀上看，m應(yīng)取得充分大，因此可取m為機器大數(shù)，另外應(yīng)取gcd(m,b)=1，因此可取b為一素數(shù)。隨機算法9/66為便于講解，本章約定RandomNumber為隨機數(shù)類其中有成員函數(shù)：Random(unsignedlongn)//產(chǎn)生0:n-1間的隨機整數(shù)fRandom()//產(chǎn)生[0,1)之間的隨機實數(shù)

隨機函數(shù)uniform設(shè)a，b為實數(shù)，a<b,

uniform(a,b)返回x，a≤x<b②設(shè)i，j為整數(shù)，i≤j,

uniform(i,j)=k,i≤k≤j③

設(shè)X是非空有限集，

uniform(X)∈X隨機算法10/66二、數(shù)值隨機算法1、用隨機投點法計算π值2、計算定積分隨機算法11/661、用隨機投點法計算π值

這類算法主要用于找到一個數(shù)字問題的近似解實驗：將n根飛鏢隨機投向一正方形的靶子，計算落入此正方形的內(nèi)切圓中的飛鏢數(shù)目k。 假定飛鏢擊中方形靶子任一點的概率相等(用計算機模擬比任一飛鏢高手更能保證此假設(shè)成立)

設(shè)圓的半徑為r，面積s1=πr2,方靶面積s2=4r2

由等概率假設(shè)可知落入圓中的飛鏢和正方形內(nèi)的飛鏢平均比為：

由此知：

隨機算法12/66求π近似值的算法

為簡單起見，只以上圖的第1象限為樣本doubleDarts(intn){staticRandomNumberdart;intk=0;for(inti=1;i<=n;i++){doublex=dart.fRandom();doubley=dart.fRandom();if((x*x+y*y)<=1)k++;}return4*k/double(n);}實驗結(jié)果：π=3.141592654 n=1000萬:3.140740,3.142568(2位精確) n=1億:3.141691,3.141363(3位精確) n=10億:3.141527,3.141507(4位精確)隨機算法13/66設(shè)f:[0,1]→[0,1]是一個連續(xù)函數(shù)，則由曲線y=f(x),x軸,y軸和直線x=1圍成的面積由下述積分給出：

向單位面積的正方形內(nèi)投鏢n次，落入陰影部分的鏢的數(shù)目為k，則只要n足夠大

2、計算定積分隨機算法14/66求定積分的算法

doubleHitorMiss(n){staticRandomNumberdart;intk=0;for(inti=1;i<=n;i++){doublex=dart.fRandom();doubley=dart.fRandom();if(y≤f(x))k++;}returnk/double(n);}

隨機算法15/66三、舍伍德(Sherwood)算法Sherwood算法能夠平滑不同輸入實例的執(zhí)行時間設(shè)A是一個確定算法，tA(x)是解某個實例x的執(zhí)行時間，設(shè)n是一整數(shù)，Xn是大小為n的實例的集合 假定Xn中每一個實例是等可能出現(xiàn)的，則算法A解一個大小為n的實例的平均執(zhí)行時間是：

這里無法消除這樣的可能性： 存在一個size為n的實例x使得>>設(shè)B是一個隨機算法，對每個size為n的實例x都滿足 這里tB(x)是算法B在實例x上的期望值，s(n)是隨機算法B為了取得均勻性所付出的成本。隨機算法16/66雖然算法B的執(zhí)行時間也可能偶然地在某一個實例x上大于，但這種偶然性行為只是由于算法所做的概率選擇引起的，與實例x本身沒有關(guān)系。因此，不再有最壞的情況的實例，但有最壞的執(zhí)行時間。算法B在一個size為n的實例集上的平均期望時間可定義為：很清楚。也就是說Sherwood算法的平均執(zhí)行時間略為增加。§1.4Sherwood算法隨機算法17/66在n個元素中選擇第k個最小元素的算法關(guān)鍵在于選擇劃分元，有兩種常用的方法：精心挑選劃分元，使之是一個偽中值的元素，這樣可使算法的最壞執(zhí)行時間是O(n)。取當前搜索區(qū)間的第一個元素作劃分元，平均時間為O(n)，但最壞時間是O(n2)。由于此方法簡單，故平均性能較前者好。該類確定算法的特點：設(shè)T[1..n]互不相同，算法的執(zhí)行時間不是依賴于數(shù)組元素的值，而是依賴于元素間的相對次序，因此，表達時間的函數(shù)不只是依賴于n，而且還依賴于數(shù)組元素的排列δ，

設(shè)tp(n,δ)——使用偽中值算法的執(zhí)行時間

ts(n,δ)——使用簡單算法的執(zhí)行時間 對多數(shù)的δ

，1、選擇與排序隨機算法18/66隨機算法：

隨機選擇T中的元素作為劃分元 期望時間為O(n)，獨立于輸入實例 注意：算法的某次執(zhí)行有可能達到O(n2)，但這種可能性與實例無關(guān) 隨著n的增大，這種可能性會很小。 設(shè)tr(n,δ)是Sherwood算法的平均時間，則§1.4.1選擇與排序隨機算法19/66

將選擇和排序的確定算法修改為Sherwood算法很簡單，但是當算法較復(fù)雜，就很難對其進行修改。注意，只有當該算法平均時間性能較優(yōu)，但最壞性能較差時，才有修改的價值。 一般方法是：將被解的實例變換到一個隨機實例。//預(yù)處理用確定算法解此隨機實例，得到一個解。將此解變換為對原實例的解。//后處理2、隨機預(yù)處理隨機算法20/66

設(shè)：f:X→Y是解某問題用到的一個函數(shù)，且平均性能較優(yōu)(指相應(yīng)的算法)；

n∈N，Xn是size為n的實例的集合，An是一個大小和Xn大小相同的集合，假定在An中能夠有效地均勻隨機抽樣

A=∪An

則隨機的預(yù)處理由一對函數(shù)構(gòu)成：

u和v滿足三個性質(zhì)：①

②③

函數(shù)u和v在最壞情況下能夠有效計算§1.4.2隨機的預(yù)處理隨機算法21/66

于是確定算法f(x)可改造為Sherwood算法：

RH(x){

//用Sherwood算法計算f(x) n←length[x];//x的size為n r←uniform(An);//隨機取一元素

y←u(x,r);//將原實例x轉(zhuǎn)化為隨機實例y s←f(y);//用確定算法求y的解s returnv(r,s);//將s的解變換為x的解

}§1.4.2隨機的預(yù)處理隨機算法22/66選擇和排序的舍伍德算法只需進行隨機預(yù)處理，將輸入實例中元素打亂即可，相當于洗牌，后處理無需進行例如，對于確定性選擇算法，可以用下面的洗牌算法Shuffle將數(shù)組a中元素隨機排列，然后用確定性選擇算法求解。這樣做所收到的效果與舍伍德型算法的效果是一樣的。template<classType>voidShuffle(Typea[],intn){ //隨機洗牌算法staticRandomNumberrnd;for(inti=0;i<n;i++){//在a[i..n]中隨機選1元素放在a[i]上intj=rnd.Random(n-i)+i;Swap(a[i],a[j]);}}隨機算法23/662、跳躍表舍伍德型算法的設(shè)計思想可用于設(shè)計高效的數(shù)據(jù)結(jié)構(gòu)。如果用有序鏈表來表示一個含有n個元素的有序集S，則在最壞情況下，搜索S中一個元素需要?(n)計算時間。提高有序鏈表效率的一個技巧是在有序鏈表的部分結(jié)點處增設(shè)附加指針以提高其搜索性能。在增設(shè)附加指針的有序鏈表中搜索一個元素時，可借助于附加指針跳過鏈表中若干結(jié)點，加快搜索速度。這種增加了向前附加指針的有序鏈表稱為跳躍表。應(yīng)在跳躍表的哪些結(jié)點增加附加指針以及在該結(jié)點處應(yīng)增加多少指針完全采用隨機化方法來確定。這使得跳躍表可在O(logn)平均時間內(nèi)支持關(guān)于有序集的搜索、插入和刪除等運算。隨機算法24/66在一般情況下，給定一個含有n個元素的有序鏈表，可以將它改造成一個完全跳躍表，使得每一個k級結(jié)點含有k+1個指針，分別跳過2k-1，2k-1-1，…，20-1個中間結(jié)點。第i個k級結(jié)點安排在跳躍表的位置i2k處，i≥0。這樣就可以在時間O(logn)內(nèi)完成集合成員的搜索運算。在一個完全跳躍表中，最高級的結(jié)點是

logn

級結(jié)點。完全跳躍表與完全二叉搜索樹的情形非常類似。它雖然可以有效地支持成員搜索運算，但不適應(yīng)于集合動態(tài)變化的情況。集合元素的插入和刪除運算會破壞完全跳躍表原有的平衡狀態(tài)，影響后繼元素搜索的效率。隨機算法25/66為了在動態(tài)變化中維持跳躍表中附加指針的平衡性，必須使跳躍表中k級結(jié)點數(shù)維持在總結(jié)點數(shù)的一定比例范圍內(nèi)。注意到在一個完全跳躍表中，50%的指針是0級指針；25%的指針是1級指針；…；(100/2k+1)%的指針是k級指針。因此，在插入一個元素時，以概率1/2引入一個0級結(jié)點，以概率1/4引入一個1級結(jié)點，…，以概率1/2k+1引入一個k級結(jié)點。另一方面，一個i級結(jié)點指向下一個同級或更高級的結(jié)點，它所跳過的結(jié)點數(shù)不再準確地維持在2i-1。經(jīng)過這樣的修改，就可以在插入或刪除一個元素時，通過對跳躍表的局部修改來維持其平衡性。隨機算法26/66注意到，在一個完全跳躍表中，具有i級指針的結(jié)點中有一半同時具有i+1級指針。為了維持跳躍表的平衡性，可以事先確定一個實數(shù)0<p<1，并要求在跳躍表中維持在具有i級指針的結(jié)點中同時具有i+1級指針的結(jié)點所占比例約為p。為此，在插入一個新結(jié)點時，先將其結(jié)點級別初始化為0，然后用隨機數(shù)生成器反復(fù)地產(chǎn)生一個[0，1)間的隨機實數(shù)q。如果q<p，則使新結(jié)點級別增加1，直至q≥p。由此可知，所產(chǎn)生的新結(jié)點的級別為0的概率為1-p，級別為1的概率為p(1-p)，…，級別為i的隨機為pi(1-p)。如此產(chǎn)生的新結(jié)點的級別有可能是一個很大的數(shù)，甚至遠遠超過表中元素的個數(shù)。為了避免這種情況，用log1/pn作為新結(jié)點級別的上界。其中n是當前跳躍表中結(jié)點個數(shù)。當前跳躍表中任一結(jié)點的級別不超過log1/pn隨機算法27/66拉斯維加斯算法的一個顯著特征是它所作的隨機性決策有可能導(dǎo)致算法找不到所需的解。算法的一般形式

LV(x,y,success)——x是輸入的實例，y是返回的參數(shù)，success是布爾值，true表示成功，false表示失敗

p(x)——對于實例x，算法成功的概率

s(x)——算法求解成功時所需的期望時間

e(x)——算法求解失敗時所需的期望時間一個正確的LasVegas算法，要求對每個實例x，p(x)>0，更好的情況是：四、

拉斯維加斯(LasVegas)算法隨機算法28/66 Obstinate(x){ repeat LV(x,y,success); untilsuccess; returny;}

設(shè)t(x)是算法obstinate找到一個正確解所需的期望時間，則

若要最小化t(x)，則需在p(x),s(x)和e(x)之間進行某種折衷?！?.5LasVegas算法隨機算法29/661、n后問題對于n后問題的任何一個解而言，每一個皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機放置的。由此容易想到下面的拉斯維加斯算法。在棋盤上相繼的各行中隨機地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至n個皇后均已相容地放置好，或已沒有下一個皇后的可放置位置時為止。如果將上述隨機放置策略與回溯法相結(jié)合，可能會獲得更好的效果?？梢韵仍谄灞P的若干行中隨機地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個解或宣告失敗。隨機放置的皇后越多，后繼回溯搜索所需的時間就越少，但失敗的概率也就越大。隨機算法30/66傳統(tǒng)的回溯法(8后問題)置當前行為第1行，當前列為第1列，即i←j←1;whilei≤8do{//當前行號≤8

檢查當前行：從當前列j起向后逐列試探，尋找安全列號；

if

找到安全列號then{

放置皇后，將列號記入棧，并將下一行置為當前行(i++); j←1;}//當前列置為1

else{

退?；厮莸缴弦恍?，即i--； 移去該行已放置的皇后，以該皇后所在列的下一列作為當前列；

} }隨機算法31/66LasVegas方法向量try[1..8]中存放結(jié)果

try[i]——表示第i個皇后放在（i，try[i]）位置上try[1..k]稱為k-promising是指： 若k個皇后的位置(0≤k≤8):(1,try[1]),(2,try[2]),…,(k,try[k])互相不攻擊，則稱try[1..k]是k-promising的。

形式化：對，若有

(式1)

若式1成立，則：無行沖突：無須考慮，因為第i個皇后放在第i行，故同一行不會有兩皇后； 隨機算法32/66無列沖突：若對任意不同的兩行i、j，因為其列數(shù)之差不為0，故任意兩皇后不可能在同一列上。135°對角線無沖突：和沖突時有： 即故任兩皇后不會在135°對角線上沖突。45°對角線無沖突：和沖突時有： 即try[i]-try[j]=i-j

故任兩皇后不會在45°對角線上沖突。綜上所述，式1成立時try[1..k]是k-promising。顯然，若k≤1，則向量try[1..k]是k-promising的，對8后問題，解是8-promising的。算法隨機算法33/66QueensLv(success){//貪心的LV算法，所有皇后都是隨機放置

//若Success=true，則try[1..8]包含8后問題的一個解。

col,diag45,diag135←Φ；//列及兩對角線集合初值為空

k←0；//行號

repeat//try[1..k]是k-promising，考慮放第k+1個皇后

nb←0；//計數(shù)器，nb值為（k+1)th皇后的open位置總數(shù)

fori←1to8do{//i是列號

if(icol)and(i-k-1diag45)and(i+k+1diag135)then{

//列i對（k+1）th皇后可用，但不一定馬上將其放在第i列

nb←nb+1；

ifuniform(1..nb)=1then//或許放在第i列

j←i；//注意第一次uniform一定返回1，即j一定有值 }//endif }//endfor，在nb個安全的位置上隨機選擇1個位置j放置之隨機算法34/66if(nb>0)then{//nb=0時無安全位置，第k+1個皇后尚未放好

//在所有nb個安全位置上，(k+1)th皇后選擇位置j的概率為1/nb k←k+1；//try[1..k+1]是(k+1)-promisingtry[k]←j；//放置(k+1)th個皇后

col←col∪{j}；

diag45←diag45∪{j-k}；

diag135←diag135∪{j+k}；

}//endifuntil（nb=0）or（k=8）；//當前皇后找不到合適的位置或try是

//8-promising時結(jié)束。

success←（nb>0）；}隨機算法35/66問題及改進消極：LV算法過于消極，一旦失敗，從頭再來樂觀：回溯法過于樂觀，一旦放置某個皇后失敗，就進行系統(tǒng)回退一步的策略，而這一步往往不一定有效。

折中：會更好嗎？一般情況下為此。 先用LV方法隨機地放置前若干個結(jié)點，例如k個。 然后使用回溯法放置后若干個結(jié)點，但不考慮重放前k個結(jié)點。若前面的隨機選擇位置不好，可能使得后面的位置不成功，如若前兩個皇后的位置是1、3。隨機放置的皇后越多，則后續(xù)回溯階段的平均時間就越少，失敗的概率也就越大。隨機算法36/66改進算法

折中算法只需將QueensLV的最后兩行改為：

untilnb=0ork=stopVegas；

if（nb>0)then//已隨機放好stopVegas個皇后

backtrace(k,col,diag45,diag135,success); else success←false；

stopVegas——控制隨機放置皇后的個數(shù)，如何選擇？改進算法的試驗結(jié)果：

隨機算法37/66

純回溯時間：40ms stopVegas=2or3：10ms（平均） 純貪心LV：23ms（平均） 結(jié)論：一半略少的皇后隨機放置較好。StopVegaspset01114—1141139.63—39.6320.87522.5339.6728.2030.493113.4815.1029.0140.261810.318.7935.1050.16249.337.2946.9260.13579.056.9853.5070.129396.9755.9380.129396.9753.93隨機算法38/662、整數(shù)因子分解設(shè)n>1是一個整數(shù)。關(guān)于整數(shù)n的因子分解問題是找出n的如下形式的唯一分解式：其中，p1<p2<…<pk是k個素數(shù)，m1,m2,…,mk是k個正整數(shù)。若n是合數(shù)，則n必有一個非平凡因子x(不是1和n本身)。給定合數(shù)n，求n的一個非平凡因子的問題稱為整數(shù)n的因子分割問題。intSplit(intn){intm=floor(sqrt(double(n)))//下取整;for(inti=2;i<=m;i++)if(n%i==0)returni;return1;}事實上，算法split(n)是對范圍在1～x的所有整數(shù)進行了試除而得到范圍在1～x2的任一整數(shù)的因子分割。隨機算法39/66Pollard算法在開始時選取0～n-1范圍內(nèi)的隨機數(shù)，然后遞歸地由xi=(xi-12-1)modn產(chǎn)生無窮序列x1,x2,…,xk,…對于i=2k，以及2k<j≤2k+1，算法計算出xi-xj與n的最大公因子d=gcd(xi-xj，n)。如果d是n的非平凡因子，則實現(xiàn)對n的一次分割，算法輸出n的因子d。對Pollard算法更深入的分析可知，執(zhí)行算法的while循環(huán)約p1/2次后，Pollard算法會輸出n的一個因子p。由于n的最小素因子p≤n1/2，故Pollard算法可在O(n1/4)時間內(nèi)找到n的一個素因子。voidPollard(intn){//

求因子分割的拉斯維加斯算法RandomNumberrnd;inti=1;intx=rnd.Random(n);//隨機整數(shù)inty=x,k=2;while(true){i++;x=(x*x-1)%n;//求n的非平凡因子intd=gcd(y-x,n);if((d>1)&&(d<n))cout<<d<<endl;if(i==k){y=x;k*=2;}}}隨機算法40/66存在某些問題，無論是確定的還是隨機的，均找不到有效的算法獲得正確的答案。 MonteCarlo算法偶然會犯錯，但它無論對何實例均能以高概率找到正確解。通常無法判定一個具體解是否正確。基本概念Def1：設(shè)p是一個實數(shù)，且1/2<p<1，若一個MC算法以不小于p的概率返回一個正確的解，則該MC算法稱為p-正確，算法的優(yōu)勢（advantage）是p-1/2.Def2：若一個MC算法對同一實例決不給出兩個不同的正確解，則該算法稱是相容的（consistent）或一致的。五、

蒙特卡羅(MonteCarlo)算法隨機算法41/66某些MC算法的參數(shù)不僅包括被解的實例，還包括錯誤概率的上界。因此，這樣算法的時間被表示為實例大小及相關(guān)可接受的錯誤概率的函數(shù)?；舅枷耄簽榱嗽黾右粋€一致的、p-正確算法成功的概率，只需多次調(diào)用同一算法，然后選擇出現(xiàn)次數(shù)最多的解。 例：設(shè)MC(x)是一個一致、75%-correct的MC算法，考慮下述算法：

MC3(x){ t←MC(x);u←MC(x);v←MC(x); ift=uort=vthenreturnt; elsereturnv; }隨機算法42/66該算法是一致的和27/32-correct的(約84%)pf:

相容性（一致性）易證。 ∵t、u、v正確的概率為75%=3/4=p∴錯誤的概率為q=1/4. 1)若t、u、v均正確，∵MC是一致的

∴t=u=v，則MC3返回的t正確，此概率為：(3/4)3

2)若t、u、v恰有兩個正確則MC3返回 此概率為：

3)若t、u、v恰有一個正確，則只有v正確時，MC3返回正確答案，此概率為：隨機算法43/66因此MC3成功的概率為：

多運行2次（共3次）使成功率設(shè)ε和δ是正實數(shù)，且ε+δ<1/2，如果重復(fù)調(diào)用一個一致的，(1/2+ε)-correct的MC算法2m-1次，則可得到一個(1-δ)-correct的最終算法，其中：隨機算法44/66有偏算法 重復(fù)一個算法幾百次來獲得較小的出錯概率是沒有吸引力的，幸運地，大多數(shù)MC算法實際上隨著重復(fù)次數(shù)的增加，正確概率增長會更快。Def：(偏真算法)為簡單起見，設(shè)MC(x)是解某個判定問題，對任何x，若當MC(x)返回true時解總是正確的，僅當它返回false時才有可能產(chǎn)生錯誤的解，則稱此算法為偏真的(true-biased)。 顯然，當多次調(diào)用一個偏真的MC算法時，只要有一次調(diào)用返回true就可斷定相應(yīng)的解是正確解。

對于偏真的MC算法，重復(fù)調(diào)用4次，就可將55%-正確的算法改進到95%正確。6次重復(fù)就可得到99%正確的算法，且對p>1/2的要求可以放寬到p>0即可。隨機算法45/66Def：(偏y0算法)更一般的情況即所討論的問題不一定是一個判定問題。一個MC是偏y0的算法(y0是某個特定解)，即如果存在問題實例的子集X使得：若被解實例，則算法MC(x)返回的解總是正確的(無論返回y0還是非y0)若，正確解是y0

，但MC并非對所有這樣的實例x都返回正確解y0。總結(jié)：若算法返回y0時，它總是正確的，無需測試x是否是X的成員；若返回非y0時以p為概率正確（當x不是X的成員，解是正確的，當x是X的成員，解是錯誤的，產(chǎn)生這種錯誤的概率不超過1-p）。重復(fù)調(diào)用一個一致的p正確偏y0的蒙特卡羅算法k次，可得到一個

1-(1-p)k正確的蒙特卡羅算法，且所得算法仍是一個一致的偏y0蒙特卡羅算法隨機算法46/66Def：設(shè)T[1..n]是n個元素的數(shù)組，若T中等于x的元素個數(shù)大于n/2(即)，則稱x是數(shù)組T的主元素。

(Note：若存在，則只可能有1個主元素)判T是否有主元素template<classType>boolMaj(Type*T,intn){//測試隨機元素x是否為T的主元素inti=rnd.Random(n)+1;Typex=T[i];//隨機選擇數(shù)組元素intk=0;for(intj=1;j<=n;j++)if(T[j]==x)k++;return(k>n/2);//k>n/2時T含有主元素}1、主元素問題Maj算法是一個偏真的1/2正確的算法：若Maj返回true，則T必有主元素，解一定正確。因為隨機選中主元素的概率大于1/2，故該算法是1/2-正確。若Maj返回false，則T可能沒有主元素。當然，若T沒有主元素，則必返回false。隨機算法47/66實際使用時，50%的錯誤概率是不可容忍的。而對有偏算法，可以通過重復(fù)調(diào)用技術(shù)來使錯誤概率降低到任何值。

Maj2(Type*T,intn){ ifMaj(T,n)then returntrue;//1次成功

else//1次失敗后調(diào)用第2次

returnMaj(T,n);//調(diào)用2次

}隨機算法48/66分析

1)若T無主元素，則Maj每次均返回false，Maj2亦肯定返 回false。此時算法返回值正確（成功）。

2)若T有主元素，則：

第一次調(diào)用Maj返回true的概率是p>1/2，此時Maj2亦返回true。第一次調(diào)用Maj返回false的概率為1-p，第2次調(diào)用Maj仍以概率p返回true，Maj2亦返回true，其概率為：(1-p)p，此時算法返回值正確（成功）。總結(jié)：當T有主元時，Maj2返回true的概率是：

p+(1-p)p=1-(1-p)2>3/4.

即：Maj2是一個偏真的3/4正確的MC算法。隨機算法49/66算法改進 錯誤的概率能夠迅速減小，主要是因為重復(fù)調(diào)用Maj的結(jié)果是相互獨立的，即：對同一實例T，某次Maj返回false，并不會影響繼續(xù)調(diào)用返回true的概率。 因此，當T含有主元素時，k次重復(fù)調(diào)用Maj均返回false的概率小于2-k。 另一方面，在k次調(diào)用中，只要有一次Maj返回true，即可判定T有主元素。隨機算法50/66當需要控制算法出錯概率小于ε>0時，相應(yīng)算法調(diào)用Maj的次數(shù)為：template<classType>boolMajMC(Type*T,intn,doubleε){//重復(fù)調(diào)用算法Majintk=

for(inti=1;i<=k;i++)if(Maj(T,n))returntrue;returnfalse;}該算法的時間為。注意，這里只是用此問題來說明MC算法，實際上對于判定主元素問題存在O(n)的確定性算法。隨機算法51/662、素數(shù)測試判定一個給定的整數(shù)是否為素數(shù)，到目前為止尚未找到有效的確定性算法或LasVegas算法。簡單的隨機算法

prime(n){ d←uniform(2..); return }若返回false，則算法幸運地找到了n的一個非平凡因子，n為合數(shù)。若返回true，則未必是素數(shù)。實際上，若n是合數(shù)，prime亦以高概率返回true。隨機算法52/66

例如：

prime在2~51內(nèi)隨機選一整數(shù)d

成功：d=43，算法返回false(概率為2%)，結(jié)果正確

失?。篸≠43，算法返回true(概率為98%)，結(jié)果錯誤 當n增大時，情況更差。Fermat小定理 若n是素數(shù)，則?a∈[1，n-1]，有變換命題（逆否定理） 設(shè)n和a是整數(shù)，若

a∈[1，n-1]使，則n不是素數(shù)。隨機算法53/66素性測定算法（偏假的：返回false時解總是正確的）：

Fermat(n){

RandomNumberrnd; a←rnd.Random(n-2)+1; ifthen returntrue;//未必正確，n未必為素數(shù)

else returnfalse；//正確，n一定是合數(shù)

}隨機算法54/66

結(jié)論：我們不能通過驗證an-1modn是否為1來判定n是否為素數(shù)，F(xiàn)ermat小定理只是素數(shù)判定的必要條件。例如： ∵ ∴ 若是時呢？設(shè)n=15(合數(shù))，另外，有的合數(shù)也滿足Fermat小定理，稱為Carmichael數(shù)，如561，1105，1729。統(tǒng)計表明，在前10億個自然數(shù)中共有50,847,534個素數(shù)，而滿足2n-1modn=1的合數(shù)n有5,597個。判定錯誤的可能性約為0.00011。隨機算法55/66偽素數(shù)和素性偽證據(jù)

設(shè)2≤a≤n-2，一個滿足的合數(shù)n稱為以a為底的偽素數(shù)，a稱為n的素性偽證據(jù)。若將Fermat測試改為從2~n-2之間隨機選a，則只有選到一個偽證據(jù)時，對合數(shù)的測試失敗(被認為是素數(shù)).隨機算法56/66偽證據(jù)有多少？總體情況是偽證據(jù)相當少

1000之內(nèi)的奇合數(shù)測試誤差概率<3.3%。n較大時，概率更小。有些合數(shù)偽證據(jù)比例相當高 如561，有318個偽證據(jù)，超過證據(jù)數(shù)的一半（2~559）。極端情況：Fermat(651693055693681)返回true的概率>99.9965%一般地，對，存在無窮多個合數(shù)，使得Fermat測試發(fā)現(xiàn)他們是合數(shù)的概率小于δ

即：對任意的p>0，F(xiàn)ermat測試都不是p-正確的。因此，將Fermat測試重復(fù)固定次數(shù)，并不能將誤差降到任意小的ε內(nèi)。隨機算法57/66Fermat測試改進強偽素數(shù) 設(shè)n是一個大于4的奇整數(shù)，q和m是使得n-1=2qm的正整數(shù)，其中m為奇數(shù)，設(shè)B(n)是如下定義的整數(shù)集合： 當且僅當2≤a≤n-2且滿足下述2個條件之一：

或整數(shù)i，0≤i<q滿足當n為素數(shù)時，，均有

當n為合數(shù)時，若，則稱n為一個以a為底的強偽素數(shù)，稱a為n素性的強偽證據(jù)。n為素數(shù)，說明它對所有底均為強偽素數(shù)。

隨機算法58/66Btest(a，n){//n為奇數(shù)，