[學(xué)習(xí)]算法設(shè)計(jì)與分析ch8隨機(jī)算法

1、第八章 Randomized Algorithms,8.1 Introduction to Randomized Algorithms,什么是隨機(jī)算法隨機(jī)算法是一種使用概率和統(tǒng)計(jì)方法在其執(zhí)行過程中對(duì)于下一計(jì)算步驟作出隨機(jī)選擇的算法隨機(jī)算法的優(yōu)越性對(duì)于有些問題: 算法簡(jiǎn)單對(duì)于有些問題: 時(shí)間復(fù)雜性低對(duì)于有些問題: 同時(shí)兼有簡(jiǎn)單和時(shí)間復(fù)雜性低隨機(jī)算法的隨機(jī)性對(duì)于同一實(shí)例的多次執(zhí)行, 效果可能完全不同時(shí)間復(fù)雜性的一個(gè)隨

2、機(jī)變量解的正確性和準(zhǔn)確性也是隨機(jī)的,隨機(jī)算法的基本概念,隨機(jī)算法的分類,隨機(jī)數(shù)值算法主要用于數(shù)值問題求解算法的輸出往往是近似解近似解的精確度與算法執(zhí)行時(shí)間成正比Monte Carlo算法主要用于求解需要準(zhǔn)確解的問題算法可能給出錯(cuò)誤解獲得精確解概率與算法執(zhí)行時(shí)間成正比,Las Vegas算法一旦找到一個(gè)解, 該解一定是正確的找到解的概率與算法執(zhí)行時(shí)間成正比增加對(duì)問題反復(fù)求解次數(shù), 可是求解無效的概率任意小Sherw

3、ood算法一定能夠求得一個(gè)正確解確定算法的最壞與平均復(fù)雜性差別大時(shí), 加入隨機(jī)性, 即得到Sherwood算法消除最壞行為與特定實(shí)例的聯(lián)系,隨機(jī)算法分析的特征僅依賴于隨機(jī)選擇, 不依賴于輸入的分布確定算法的平均復(fù)雜性分析: 依賴于輸入的分布對(duì)于每個(gè)輸入都要考慮算法的概率統(tǒng)計(jì)性能隨機(jī)算法分析的目標(biāo)平均時(shí)間復(fù)雜性: 時(shí)間復(fù)雜性隨機(jī)變量的均值獲得正確解的概率獲得優(yōu)化解的概率解的精

4、確度估計(jì),隨機(jī)算法的性能分析,8.2 Randomized Numerical Algorithms,計(jì)算?值,數(shù)學(xué)基礎(chǔ)設(shè)有一個(gè)半徑為r的園及其外切四邊形,向正方形隨機(jī)地投擲n個(gè)點(diǎn), 設(shè)k個(gè)點(diǎn)落入園內(nèi)投擲點(diǎn)落入園內(nèi)的概率為 (?r2)/(4r2)= ?/4.用k/n逼近?/4, 即k/n??/4, 于是??(4k)/n.我們可以令r=1用投擲n個(gè)點(diǎn)的方法計(jì)算?,算法K=0;For i=1 To n

5、隨機(jī)地產(chǎn)生四邊形中的一點(diǎn)(x, y); If x2+y2?1 Then k=k+1;EndforReturn (4k)/n時(shí)間復(fù)雜性=O(n)不是輸入的大小, 而是隨機(jī)樣本的大小解的精確度隨著隨機(jī)樣本大小n增加而增加,計(jì)算定積分,問題 計(jì)算積分,數(shù)學(xué)基礎(chǔ)令f(x)是區(qū)間[a, b]上的一組獨(dú)立、同分布的隨機(jī)變量{?i}的任意密度函數(shù)令g*(x)=g(x)/f(x), 則{g*(?)}

