第十九講 隨機(jī)算法

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

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

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

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

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

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

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

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

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

10、Y是否為X的子串？（即Y是否為X中的一段）。l可用KMP算法在O(m+n)時(shí)間內(nèi)獲得結(jié)果，但算法較為繁瑣。l考慮隨機(jī)算法（用brute-force 思想）；記X(j)=xjxj1xj+m-1（從X的第j位開始、長(zhǎng)度與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)）計(jì)算出來(lái)，故算法可以很快完成；1.隨機(jī)取一個(gè)小于M的素?cái)?shù)p，置j1；2.計(jì)算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)計(jì)算出Ip(X(j+1)；j增14. return 0; /X肯定沒(méi)有子串等于Y/l時(shí)間復(fù)雜度分析：l計(jì)算Ip(Y)、Ip(X(1)及2m mod p的時(shí)間不超過(guò)O(m)次運(yùn)算；Ip(X(j+1)的計(jì)算，只需用O(1)時(shí)間；l由于循環(huán)最多執(zhí)行n-m+1次，故這部分的時(shí)間復(fù)雜度為O(n)，于是，總的時(shí)間復(fù)雜性為O(m+n)；l當(dāng)YX(j)，但I(xiàn)p(Y)=Ip(X(j)時(shí)產(chǎn)生失敗；l失敗的概率Prfailure<1/n，即失敗的