算法設(shè)計與分析：隨機算法

隨機算法

RandomAlgorithm隨機數(shù)發(fā)生器隨機數(shù)在概率算法設(shè)計中扮演著十分重要的角色。在現(xiàn)實計算機上無法產(chǎn)生真正的隨機數(shù)，因此在概率算法中使用的隨機數(shù)都是一定程度上隨機的，即偽隨機數(shù)。線性同余法是產(chǎn)生偽隨機數(shù)的最常用的方法。由線性同余法產(chǎn)生的隨機序列a0,a1,…,an滿足其中b>=0，c>=0，d<=m。d稱為該隨機序列的種子。如何選取該方法中的常數(shù)b、c和m直接關(guān)系到所產(chǎn)生的隨機序列的隨機性能。這是隨機性理論研究的內(nèi)容，已超出本書討論的范圍。從直觀上看，m應(yīng)取得充分大，因此可取m為機器大數(shù)，另外應(yīng)取gcd(m,b)=1，因此可取b為一素數(shù)。圓周率計算rpublicstaticdoubledarts(intn){//用隨機投點法計算pi值

intk=0;for(inti=1;i<=n;i++){doublex=dart.fRandom();doubley=dart.fRandom();if((x*x+y*y)<=1)k++;}return4*k/(double)n;}d18世紀(jì)，法國數(shù)學(xué)家布豐和勒可萊爾提出的“投針問題”，記載于布豐1777年出版的著作中：“在平面上畫有一組間距為d的平行線，將一根長度為s（s<d）的針任意擲在這個平面上，求此針與平行線中任一條相交的概率。”1)取一張白紙，在上面畫上許多條間距為d的平行線。2)取一根長度為s（s<d）的針，隨機地向畫有平行直線的紙上擲n次，觀察針與直線相交的次數(shù)，記為m3)計算針與直線相交的概率p布豐本人證明了，這個概率是d一個直徑為d的圓圈，不管如何投擲，必定是有兩個交點。那么投擲n，共有2n個交點。把圓圈拉直，變成一條長為πd的線段。顯然，這樣的線段扔下時與平行線相交的情形要比圓圈復(fù)雜些，可能有4個交點，3個交點，2個交點，1個交點，甚至于都不相交。由于圓圈和線段的長度同為πd，根據(jù)機會均等的原理，當(dāng)它們均投擲n次(n是一較大的數(shù))，兩者與平行線組交點的總數(shù)期望值也是一樣的，即均為2n。長度為s的線段，投擲n次后，交點的個數(shù)為記為m，那么：m/2n=s/πd布豐投針實驗是第一個用幾何形式表達概率問題的例子，他首次使用隨機實驗處理確定性數(shù)學(xué)問題，為概率論的發(fā)展起到一定的推動作用。像投針實驗一樣，用通過概率實驗所求的概率來估計我們感興趣的一個量，這樣的方法稱為蒙特卡羅方法（MonteCarlomethod）。蒙特卡羅方法是在第二次世界大戰(zhàn)期間隨著計算機的誕生而興起和發(fā)展起來的。這種方法在應(yīng)用物理、原子能、固體物理、化學(xué)、生態(tài)學(xué)、社會學(xué)以及經(jīng)濟行為等領(lǐng)域中得到廣泛利用。蒙特·卡羅方法（MonteCarlomethod），也稱統(tǒng)計模擬方法，是二十世紀(jì)四十年代中期由于科學(xué)技術(shù)的發(fā)展和電子計算機的發(fā)明，而被提出的一種以概率統(tǒng)計理論為指導(dǎo)的一類非常重要的數(shù)值計算方法。是指使用隨機數(shù)（或更常見的偽隨機數(shù)）來解決很多計算問題的方法。蒙特·卡羅方法的名字來源于摩納哥的一個城市蒙地卡羅，該城市以賭博業(yè)聞名，而蒙特·卡羅方法正是以概率為基礎(chǔ)的方法。隨機非重復(fù)采樣問題設(shè)有n個樣本，要求從中隨機選出m個樣本(m<n/2)。請設(shè)計一個隨機算法來完成該任務(wù)，并分析該算法的時間復(fù)雜度。思路：將n個樣本存放于數(shù)組Sample[1…n]中。數(shù)組Result[1…m]存放選中的m個樣本。定義一個長度為n的標(biāo)志數(shù)組Flag[1…n]。Flag[i]=true表示對應(yīng)位置的樣本已經(jīng)被選中；否則為未選中。隨機生成一個落在區(qū)間[1,n]的隨機數(shù)r。若Flag[r]為false，Sample[r]追加到數(shù)組Result中,并將Flag[r]置為true；若Flag[r]為true,則重新生成隨機數(shù)r，直到Flag[r]為false。重復(fù)此步驟，直到m個樣本選擇完成。輸入：樣本數(shù)組Sample[1…n],選擇樣本的個數(shù)m,且m<n輸出：選中的樣本Result[1..m]1.fori←1ton2.Flag[i]←false//boolean數(shù)組，表示對應(yīng)的樣本是否已被選中3.endfor4.k←05.whilek<m6.r←random(1,n)7.ifnotFlag[r]then8.k←k+19.Result[k]←Sample[r]10.Flag[r]←true11.endif12.endwhile13.returnResult[1…m]falseturetruefalseSampleFlagResult123…m…n……………時間復(fù)雜度分析很顯然，這是一個典型的迭代算法，因而可以使用計算迭代次數(shù)的技術(shù)來分析。觀察：然而每次運行此算法，迭代次數(shù)都可能是不同的。引理1：在某個空間中拋擲硬幣，設(shè)正面朝上的概率是p，反面朝上的概率為q(q=1-p)。用隨機變量X表示“出現(xiàn)正面朝上”需要連續(xù)拋擲的次數(shù)，則隨機變量X的分布滿足幾何分布X的數(shù)學(xué)期望是

