Chapter-8隨機(jī)算法.ppt

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