第十九講 隨機算法

1、 隨機數(shù)：隨機序列；概率相等(均勻隨機)；不可預(yù)測；不可重現(xiàn)l在目前的計算機中：Ø無法產(chǎn)生真正的隨機數(shù)，因此在隨機算法中使用的隨機數(shù)都是一定程度上隨機的，即偽隨機數(shù)；Ø產(chǎn)生偽隨機數(shù)的方法· 線性同余法，確定性算法l輸入確定。l則對這個特定輸入的每運行過程是可重復(fù)的，運行結(jié)果是一樣的；比如，對于輸入<6,4,5,8,9,3>，正確的插入排序算法對這個輸入，每次的運行過程一樣，運行結(jié)果也一樣。隨機算法的基本思想：Randomized Algorithms (隨機算法)；lProbabilistic Algorithms (概率算法)；引入了隨機因素。l在隨

2、機算法中：Ø不要求算法對所有可能的輸入均正確計算；Ø只要求出現(xiàn)錯誤的可能性小到可以忽略的程度。另外也不要求對同一輸入，算法每次執(zhí)行時給出相同的結(jié)果。隨機算法的特點：l有不少問題，目前只有效率很差的確定性求解算法， 但用隨機算法去求解，可以（很快地）獲得相當(dāng)可信的結(jié)果。隨機算法的應(yīng)用領(lǐng)域：l隨機算法在分布式計算、通信、信息檢索、計算幾何、密碼學(xué)等許多領(lǐng)域都有著廣泛的應(yīng)用，最著名的是在公開密鑰體系、RSA算法方面的應(yīng)用。隨機算法的種類l通?？煞譃閮深悾?#216;Las Vegas算法ØMonte Carlo算法Las Vegas算法：在少數(shù)應(yīng)用中，可能出現(xiàn)求不出解的

3、情況；但一旦找到一個解，這個解一定是正確的；l在求不出解時，需再次調(diào)用算法進行計算，直到獲得解為止；對于此類算法，主要是分析算法的時間復(fù)雜度的期望值，以及調(diào)用一次產(chǎn)生失?。ㄇ蟛怀鼋猓┑母怕?。Monte Carlo算法：l通常不能保證計算出來的結(jié)果總是正確的，一般只能斷定所給解的正確性不小于p（ 1/2p1）；l通過算法的反復(fù)執(zhí)行（即以增大算法的執(zhí)行時間為代價），能夠使發(fā)生錯誤的概率小到可以忽略的程度；l由于每次執(zhí)行的算法是獨立的，故k次執(zhí)行均發(fā)生錯誤的概率為(1-p)k；l對于判定問題（回答只能是“Yes”或“No”）Ø帶雙錯的（two-sided error）: 回答”Yes”或”

4、No”都有可能錯；Ø帶單錯的（one-sided error）：只有一種回答可能錯。lLas Vegas算法可以看成是單錯概率為0的Monte Carlo算法兩類隨機算法的應(yīng)用場景：l使用時，選擇哪一類隨機算法，到底哪一種隨機算法好呢？Ø依賴于應(yīng)用，在不允許發(fā)生錯誤的應(yīng)用中（e.g. 人造飛船、電網(wǎng)控制等），Monte Carlo算法不可以使用；若小概率的出錯允許的話，Monte Carlo算法比Las Vegas算法要節(jié)省許多時間，是人們常常采用的方法。隨機算法的優(yōu)點：對于某一給定的問題，隨機算法所需的時間與空間復(fù)雜性，往往比當(dāng)前已知的、最好的確定性算法要好；到目前為止設(shè)

5、計出來的各種隨機算法，無論是從理解上還是實現(xiàn)上，都是極為簡單的；隨機算法避免了去構(gòu)造最壞情況的例子。找第k小元素的隨機算法（Las Vegas算法）在n個數(shù)中隨機的找一個數(shù)Ai=x, 然后將其余n-1個數(shù)與x比較，分別放入三個數(shù)組中：S1(元素均<x), S2(元素均=x), S3(元素均x)；若|S1|k ，則調(diào)用Select(k,S1)；若（|S1|+|S2|）k，則第k小元素就是x；否則就有（|S1|+|S2|） k，此時調(diào)用Select(k-|S1|-|S2|,S3)。找第k小元素的隨機算法 分析（Las Vegas算法）：定理：若以等概率方法在n個數(shù)中隨機取數(shù)，則該算法用到的比