E(X)的含義是：平均連續(xù)拋擲1/p次，會出現(xiàn)一次正面。

分析：假設(shè)已經(jīng)選中了k-1個樣本，當(dāng)前需要選擇第k個樣本。falseturetruefalseFlag123…m…n……“空位置個數(shù)”:n-(k-1)“全部位置個數(shù)”:n“隨機數(shù)r落在空位置的概率”:n-(k-1)/n用隨機變量Xk

表示“落在空位置”需要連續(xù)生成隨機數(shù)的次數(shù)(為選中第k個樣本算法需要的迭代次數(shù))。由引理可知：E(Xk)=n/(n-k+1)k-1個true用隨機變量Y表示為了從n個樣本中選出m個樣本而生成的總的隨機數(shù)個數(shù)(即算法總的迭代次數(shù))，根據(jù)數(shù)學(xué)期望的線性性質(zhì)，我們有E(Y)=E(X1)+E(X2)+…+E(Xm)由于：則有：算法的期望運行時間T(n)主要有兩部分組成：1)將boolean數(shù)組S[1…n]置為false耗時

(n)，2)產(chǎn)生隨機數(shù)r←random(1,n)的期望運行時間E(Y)≈1.69n；因此，期望運行時間T(n)≈

(n)+1.69n=

(n)

測試串的相等性

通信問題：發(fā)射端A發(fā)送信號x（x一般為很長的二進制串），接收端B收到信號y，要確定是否x=y。

xyAB1.AsendxtoB2.Acomparexwithy3.BsendresulttoA目標(biāo)：降低通信量，以減少對通信資源的占用。xyAB1.發(fā)送x的指紋及生成方法2.利用同樣的方法生成y的指紋，并和x的指紋比對：如果指紋不相同，認(rèn)為x≠y；否則，認(rèn)為x=y。

