Chapter-8隨機算法.ppt

南京理工大學(xué),隨機算法 Random Algorithm,南京理工大學(xué),隨機算法的設(shè)計思想,允許結(jié)果以較小的概率出現(xiàn)錯誤，以此為代價，獲得算法運行時間的大幅度減少。如果一個問題沒有有效的確定性算法可以在一個合理的時間內(nèi)給出解答，但是該算法能接受小概率的錯誤，那么采用隨機算法就可以快速地找到這個問題的解。 例如：判斷表達式f(x1, x2, xn)是否恒等于0，若用解析的方式來判斷非常費時。隨機算法首先隨機生成一個n元向量(r1, r2, rn)，若f(r1, r2, rn) 0，則表達式f0顯然不成立； 若f(r1, r2, rn) =0，或者是f0，或者是選擇的(r1, r2, rn)比較湊巧，那么多試驗幾次，若繼續(xù)得到f(r1, r2, rn) =0的結(jié)論，就可以得出f(r1, r2, rn) 0的結(jié)論，并且試驗的次數(shù)越多，出錯的概率越小。,南京理工大學(xué),隨機數(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ù)。,南京理工大學(xué),圓周率計算,r,public static double darts(int n) / 用隨機投點法計算pi值 int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if (x*x+y*y)=1) k+; return 4*k/(double)n; ,南京理工大學(xué),d,18世紀，法國數(shù)學(xué)家布豐和勒可萊爾提出的“投針問題”，記載于布豐1777年出版的 著作中：“在平面上畫有一組間距為d的平行線，將一根長度為s（sd）的針任意擲在 這個平面上，求此針與平行線中任一條相交的概率。” 1) 取一張白紙，在上面畫上許多條間距為d的平行線。 2) 取一根長度為s（sd） 的針，隨機地向畫有平行直線 的紙上擲n次，觀察針與直線相交的次數(shù)，記為m 3) 計算針與直線相交的概率p 布豐本人證明了，這個概率是,南京理工大學(xué),d,一個直徑為d的圓圈，不管如何投擲，必定是有兩個交點。那么投擲n，共有2n個交點。 把圓圈拉直，變成一條長為d的線段。顯然，這樣的線段扔下時與平行線相交的情形要比圓圈復(fù)雜些，可能有4個交點，3個交點，2個交點，1個交點，甚至于都不相交。由于圓圈和線段的長度同為d，根據(jù)機會均等的原理，當它們均投擲n次(n是一較大的數(shù)) ，兩者與平行線組交點的總數(shù)期望值也是一樣的，即均為2n。 長度為s的線段，投擲n次后，交點的個數(shù)為記為m，那么： 投針實驗 s : n : m 圓圈拉直實驗 d : n : 2n 因此有： m/2n = s/d,南京理工大學(xué),蒙特卡羅方法,布豐投針實驗是第一個用幾何形式表達概率問題的例子，他首次使用隨機實驗處理確定性數(shù)學(xué)問題，為概率論的發(fā)展起到一定的推動作用。 像投針實驗一樣，用通過概率實驗所求的概率來估計我們感興趣的一個量，這樣的方法稱為蒙特卡羅方法（Monte Carlo method）。蒙特卡羅方法是在第二次世界大戰(zhàn)期間隨著計算機的誕生而興起和發(fā)展起來的。這種方法在應(yīng)用物理、原子能、固體物理、化學(xué)、生態(tài)學(xué)、社會學(xué)以及經(jīng)濟行為等領(lǐng)域中得到廣泛利用。 蒙特卡羅方法（Monte Carlo method），也稱統(tǒng)計模擬方法，是二十世紀四十年代中期由于科學(xué)技術(shù)的發(fā)展和電子計算機的發(fā)明，而被提出的一種以概率統(tǒng)計理論為指導(dǎo)的一類非常重要的數(shù)值計算方法。是指使用隨機數(shù)（或更常見的偽隨機數(shù)）來解決很多計算問題的方法。蒙特卡羅方法的名字來源于摩納哥的一個城市蒙地卡羅，該城市以賭博業(yè)聞名，而蒙特卡羅方法正是以概率為基礎(chǔ)的方法。,南京理工大學(xué),隨機非重復(fù)采樣問題,設(shè)有n 個樣本，要求從中隨機選出m 個樣本(mn/2)。請設(shè)計一個隨機算法來完成該任務(wù)，并分析該算法的時間復(fù)雜度。 思路： 將n個樣本存放于數(shù)組Sample1n中。數(shù)組Result1m存放選中的m個樣本。 定義一個長度為n的標志數(shù)組Flag1n。Flagi=true表示對應(yīng)位置的樣本已經(jīng)被選中；否則為未選中。 隨機生成一個落在區(qū)間1,n的隨機數(shù)r。若Flagr為false，Sampler追加到數(shù)組Result中,并將Flagr置為true；若Flagr為true,則重新生成隨機數(shù)r，直到Flagr為false。重復(fù)此步驟，直到m個樣本選擇完成。,南京理工大學(xué),輸入：樣本數(shù)組Sample1n, 選擇樣本的個數(shù)m, 且mn 輸出：選中的樣本Result1m 1.for i1 to n 2. Flagi false /boolean數(shù)組，表示對應(yīng)的樣本是否已被選中 3. end for 4. k0 5. while km 6. rrandom(1,n) 7. if not Flagr then 8. kk+1 9. Resultk Sampler 10. Flagr true 11. end if 12.end while 13.return Result1m,Sample,Flag,Result,1 2 3 m n,南京理工大學(xué),時間復(fù)雜度分析,很顯然，這是一個典型的迭代算法，因而可以使用計算迭代次數(shù)的技術(shù)來分析。 觀察：然而每次運行此算法，迭代次數(shù)都可能是不同的。,南京理工大學(xué),引理1：在某個空間中拋擲硬幣，設(shè)正面朝上的概率是p，反面朝上的概率為q(q=1-p)。用隨機變量X表示“第一次出現(xiàn)正面朝上”需要連續(xù)拋擲的次數(shù)，則隨機變量X的分布滿足幾何分布,X的數(shù)學(xué)期望是,E(X)的含義是：平均連續(xù)拋擲1/p次，會出現(xiàn)一次正面。,南京理工大學(xué),引理2：設(shè)隨機數(shù)r在1,n內(nèi)滿足均勻分布，則當已經(jīng)選定k-1個數(shù)時，隨機函數(shù)一次就生成一個未被選定的整數(shù)的概率pk (即產(chǎn)生一個有效的隨機數(shù)的概率pk)為 (n-k+1)/n,Flag,1 2 3 m n,“空位置個數(shù)”: n-(k-1),“全部位置個數(shù)”: n,“隨機數(shù)r落在空位置的概率”: n-(k-1) /n,k-1個true,南京理工大學(xué),南京理工大學(xué),用隨機變量Y表示為了從n個樣本中選出m個樣本而生成的總的隨機數(shù)個數(shù)(即算法總的迭代次數(shù))，根據(jù)數(shù)學(xué)期望的線性性質(zhì)，我們有 E(Y) = E(X1)+ E(X2)+ E(Xm),南京理工大學(xué),由于：,則有：,算法的期望運行時間T(n)主要有兩部分組成：1)將boolean數(shù)組S1n置為false耗時(n)，2)產(chǎn)生隨機數(shù)rrandom(1,n)的期望運行時間E(Y)1.69n；因此，期望運行時間 T(n) (n)+ 1.69n = (n),南京理工大學(xué),測試串的相等性,通信問題：發(fā)射端A發(fā)送信號x（x一般為很長的二進制串），接收端B收到信號y，要確定是否x = y。,x,y,A,B,1. A send x to B,2. A compare x with y,3. B send result to A,目標：降低通信量，以減少對通信資源的占用。,南京理工大學(xué),x,y,A,B,1. 發(fā)送x的指紋及生成方法,2. 利用同樣的方法生成 y的指紋，并和x的指紋 比對：如果指紋不相同， 認為x y；否則，認為 x = y。,3. 回傳比對結(jié)果,生成x的指紋,指紋庫 (B地),嫌疑人 (A地),南京理工大學(xué),生成指紋,對于一個n位(bit)的二進制串x，I(x)為該二進制串所表示的一個整數(shù)。一種生成指紋的方法是：選擇一個素數(shù)p，令 Ip(x) = I(x) (mod p) Ip(x)即作為x的指紋。 因為Ip(x)p，則Ip(x)可用一個不超過logp+1位的二進制串來表示。因此，如果p 不是很大，那么，指紋Ip(x)可以作為一個較短的串來發(fā)送，串長度為O(log p)。 例如：x=(101011)2=(43)10, 取p=(101)2=(5)10, 則I(x) (mod p) = 43(mod 5)=3=(11)2, 僅需2比特.,南京理工大學(xué),分析,上述算法如果給出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).,南京理工大學(xué),下面我們先給出算法的框架，再分析出錯的概率。 算法： 1 從小于M 的素數(shù)集中隨機選擇一個p 2 A 將p 和 Ip(x)發(fā)送給B 3 B 檢查是否Ip(x) = Ip(y)，從而確定x 是否和y 相等。,當算法報告x=y時，可能會出錯。是否會出錯取決于所選擇的素數(shù)p。因此，該算法的出錯概率為：,南京理工大學(xué),用(n)表示小于整數(shù)n 的不同素數(shù)的個數(shù)。那么(n)漸趨近于n/ln(n)。 如果整數(shù)k 2n，那么能夠整除k 的素數(shù)的個數(shù)小于(n)。,由于，x, y均為n位二進制串，所以： 0I(x),I(y)2n，-2n I(x)-I(y) 2n. 則由結(jié)論2可知，整除I(x)-I(y)的素數(shù)個數(shù)小于(n) 。,若取M=2n2，則：,南京理工大學(xué),連續(xù)執(zhí)行k次，則出錯概率可以降低為：,例子：傳輸一個百萬位的串即n=1,000,000，取M=2n2=21012，傳輸素數(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)=1Ip(y)=2，驗證不通過；,南京理工大學(xué),模式匹配問題,問題描述：給一個字模式串X=x1x2xn，模式串Y=y1y2ym，其中mn，問：模式串Y是否在模式串X中出現(xiàn)？不失一般性，假設(shè)模式串定義在字符集0,1上。 最直觀的方法：沿模式串X滑動Y，逐個比較子模式串X(j)=xjxj+m-1和Y。時間復(fù)雜度：最壞情況下為O(mn)，例如： X=000000000000000000000000000000000000000001 Y=000001,南京理工大學(xué),隨機算法,思想：同樣沿著模式串X滑動Y，但不是直接將模式串Y與每個子模式串X(j)=xjxj+m-1進行比較；而是借鑒指紋匹配的思想，將Y的指紋與子模式串X(j)的指紋比較，從而判斷Y是否與X(j)相同。 直接使用上述方法時間復(fù)雜性不能有效降低，因為指紋計算同樣要耗費時間。 然而，分析可以發(fā)現(xiàn)：新串X(j+1)的指紋可以很方便地從X(j)的指紋計算出來，即： Ip(X(j+1)=(2Ip(X(j) 2mxj + xj+m) (mod p) 為何有上述結(jié)論？,南京理工大學(xué),2(2):,(1),(2),(3),(3) - (1):,南京理工大學(xué),輸入：模式串X，長度為n，模式串Y，長度為m 輸出：若Y在X中出現(xiàn)，則返回Y在X中的第1個位置，否則返回-1 1. 從小于M的素數(shù)集中隨機選擇一個素數(shù)p 2. j1 3. 計算Wp=2m(mod p), Ip(Y) 和 Ip(X1) /O(m)+O(m)+O(m) 4. while jn-m+1 /Xj = xjxj+m-1, 須有j+m-1 n，即jn-m+1 5. if Ip(Xj) = Ip(Y) then return j /(可能)找到了匹配子串, O(logp) 6. Ip(Xj+1) (2Ip(Xj) - xjWp + xj+m) /每步O(1)時間，共O(n) 7. jj+1 8. end while 9. return -1 /Y肯定不在X中(若在，已由第5步返回j值),時間復(fù)雜度分析：O(m) + O(n) + O(logp) = O(m+n),南京理工大學(xué),南京理工大學(xué),蒙特卡羅方法小結(jié),蒙特卡洛型算法在一般情況下可以保證：對于問題的所有實例，都以高概率給出正確解，但是通常無法判斷一個解是否正確。 蒙特卡洛型隨機算法的特點是：總是給出解，但偶爾解是錯的，不知道一個解是對是錯。 然而，可以多次運行原算法，設(shè)法使得每次運行時的隨機選擇都相對獨立，則可以使非正確解的概率可以減小到任意小。,南京理工大學(xué),拉斯維加斯(Las Vegas)型隨機算法,拉斯維加斯算法特點是“或者給出正確解”、“或者無解”。該類型算法不時做出可導(dǎo)致算法陷入僵局的選擇，并且算法能夠檢測是否陷入僵局，如果是，算法承認失敗。但是，只要這種行為出現(xiàn)的概率不占多數(shù)，當出現(xiàn)失敗時，只要在相同的輸入實例上再次運行隨機算法，就又有成功的可能。 拉斯維加斯算法中的隨機性選擇能夠引導(dǎo)算法快速求解問題，顯著地改進算法的時間復(fù)雜性，甚至對某些迄今為止找不到有效算法的問題，也能找到滿意的解。,南京理工大學(xué),高斯8皇后問題,南京理工大學(xué),1. for i1 to 8 2. xi 0 3. end for 4. count0 /試探次數(shù) 5. for i1 to 8 6. j random(1,8) 7. count count+1 8. if皇后i在位置j不沖突 then 9. xi j; count0; ii+1; 轉(zhuǎn)步驟5 10. else if count=8 then output “failure” 11. else 轉(zhuǎn)步驟6 /重新放置皇后 12. end if 13. end for 14. return x18,南京理工大學(xué),反復(fù)調(diào)用Las Vegas型8皇后問題的隨機算法，直到得到問題的一個解。 將隨機性算法與回溯法相結(jié)合，會獲得更好的效果。可在棋盤上若干行隨機放置相容的皇后，然后在其他行用回溯法繼續(xù)放置，直到找到一個解或宣布算法失敗。 特點：隨機放置的皇后越多，回溯法搜索所需時間越少，但失敗的概率越大。,南京理工大學(xué),將串匹配問題的Monte Carlo算法轉(zhuǎn)換為Las Vegas算法,Las Vegas算法特點：要么找到正確解，要么算法失敗。 策略：只要產(chǎn)生匹配，就測試模式串Y與子串Xj是否相等，以確保找到正確解。,南京理工大學(xué),Las Vegas算法時間復(fù)雜度,O(n+m) (1-1/n) + O(mn)(1/n) = O(n+m) 其中： 1-1/n為Monte Carlo算法成功的概率， 1/n為調(diào)用Las Veg