6、是密度為f(x)的隨機(jī)變量集合, 而且,由強(qiáng)大數(shù)定律,我們可以用 來近似計(jì)算I,,令 f(x)=1/(b-a) a ? x ? b索求積分可以由如下I’來近似計(jì)算I,算法I=0;For i=1 To n 隨機(jī)產(chǎn)生[a, b]中點(diǎn)x; I=I+g(x);EndforReturn (b-a)*I/n時(shí)間復(fù)雜性=O(n)不是輸入的大小,

7、而是隨機(jī)樣本的大小解的精確度隨著隨機(jī)樣本大小n增加而增加,8.3 Randomized Selection Algorithms,問題的定義隨機(jī)算法算法的性能分析,問題的定義,輸入: S={x1, x2, …, xn}， 整數(shù)k，1?k?n. 輸出: S中第k個(gè)最小元素.,,記號(hào) Rank(Q, t) =集合Q中的元素t的rank (第k小元

8、素的rank是k) min(Q, i) = 集合Q中第i個(gè)最小元素.,隨機(jī)算法,,基本思想 從S中隨機(jī)地抽取n3/4個(gè)樣本存入R, 排序R S中第k最小元素可能成為R中x=kn3/4/n最小元素 為了解決誤差問題, 我們考察區(qū)間[x-n1/2, x+n1/2],把S中屬于[L, H]數(shù)據(jù)存入P 在P中查找min(S, k),,,LAZYSELECT(S, k) R=獨(dú)立、均勻、可放回地從S隨機(jī)選取的n3/4元素;

9、在O(nlogn)時(shí)間內(nèi)排序R; x=(k/n)n3/4; /* (k/n)n3/4=kn-1/4 */ l=max{ , 0}; h= min{ , n3/4}; L=min(R, l); H=min(R, h); Lp=Rank(S,L), Hp=Rank(S,H); /*L和H與S元素比較*/ P={y?S | L?y?H}; If min(

10、S, k)?P and |P|?4n3/4+1 /* max(S, k)?P可由Lp?k?Hp確定 */ 9. Then 排序P, min(S, k)=min(P, (k-Lp)), 算法結(jié)束; 10. ELSE goto 1.,數(shù)學(xué)基礎(chǔ)數(shù)學(xué)期望離散隨機(jī)變量X的數(shù)學(xué)期望E[X]=?i i?P(X=i)若f(x)是定義在整數(shù)集上的實(shí)數(shù)值函數(shù), 則

11、 E[f(X)]=?i f(i)?P(X=i).Markov不等式P( Y ? t ) ? E[Y]/t, 其中Y為非負(fù)隨機(jī)變量, t > 0.,算法的性能分析,,方差的性質(zhì)與Chebyshev不等式方差?x2 =E[(X-?x)2], ?x為隨機(jī)變量X的數(shù)學(xué)期望?x稱為標(biāo)準(zhǔn)差Chebyshev不等式: P(|X-?x|>t?x) ? 1/t2如果隨機(jī)變量X滿足P(X=1)=p, P(X=0)=1-p, 則

12、 ?x2 = p(1-p).若X=?1?i?n Xi , ?x2=?1?i?n ?xi2, Xi是獨(dú)立隨機(jī)變量若隨機(jī)變量Xi滿足P(Xi=1)=p, P(Xi=0)=1-p, 則 ?x2 = np(1-p).,算法的性能分析定理. 算法執(zhí)行1-9步一遍就可求出min(S,k)的概率是1-O(n-1/4),

13、 即算法需要2n+O(nlogn)次比較就可求出min(S,k)的概率 是1-O(n-1/4).證明. 若算法執(zhí)行1-9一遍可求出min(S, k), 則第6步需2n次比較, 其他步需O(nlogn)次比較, 總需2n+O(nlogn)次比較. 往證算法執(zhí)行1-9一遍可求出min(S, k)的概率是1-O(n-1/4). 算法執(zhí)行1-9一遍可求出m

