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

隨機(jī)算法

RandomAlgorithm隨機(jī)數(shù)發(fā)生器隨機(jī)數(shù)在概率算法設(shè)計(jì)中扮演著十分重要的角色。在現(xiàn)實(shí)計(jì)算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù)，因此在概率算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，即偽隨機(jī)數(shù)。線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法。由線性同余法產(chǎn)生的隨機(jī)序列a0,a1,…,an滿足其中b>=0，c>=0，d<=m。d稱為該隨機(jī)序列的種子。如何選取該方法中的常數(shù)b、c和m直接關(guān)系到所產(chǎn)生的隨機(jī)序列的隨機(jī)性能。這是隨機(jī)性理論研究的內(nèi)容，已超出本書討論的范圍。從直觀上看，m應(yīng)取得充分大，因此可取m為機(jī)器大數(shù)，另外應(yīng)取gcd(m,b)=1，因此可取b為一素?cái)?shù)。圓周率計(jì)算rpublicstaticdoubledarts(intn){//用隨機(jī)投點(diǎn)法計(jì)算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的平行線，將一根長(zhǎng)度為s（s<d）的針任意擲在這個(gè)平面上，求此針與平行線中任一條相交的概率?！?)取一張白紙，在上面畫上許多條間距為d的平行線。2)取一根長(zhǎng)度為s（s<d）的針，隨機(jī)地向畫有平行直線的紙上擲n次，觀察針與直線相交的次數(shù)，記為m3)計(jì)算針與直線相交的概率p布豐本人證明了，這個(gè)概率是d一個(gè)直徑為d的圓圈，不管如何投擲，必定是有兩個(gè)交點(diǎn)。那么投擲n，共有2n個(gè)交點(diǎn)。把圓圈拉直，變成一條長(zhǎng)為πd的線段。顯然，這樣的線段扔下時(shí)與平行線相交的情形要比圓圈復(fù)雜些，可能有4個(gè)交點(diǎn)，3個(gè)交點(diǎn)，2個(gè)交點(diǎn)，1個(gè)交點(diǎn)，甚至于都不相交。由于圓圈和線段的長(zhǎng)度同為πd，根據(jù)機(jī)會(huì)均等的原理，當(dāng)它們均投擲n次(n是一較大的數(shù))，兩者與平行線組交點(diǎn)的總數(shù)期望值也是一樣的，即均為2n。長(zhǎng)度為s的線段，投擲n次后，交點(diǎn)的個(gè)數(shù)為記為m，那么：m/2n=s/πd布豐投針實(shí)驗(yàn)是第一個(gè)用幾何形式表達(dá)概率問題的例子，他首次使用隨機(jī)實(shí)驗(yàn)處理確定性數(shù)學(xué)問題，為概率論的發(fā)展起到一定的推動(dòng)作用。像投針實(shí)驗(yàn)一樣，用通過概率實(shí)驗(yàn)所求的概率來估計(jì)我們感興趣的一個(gè)量，這樣的方法稱為蒙特卡羅方法（MonteCarlomethod）。蒙特卡羅方法是在第二次世界大戰(zhàn)期間隨著計(jì)算機(jī)的誕生而興起和發(fā)展起來的。這種方法在應(yīng)用物理、原子能、固體物理、化學(xué)、生態(tài)學(xué)、社會(huì)學(xué)以及經(jīng)濟(jì)行為等領(lǐng)域中得到廣泛利用。蒙特·卡羅方法（MonteCarlomethod），也稱統(tǒng)計(jì)模擬方法，是二十世紀(jì)四十年代中期由于科學(xué)技術(shù)的發(fā)展和電子計(jì)算機(jī)的發(fā)明，而被提出的一種以概率統(tǒng)計(jì)理論為指導(dǎo)的一類非常重要的數(shù)值計(jì)算方法。是指使用隨機(jī)數(shù)（或更常見的偽隨機(jī)數(shù)）來解決很多計(jì)算問題的方法。蒙特·卡羅方法的名字來源于摩納哥的一個(gè)城市蒙地卡羅，該城市以賭博業(yè)聞名，而蒙特·卡羅方法正是以概率為基礎(chǔ)的方法。隨機(jī)非重復(fù)采樣問題設(shè)有n個(gè)樣本，要求從中隨機(jī)選出m個(gè)樣本(m<n/2)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)隨機(jī)算法來完成該任務(wù)，并分析該算法的時(shí)間復(fù)雜度。思路：將n個(gè)樣本存放于數(shù)組Sample[1…n]中。數(shù)組Result[1…m]存放選中的m個(gè)樣本。定義一個(gè)長(zhǎng)度為n的標(biāo)志數(shù)組Flag[1…n]。Flag[i]=true表示對(duì)應(yīng)位置的樣本已經(jīng)被選中；否則為未選中。隨機(jī)生成一個(gè)落在區(qū)間[1,n]的隨機(jī)數(shù)r。若Flag[r]為false，Sample[r]追加到數(shù)組Result中,并將Flag[r]置為true；若Flag[r]為true,則重新生成隨機(jī)數(shù)r，直到Flag[r]為false。重復(fù)此步驟，直到m個(gè)樣本選擇完成。輸入：樣本數(shù)組Sample[1…n],選擇樣本的個(gè)數(shù)m,且m<n輸出：選中的樣本Result[1..m]1.fori←1ton2.Flag[i]←false//boolean數(shù)組，表示對(duì)應(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……………時(shí)間復(fù)雜度分析很顯然，這是一個(gè)典型的迭代算法，因而可以使用計(jì)算迭代次數(shù)的技術(shù)來分析。觀察：然而每次運(yùn)行此算法，迭代次數(shù)都可能是不同的。引理1：在某個(gè)空間中拋擲硬幣，設(shè)正面朝上的概率是p，反面朝上的概率為q(q=1-p)。用隨機(jī)變量X表示“出現(xiàn)正面朝上”需要連續(xù)拋擲的次數(shù)，則隨機(jī)變量X的分布滿足幾何分布X的數(shù)學(xué)期望是

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

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

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

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

(n)+1.69n=

(n)

測(cè)試串的相等性

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

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

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

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

Ip(x)即作為x的指紋。因?yàn)镮p(x)<p，則Ip(x)可用一個(gè)不超過

logp

+1位的二進(jìn)制串來表示。因此，如果p不是很大，那么，指紋Ip(x)可以作為一個(gè)較短的串來發(fā)送，串長(zhǎng)度為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,則可能出錯(cuò)。出現(xiàn)錯(cuò)誤匹配情形是：x≠y，但I(xiàn)p(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,則會(huì)出現(xiàn)錯(cuò)誤匹配，即：x≠y,但I(xiàn)p(x)=3=Ip(y).下面我們先給出算法的框架，再分析出錯(cuò)的概率。算法：1．

從小于M的素?cái)?shù)集中隨機(jī)選擇一個(gè)p2．A將p和

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

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

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

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

。

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

log(M)

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