3.回傳比對結(jié)果生成x的指紋指紋庫(B地)嫌疑人(A地)生成指紋

對于一個n位(bit)的二進制串x，I(x)為該二進制串所表示的一個整數(shù)。一種生成指紋的方法是：選擇一個素數(shù)p，令I(lǐng)p(x)=I(x)(modp)

Ip(x)即作為x的指紋。因為Ip(x)<p，則Ip(x)可用一個不超過

logp

+1位的二進制串來表示。因此，如果p不是很大，那么，指紋Ip(x)可以作為一個較短的串來發(fā)送，串長度為O(logp)。例如：x=(101011)2=(43)10,取p=(101)2=(5)10,則I(x)(modp)=43(mod5)=3=(11)2,僅需2比特.分析上述算法如果給出x≠y，肯定正確;如果給出x=y,則可能出錯。出現(xiàn)錯誤匹配情形是：x≠y，但Ip(x)=Ip(y)

x≠y，p整除I(x)?I(y)

例：x=(101011)2=(43)10,y=(110101)2=(53)10。若取p=(101)2=(5)10,則會出現(xiàn)錯誤匹配，即：x≠y,但Ip(x)=3=Ip(y).下面我們先給出算法的框架，再分析出錯的概率。算法：1．

從小于M的素數(shù)集中隨機選擇一個p2．A將p和

Ip(x)發(fā)送給B3．B檢查是否Ip(x)=Ip(y)，從而確定x是否和y相等。當(dāng)算法報告x=y時，可能會出錯。是否會出錯取決于所選擇的素數(shù)p。因此，該算法的出錯概率為：用π(n)表示小于整數(shù)n的不同素數(shù)的個數(shù)。那么π(n)漸趨近于n/ln(n)。如果整數(shù)k<2n，那么能夠整除k的素數(shù)的個數(shù)小于π(n)。

由于，x,y均為n位二進制串，所以：

0<I(x),I(y)<2n，-2n<I(x)-I(y)<2n.

則由結(jié)論2可知，整除I(x)-I(y)的素數(shù)個數(shù)小于π(n)

。

若取M=2n2，則：連續(xù)執(zhí)行k次，則出錯概率可以降低為：例子：傳輸一個百萬位的串即n=1,000,000，取M=2n2=2×1012，傳輸素數(shù)p至多需

log(M)

+1=41位，傳輸指紋也至多41位，共82位。驗證1次發(fā)生假匹配的概率為1/1,000,000，重復(fù)驗證5次，假匹配概率可減小到(10-6)5=10-30.例：x=(101011)2=(43)10,y=(110101)2=(53)10,取p=(101)2=(5)10,Ip(x)=3=Ip(y)，出現(xiàn)假匹配；再取p=3，Ip(x)=1≠Ip(y)=2，驗證不通過；模式匹配問題問題描述：給一個字模式串X=x1x2…xn，模式串Y=y1y2…ym，其中m<n，問：模式串Y是否在模式串X中出現(xiàn)？不失一般性，假設(shè)模式串定義在字符集{0,1}上。最直觀的方法：沿模式串X滑動Y，逐個比較子模式串X(j)=xj…xj+m-1和Y。時間復(fù)雜度：最壞情況下為O(mn)，例如：X=′000000000000000000000000000000000000000001′Y=′000001′隨機算法思想：同樣沿著模式串X滑動Y，但不是直接將模式串Y與每個子模式串X(j)=xj…xj+m-1進行比較；而是借鑒指紋匹配的思想，將Y的指紋與子模式串X(j)的指紋比較，從而判斷Y是否與X(j)相同。直接使用上述方法時間復(fù)雜性不能有效降低，因為指紋計算同樣要耗費時間。然而，分析可以發(fā)現(xiàn)：新串X(j+1)的指紋可以很方便地從X(j)的指紋計算出來，即：Ip(X(j+1))=(2Ip(X(j))