14、in(S, k)的條件是: (1). min(S, k)在L和H之間即P包含min(S, k), (2). |P|?4n3/4+1. 我們首先來計(jì)算上述兩個(gè)條件失敗的概率.,,,,A. 計(jì)算條件(1)不成立的概率條件(1)不成立當(dāng)且僅當(dāng)L>min(S, k)或H<min(S, k).令Xi=1如果第i個(gè)隨機(jī)樣本?min(S, k), 否則Xi=0.于是,

15、 P(Xi=1)=k/n, P(Xi=0)=1-k/n.令 X=?1 ?i ? n3/4 Xi 是R中小于等于min(S, k) 的樣本數(shù). 我們有 X的數(shù)學(xué)期望?x=n3/4k/n=kn-1/4, X的方差?x2= n3/4(k/n)(1-k/n) ? n3/4/4, X的標(biāo)準(zhǔn)差?x ? n3/8/2.,如果L>min(S,

16、k), Xmin(S, k))=P(Xn1/2), P(Hh)+P(X=h)=P(|X-?x|?n1/2)+(n3/4+1)-1.應(yīng)用Chebyshev不等式, 又由2n1/8 ?x ?n1/2, 我們有 P(|X-?x|>n1/2)?P(|X-?x|>2n1/8?x)?1/(2n1/8)2=O(n-1/4). 于是 P(L>min(S, k))=P(H<min(S, k))=O(n-1/4).,,B.

17、計(jì)算P包含min(S, k)但|P|?4n3/4+1不成立的概率令kl=max{0, k-2n3/4}, kh=min{k+2n3/4, n}. “P包含min(S, k)但|P|?4n3/4+1不成立”發(fā)生當(dāng)且僅當(dāng) Lmin(S, kh).類似與上面A中的分析， P(Lmin(S, kh))=O(n-1/4).由A和B, “算法執(zhí)行1-9一遍就可以求出min(S, k)”不成立的概率是O(n-1/4).即，“算法執(zhí)行1

18、-9一遍就可以求出min(S, k)”的概率是1-O(n-1/4).,8.4 Randomized Algorithm to Test Whether Number is Prime,問題的定義隨機(jī)算法設(shè)計(jì)算法的性能分析,輸入一個(gè)正整數(shù)N輸出N是否素?cái)?shù),問題的定義,基本思想對(duì)N進(jìn)行m次測(cè)試如果有一次測(cè)試成功, 則回答N是合數(shù)如果m次測(cè)試均失敗, 則回答N是素?cái)?shù)回答N是合數(shù)時(shí), 答案百分之百

19、正確回答N是素?cái)?shù)時(shí), 答案正確的概率是1-2-m,隨機(jī)算法的設(shè)計(jì),,隨機(jī)算法隨機(jī)地選擇m個(gè)數(shù){b1, b2, …, bm}, 滿足 1? b1, b2, …, bm ? N;For i=1 To m Do If W(bi)成立 Then Return (N是合數(shù));Return (N是素?cái)?shù))W(bi)定義如下:(1) biN-1 ? 1 m

20、od N, 或(2) ?j[(N-1)/2j=k是整數(shù), 1 < (bik與N的最大公因子) < N ].,例1. 給定N=12. 選擇測(cè)試數(shù)集{2, 3, 7} 測(cè)試 2: 212-1 = 2048 ? 1 mod 12, W(2)成立. N是合數(shù).,例2. 給定N=11,選擇測(cè)試數(shù)集{2, 5, 7} 測(cè)試 2: 211-1 = 1024 = 1

21、 mod 11, 令j=1, k=(N-1)/2j=10/2=5, gcd(2k-1, N)=gcd(31, 11)=1, j=1是唯一使(N-1)/2j為整數(shù)的j, W(2)不成立.,測(cè)試 5: 511-1 = 9765625 = 1

