隨機算法

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

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

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

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

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

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

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

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

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

10、此類算法，主要是分析算法的時間復雜度的期望值，以及調用一次產生失敗（求不出解）的概率。對于此類算法，主要是分析算法的時間復雜度的期望值，以及調用一次產生失?。ㄇ蟛怀鼋猓┑母怕?。MontMontCarloCarlo算法通常不能保證計算出的結果總是正確算法通常不能保證計算出的結果總是正確，一般只能斷定所給解的正確性不小于一般只能斷定所給解的正確性不小于p（＜p＜1）。21通過反復執(zhí)行算法（即通過反復執(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算法。算法。當前隨機產生的數是以前尚未選過的數的概率當前隨機產生的數是以前尚未選過

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

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

15、)=E(Y)=E(XE(X1)＋E(XE(X2)＋…＋＋…＋E(XE(Xm)=)=????mjjnn11=n=n（）????njjn111?????nmjjn111=n=n（（（（）（））??????????Ann121111???????????????????Bmnmn121111???????在數學基礎部分曾證明用積分法可得在數學基礎部分曾證明用積分法可得≤≤＋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由于算法的時間復雜度由于算法的時間復雜度T(n)T(n)正比于正比于算法產生整數的個數總和算法產生整數的個數總和Y，所以，所以，T(n)T(n)的數學期望值與的數學期望值與E(Y)E

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

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