第十九講 隨機算法

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

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

3、情況；但一旦找到一個解，這個解一定是正確的；l在求不出解時，需再次調(diào)用算法進行計算，直到獲得解為止；對于此類算法，主要是分析算法的時間復雜度的期望值，以及調(diào)用一次產(chǎn)生失?。ㄇ蟛怀鼋猓┑母怕省onte Carlo算法：l通常不能保證計算出來的結(jié)果總是正確的，一般只能斷定所給解的正確性不小于p（ 1/2p1）；l通過算法的反復執(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)點：對于某一給定的問題，隨機算法所需的時間與空間復雜性，往往比當前已知的、最好的確定性算法要好；到目前為止設(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方法，則可以采用隨機預處理的方法，使得輸入對象服從均勻分

7、布（或其他分布），然后再用確定性算法對其進行處理。所得效果在概率意義下與Sherwood型算法相同；Sherwood算法總能求得問題的一個解，且所求得的解是正確的；l當一個確定性算法在最壞情況和平均情況下的時間復雜度有較大差別時，可在確定性算法中引入隨機性將其改造為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)，當然有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,當n很大時，誤匹配的概率很?。籰設(shè)x¹y，如果取k個不同的小于2n2的素數(shù)來求Ip(x)和Ip(y)；l即k次試驗均有Ip(x)=Ip(y)但x¹y（誤匹配）的概率小于 1/nk；l當n較大、且重復了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時間復雜度分析：l計算Ip(Y)、Ip(X(1)及2m mod p的時間不超過O(m)次運算；Ip(X(j+1)的計算，只需用O(1)時間；l由于循環(huán)最多執(zhí)行n-m+1次，故這部分的時間復雜度為O(n)，于是，總的時間復雜性為O(m+n)；l當YX(j)，但Ip(Y)=Ip(X(j)時產(chǎn)生失?。籰失敗的概率Prfailure<1/n，即失敗的