隨機(jī)算法

1、RomizedRomizedAlgithmsAlgithms(隨機(jī)算法隨機(jī)算法)ProbabilisticProbabilisticAlgithmsAlgithms(概率算法概率算法)起源可以追溯到起源可以追溯到2020世紀(jì)世紀(jì)4040年代中葉。年代中葉。當(dāng)時當(dāng)時MonteMonteCarloCarlo在進(jìn)行在進(jìn)行數(shù)值計算數(shù)值計算時，提出通過統(tǒng)計模擬或抽樣得到問題的近似解，而且時，提出通過統(tǒng)計模擬或抽樣得到問題的近似解，而且出現(xiàn)錯誤的概

2、率隨著實驗出現(xiàn)錯誤的概率隨著實驗次數(shù)的增多而顯著地減少次數(shù)的增多而顯著地減少，即可以用時間，即可以用時間次數(shù)來換取求解正確性的提高。不過，次數(shù)來換取求解正確性的提高。不過，MonteMonteCarloCarlo方法很長時間沒有引入到非數(shù)值算法中來。方法很長時間沒有引入到非數(shù)值算法中來。7474年，年，MichaelMichaelRabinRabin（7676年TuringTuring獎獲得者獎獲得者哈佛教授哈佛教授以色列人）在瑞典講演

3、時指出：以色列人）在瑞典講演時指出：有些問題，如果不用隨有些問題，如果不用隨機(jī)化的方法而用確定性的算法，在可以忍受的時間內(nèi)得不到所需要的結(jié)果機(jī)化的方法而用確定性的算法，在可以忍受的時間內(nèi)得不到所需要的結(jié)果。e.g.e.g.PresburgePresburge算術(shù)系統(tǒng)（其中只有加法）中的算術(shù)系統(tǒng)（其中只有加法）中的計算程序，即使只有計算程序，即使只有100100個符號，用每秒個符號，用每秒1萬億次運算的機(jī)器萬億次運算的機(jī)器1萬億臺、進(jìn)行并

4、行計算也需做萬億臺、進(jìn)行并行計算也需做1萬億年。萬億年。但如果使用隨機(jī)性的概念，可以很快得出結(jié)果，而出錯率則微乎其微。但如果使用隨機(jī)性的概念，可以很快得出結(jié)果，而出錯率則微乎其微。7474年RabinRabin關(guān)于隨機(jī)化算法的思想還不太成熟，關(guān)于隨機(jī)化算法的思想還不太成熟，7676年RabinRabin設(shè)計了一個判定素數(shù)的隨機(jī)算法，該算法至今仍是隨機(jī)算法的一個典范。設(shè)計了一個判定素數(shù)的隨機(jī)算法，該算法至今仍是隨機(jī)算法的一個典范。隨機(jī)算法