6、較數(shù)的期望值不超過4n；說明：如果假定n個數(shù)互不相同，如果有相同的數(shù)的話，落在S2中的可能性會更大，比較數(shù)的期望值會更小一些。Sherwood隨機化方法（屬Las Vegas算法）如果某個問題已經(jīng)有了一個平均情況下較好的確定性算法，但是該算法在最壞情況下效率不高，此時引入一個隨機數(shù)發(fā)生器，（通常是服從均勻分布，根據(jù)問題需要也可以產(chǎn)生其他的分布），可將一個確定性算法改成一個隨機算法，使得對于任何輸入實例，該算法在概率意義下都有很好的性能ØSelect, Quicksort。l如果算法（所給的確定性算法）無法直接使用Sherwood方法，則可以采用隨機預(yù)處理的方法，使得輸入對象服從均勻分

7、布（或其他分布），然后再用確定性算法對其進行處理。所得效果在概率意義下與Sherwood型算法相同；Sherwood算法總能求得問題的一個解，且所求得的解是正確的；l當(dāng)一個確定性算法在最壞情況和平均情況下的時間復(fù)雜度有較大差別時，可在確定性算法中引入隨機性將其改造為Sherwood算法，以消除或減少問題的好壞輸入實例間的差別；Testing String Equality（Monte Carlo算法）問題描述：設(shè)A處有一個長字符串x（e.g. 長度為106），B處也有一個長字符串y，A將x發(fā)給B，由B判斷是否有x=y；l算法：首先由A發(fā)一個x的長度給B，若長度不等，則xy；若長度相等，則采用“

8、取指紋”的方法：A對x進行處理，取出x的“指紋”，然后將x的“指紋” 發(fā)給B；Ø由B檢查x的“指紋”是否等于y 的“指紋”；Ø若取k次“指紋”（每次取法不同），每次兩者結(jié)果均相同，則認為x與y是相等的；隨著k的增大，誤判率可趨于0。l常用的指紋：令I(lǐng)(x)是x的編碼，取Ip(x)；I(x) (mod p)作為x的指紋；這里的p是一個小于M的素數(shù)，M可根據(jù)具體需要調(diào)整。l錯判率分析：lB接到指紋Ip(x)后與Ip(y)比較：Ø如果Ip(x)Ip(y)，當(dāng)然有xy；Ø如果Ip(x)=Ip(y)而x¹y，則稱此種情況為一個誤匹配。l現(xiàn)在需要確定：誤匹

9、配的概率有多大？Ø若總是隨機地去取一個小于M的素數(shù)p，則對于給定的x和y，Prfailure =（使得Ip(x)=Ip(y)但x¹y的素數(shù)p(pM)的個數(shù)）（小于M的素數(shù)的總個數(shù)）；l誤匹配的概率小于 1/n,當(dāng)n很大時，誤匹配的概率很??；l設(shè)x¹y，如果取k個不同的小于2n2的素數(shù)來求Ip(x)和Ip(y)；l即k次試驗均有Ip(x)=Ip(y)但x¹y（誤匹配）的概率小于 1/nk；l當(dāng)n較大、且重復(fù)了k次試驗時，誤匹配的概率趨于0。Pattern Matching（Monte Carlo算法）問題：給定兩個字符串：X=x1,xn，Y=y1,ym，看

10、Y是否為X的子串？（即Y是否為X中的一段）。l可用KMP算法在O(m+n)時間內(nèi)獲得結(jié)果，但算法較為繁瑣。l考慮隨機算法（用brute-force 思想）；記X(j)=xjxj1xj+m-1（從X的第j位開始、長度與Y一樣的子串）；從起始位置j=1開始到j(luò)=n-m+1，不去逐一比較X(j)與Y，而僅逐一比較X(j)的指紋；Ip（X(j)）與Y的指紋Ip（Y）；l由于Ip（X(j+1)）可以很方便地根據(jù)Ip（X(j)）計算出來，故算法可以很快完成；1.隨機取一個小于M的素數(shù)p，置j1；2.計算Ip(Y)、Ip(X(1)及Wp(=2m mod p)；3.While jn-m+1 doif Ip(X(j)=Ip(Y) then return j/X(j)極有可能等于Y/else根據(jù)Ip(X(j)計算出Ip(X(j+1)；j增14. return 0; /X肯定沒有子串等于Y/l時間復(fù)雜度分析：l計算Ip(Y)、Ip(X(1)及2m mod p的時間不超過O(m)次運算；Ip(X(j+1)的計算，只需用O(1)時間；l由于循環(huán)最多執(zhí)行n-m+1次，故這部分的時間復(fù)雜度為O(n)，于是，總的時間復(fù)雜性為O(m+n)；l當(dāng)YX(j)，但Ip(Y)=Ip(X(j)時產(chǎn)生失??；l失敗的概率Prfailure<1/n，即失敗的