22、mod 11, 令j=1, k=(N-1)/2j=10/2=5, gcd(5k-1, N)=gcd(3124, 11)=11=N, j=1是唯一使(N-1)/2j為整數(shù)的j, W(5)不成立.,測(cè)試 7: 711-1 = 282475249 = 1 mod 11,

23、 令j=1, k=(N-1)/2j=10/2=5, gcd(7k-1, N)=gcd(16806, 11)=1, j=1是唯一使(N-1)/2j為整數(shù)的j, W(5)不成立.,結(jié)論: 11可能是素?cái)?shù) 答案正確的概率

24、為1-2-3,定理1. (1) 如果對(duì)于任意1?b<N, W(b)成立, 則N是合數(shù). (2) 如果N是合數(shù), 則(N-1)/2?|{b | 1?b<N, W(b)}|*(1)說明算法是正確的.*(2)說明, 如果N是合數(shù), 則至少一半b(b<N)使W(b)成立定理2. 算法的回答“N是素?cái)?shù)”正確的概率是1-2-m.,算法性能的分析,8.5 Randomized Sorting A

25、lgorithm,問題的定義 隨機(jī)算法 算法性能的分析,問題的定義,輸入 S={x1, x2, …, xn} 輸出 排序的S,,基本思想采用隨機(jī)抽樣的方法確定集合的劃分點(diǎn)把集合劃分為兩個(gè)子集合分別遞歸地在每個(gè)子集合上使用隨機(jī)排序算法,隨機(jī)算法,算法1. 均勻等可能地在S中隨機(jī)抽取一個(gè)樣本y;2. 比較S中每個(gè)元素, 把S劃分為如下兩個(gè)集合: S1={ x | x?S, xy };3. 遞歸地排序S1

26、和S2;4. 順序輸出排序的S1, y, S2;,,算法性能的分析,基本概念 S(i)表示S中階為i的元素 例如, S(1)和S(n)分別是最小和最大元素 隨機(jī)變量Xij 定義如下: Xij=1如果S(i)和S(j)在運(yùn)行中被比較, 否則為0 Xij是S(i)和S(j)的比較次數(shù) 算法的比較次數(shù)為 算法的平均復(fù)雜性為,計(jì)算E[Xij] 設(shè)pij為S(i)和S(j)在運(yùn)行中比較的概率, 則

27、 E[Xij]=pij?1+(1-pij)?0=pij,關(guān)鍵問題成為求解pij,,求解Pij我們可以用樹表示算法的計(jì)算過程,,我們可以觀察到如下事實(shí): 一個(gè)子樹的根必須與其子樹的所有節(jié)點(diǎn)比較 不同子樹中的節(jié)點(diǎn)不可能比較 任意兩個(gè)節(jié)點(diǎn)至多比較一次,當(dāng)S(i), S(i+1), …, S(j)在同一子樹時(shí), S(i)和S(j)才可能比較 由隨機(jī)算法的特點(diǎn), S(i), S(i+1), …, S(j)在同一子樹的概 率為1

28、 只有S(i)或S(j)被選為劃分點(diǎn)時(shí), S(i)和S(j)才可能比較 S(i), S(i+1), …, S(j)等可能地被選為劃分點(diǎn), 所以S(i)和S(j) 進(jìn)行比較的概率是: 2/(j-i+1), 即pij=2/(j-i+1),現(xiàn)在我們有,定理. 隨機(jī)排序算法的期望時(shí)間復(fù)雜性為O(nlogn),8.6 A Min-Cut Algorithm,問題定義 隨機(jī)算法算法性能的分析,輸入:無向多重連通圖G