5、在隨機(jī)算法在分布式計算、通信、信息檢索、計算幾何、密碼學(xué)分布式計算、通信、信息檢索、計算幾何、密碼學(xué)等許多領(lǐng)域都有著廣泛的應(yīng)用。等許多領(lǐng)域都有著廣泛的應(yīng)用。最著名的是在最著名的是在公開密鑰體系、公開密鑰體系、RSARSA算法算法方面的應(yīng)用。方面的應(yīng)用。用隨機(jī)化方法解決問題之例：用隨機(jī)化方法解決問題之例：設(shè)有一函數(shù)表達(dá)式設(shè)有一函數(shù)表達(dá)式f(xf(x1xx2…xn)，要判斷，要判斷f在某一區(qū)域在某一區(qū)域D中是否恒為中是否恒為0。如果。如果f

6、不能用數(shù)學(xué)方法進(jìn)行形式上的化簡不能用數(shù)學(xué)方法進(jìn)行形式上的化簡（這在工程中是經(jīng)常出現(xiàn)的）（這在工程中是經(jīng)常出現(xiàn)的），如何判斷就很麻煩。，如何判斷就很麻煩。如果我們隨機(jī)地產(chǎn)生一個如果我們隨機(jī)地產(chǎn)生一個n維的坐標(biāo)維的坐標(biāo)(r(r1，r2，…，…rn)?D，代入代入f得f(rf(r1，r2，…，…rn)≠0，則可斷定在區(qū)域則可斷定在區(qū)域D內(nèi)f不恒為不恒為0。如果如果f(rf(r1，r2，…，…rn)＝0，則有兩種可能：，則有兩種可能：1.1.在

7、區(qū)域在區(qū)域D內(nèi)f≡0；2.2.在區(qū)域在區(qū)域D內(nèi)f≠0，得到上述結(jié)果只是巧合。，得到上述結(jié)果只是巧合。如果我們對很多個隨機(jī)產(chǎn)生的坐標(biāo)進(jìn)行測試，如果我們對很多個隨機(jī)產(chǎn)生的坐標(biāo)進(jìn)行測試，結(jié)果次次均為結(jié)果次次均為0，則我們可以斷言：，則我們可以斷言：f≠0的概率是非常之小的。的概率是非常之小的。如上例所示，在隨機(jī)算法中，如上例所示，在隨機(jī)算法中，我們我們不要求算法對所有可能的輸入均正確計算不要求算法對所有可能的輸入均正確計算，只要求出現(xiàn)錯誤的可

8、能性小到可以忽略的程度只要求出現(xiàn)錯誤的可能性小到可以忽略的程度；另外我們另外我們也不要求對同一輸入算法每次執(zhí)行時給出相同的結(jié)果也不要求對同一輸入算法每次執(zhí)行時給出相同的結(jié)果。我們所關(guān)心的是我們所關(guān)心的是算法在執(zhí)行時，是否能夠產(chǎn)生真正隨機(jī)的結(jié)果算法在執(zhí)行時，是否能夠產(chǎn)生真正隨機(jī)的結(jié)果。有不少問題，目前只有效率很差的確定性求解算法，有不少問題，目前只有效率很差的確定性求解算法，但用隨機(jī)算法去求解，可以（很快地）獲得相當(dāng)可信的結(jié)果。但用隨機(jī)算

9、法去求解，可以（很快地）獲得相當(dāng)可信的結(jié)果。隨機(jī)算法通常分為兩大類：隨機(jī)算法通常分為兩大類：LasLasVegasVegas算法、算法、MonteMonteCarloCarlo算法。算法。LasLasVegasVegas算法總是給出正確的結(jié)果，算法總是給出正確的結(jié)果，但在少數(shù)應(yīng)用中，可能出現(xiàn)求不出解的情況但在少數(shù)應(yīng)用中，可能出現(xiàn)求不出解的情況。此時需再次調(diào)用算法進(jìn)行計算，直到獲得解為止。。此時需再次調(diào)用算法進(jìn)行計算，直到獲得解為止。對于

10、此類算法，主要是分析算法的時間復(fù)雜度的期望值，以及調(diào)用一次產(chǎn)生失?。ㄇ蟛怀鼋猓┑母怕省τ诖祟愃惴?，主要是分析算法的時間復(fù)雜度的期望值，以及調(diào)用一次產(chǎn)生失?。ㄇ蟛怀鼋猓┑母怕?。MontMontCarloCarlo算法通常不能保證計算出的結(jié)果總是正確算法通常不能保證計算出的結(jié)果總是正確，一般只能斷定所給解的正確性不小于一般只能斷定所給解的正確性不小于p（＜p＜1）。21通過反復(fù)執(zhí)行算法（即通過反復(fù)執(zhí)行算法（即以增大算法的執(zhí)行時間為代價以增

11、大算法的執(zhí)行時間為代價），能夠使發(fā)生錯誤的概率小到可以忽略的程度。由于每次執(zhí)行的算法是獨立的，能夠使發(fā)生錯誤的概率小到可以忽略的程度。由于每次執(zhí)行的算法是獨立的，故k次執(zhí)行均發(fā)生錯誤的概率小于次執(zhí)行均發(fā)生錯誤的概率小于(1p)(1p)k。對于對于判定問題（回答只能是“判定問題（回答只能是“YesYes”或“”或“NoNo”），MonteMonteCarloCarlo法又分為兩類：法又分為兩類：1.1.帶雙錯的帶雙錯的（twosidedt

12、wosidederrerr）:回答”回答”YesYes”或””或”NoNo”都有可能錯?！倍加锌赡苠e。2.2.帶單錯的帶單錯的（onesidedonesidederrerr）：）：只有一種回答可能錯。只有一種回答可能錯。LasLasVegasVegas算法可以看成是單錯概率為算法可以看成是單錯概率為0的特殊的的特殊的MonteMonteCarloCarlo算法。算法。當(dāng)前隨機(jī)產(chǎn)生的數(shù)是以前尚未選過的數(shù)的概率當(dāng)前隨機(jī)產(chǎn)生的數(shù)是以前尚未選過

13、的數(shù)的概率，則有，則有pj==。于是。于是qj=11pj=，即，即qj為：為：njn)1(??njn1??nj1?當(dāng)前隨機(jī)產(chǎn)生的數(shù)是以前選過的當(dāng)前隨機(jī)產(chǎn)生的數(shù)是以前選過的j1j1個數(shù)之一的概率個數(shù)之一的概率。設(shè)隨機(jī)變量設(shè)隨機(jī)變量Xj（1≤j≤m）表示：）表示：在j1j1個數(shù)已經(jīng)選出后，個數(shù)已經(jīng)選出后，再去找出第再去找出第j個數(shù)（與前個數(shù)（與前j1j1個數(shù)不同）時，個數(shù)不同）時，所需要產(chǎn)生的整數(shù)個數(shù)所需要產(chǎn)生的整數(shù)個數(shù)。則與前述的則與前述

14、的X類似，類似，Xj服從幾何分布：服從幾何分布：Pr[XPr[Xj=k]=p=k]=pjqjk1k1（k≥1q1qj=1p=1pj），于是有于是有E(XE(Xj)=)==。jp11??jnn設(shè)Y表示從表示從n個數(shù)中選出個數(shù)中選出m個數(shù)時（個數(shù)時（m≤），2n所需產(chǎn)生的所需產(chǎn)生的整數(shù)個數(shù)的總和整數(shù)個數(shù)的總和的隨機(jī)變量，的隨機(jī)變量，則有則有Y=XY=X1＋X2＋X3＋…＋＋…＋Xm。由于隨機(jī)變量的線性可加性有由于隨機(jī)變量的線性可加性有E(Y

15、)=E(Y)=E(XE(X1)＋E(XE(X2)＋…＋＋…＋E(XE(Xm)=)=????mjjnn11=n=n（）????njjn111?????nmjjn111=n=n（（（（）（））??????????Ann121111???????????????????Bmnmn121111???????在數(shù)學(xué)基礎(chǔ)部分曾證明用積分法可得在數(shù)學(xué)基礎(chǔ)部分曾證明用積分法可得≤≤＋1enlog)1log(???njj11enloglog故有故有A≤㏑

16、≤㏑n＋1，及，及B≥㏑（≥㏑（n－m＋1），于是于是E(Y)E(Y)≤n（㏑（㏑n1㏑（㏑（nm1nm1））≤n（㏑（㏑n1㏑（㏑（nmnm））≤n（㏑（㏑n1㏑（㏑（））（∵（∵m≤）2n2n=n（㏑（㏑n1㏑n㏑2）=n㏑2e2e≈1.69n1.69n由于算法的時間復(fù)雜度由于算法的時間復(fù)雜度T(n)T(n)正比于正比于算法產(chǎn)生整數(shù)的個數(shù)總和算法產(chǎn)生整數(shù)的個數(shù)總和Y，所以，所以，T(n)T(n)的數(shù)學(xué)期望值與的數(shù)學(xué)期望值與E(Y)E

17、(Y)成常數(shù)比，成常數(shù)比，即有即有T(n)=T(n)=?(n)(n)（數(shù)學(xué)期望值）（數(shù)學(xué)期望值）。找第找第k小元素的隨機(jī)算法小元素的隨機(jī)算法（LasLasVegasVegas算法）：算法）：在n個數(shù)中隨機(jī)的找一個數(shù)個數(shù)中隨機(jī)的找一個數(shù)A[i]=xA[i]=x然后將其余然后將其余n1n1個數(shù)與個數(shù)與x比較，分別放入三個數(shù)組中：比較，分別放入三個數(shù)組中：S1（元素均（元素均xx）S2（元素均（元素均=x=x）S3（元素均＞（元素均＞x）。若

18、|S|S1|≥k則調(diào)用則調(diào)用(kS(kS1)；若；若|S|S1|k但（但（|S|S1||S||S2|）≥）≥k，則第，則第k小元素就是小元素就是x；否則就有（否則就有（|S|S1||S||S2|）k，此時調(diào)用，此時調(diào)用(k|S(k|S1||S||S2|S|S3)。定理：定理：若以等概率方法在若以等概率方法在n個數(shù)中隨機(jī)取數(shù)，個數(shù)中隨機(jī)取數(shù)，則該算法用到的比較次數(shù)的期望值不超過則該算法用到的比較次數(shù)的期望值不超過4n4n。（假定（假定n個