29、輸出一個(gè)Min-Cut,問題定義,圖G的一個(gè)Cut是一組邊, 從G中刪除這個(gè)Cut將導(dǎo)致 兩個(gè)或多個(gè)連通分量 Cut的大小是其邊數(shù), 多重邊重復(fù)計(jì)算 最小Cut是具有最少邊的Cut,隨機(jī)算法,基本概念Cut可以視為節(jié)點(diǎn)集的劃分V=(C, V-C), Cut是所有G中連接C和V-C的邊集合.圖G的邊(x, y)的contraction:用新節(jié)點(diǎn)代替節(jié)點(diǎn)x和y或邊(x, y), ?v?V, 用邊(v, z)代替邊(x

30、, v)或(y, v),G的其余部分保持不變 例如:,我們用G/(x, y)表示G的邊(x, y)的收縮邊集合F?G收縮記作G/F圖G/F的節(jié)點(diǎn)集合表示為V/F圖G/F的節(jié)點(diǎn)集合表示為E/F,隨機(jī)算法1. H=G;2. While |H(V)| > 2 Do 隨機(jī)地從H(E)中選擇一條邊(x, y); F=F?{(x, y)}; H=H/(x, y);Cut=連接H中

31、兩個(gè)元節(jié)點(diǎn)的G的所有邊.,例,,,Cut={(1,3), (2, 3)},定理1. 如果算法的輸入是具有n個(gè)節(jié)點(diǎn)的多重圖, 則 算法的時(shí)間復(fù)雜性為O(n2). 證明. 一次邊收縮需要O(n)時(shí)間. 至多進(jìn)行O(n)次收縮. 于是, 算法時(shí)間復(fù)雜性為O(n2). 注意: 我們僅證明了在O(n2)時(shí)間內(nèi)算法能夠求出一個(gè)Cut, 但是這個(gè)Cut不一定是優(yōu)

32、化的.,算法的性能分析,引理1. 如果k是min-cut的大小, 則G至少有kn/2條邊. 證. 如果|G(E)|<kn/2, 則存在一個(gè)度小于k的節(jié)點(diǎn)p. 刪除與p相關(guān)連的k條, 把G劃分為兩個(gè)連通分 量, 其一是僅包含p. 于是, 與p相關(guān)連的邊集合是一個(gè)cut. 但是這個(gè)cut的大小<k, 與min-cut

33、大小為k矛盾.引理2. 算法輸出的cut是連接兩個(gè)剩余節(jié)點(diǎn)的沒有被收 縮過的邊. 證. 從算法定義可以看到, 算法輸出的cut是連接兩 個(gè)剩余節(jié)點(diǎn)的沒有被收縮的邊的集合.,引理1. 如果k是圖G的一個(gè)min-cut的大小, 則G至少有 kn/2條邊. 證. 如果|G(E)|<kn/2, 則存在一個(gè)度小于k的節(jié)點(diǎn)p.

34、 刪除與p相關(guān)連的k條, 把G劃分為兩個(gè)連通分 量, 其一是僅包含p的連通分量. 于是, 與p相關(guān)連的邊集合是一個(gè)cut. 但是這個(gè)cut的大小<k, 與min-cut大小為k矛盾.,,定理2. 設(shè)C是一個(gè)min-cut, 其大小為k. 在算法結(jié)束 時(shí), C中無邊被收縮過的概率大于2/n2. 證. Ai表

35、示第i步?jīng)]有選中C的邊, 1?i?n-2. 在第1步, 選中的邊在C中的概率至多為k/(kn/2)=2/n, 即 Pr(A1 )?1-2/n. 在第2步, 若A1發(fā)生, 則至少有k(n-1)/2條邊(每次收縮減 少一個(gè)節(jié)點(diǎn)), 選中C中邊的概率為2/(n-1), 即

36、 Pr(A2| A1 )?1-2/(n-1). 在第i步, 若A1至Ai-1發(fā)生, 則有n-i+1個(gè)節(jié)點(diǎn), 即至少有 k(n-i+1)/2條邊, 于是Pr(Ai| ?1?j?i-1 Aj )?1-2/(n-i+1) 最后我們有 Pr(?1?i?n-2 Ai ) ? ?1?i?n-2(1-