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

第八章

RandomizedAlgorithms第八章8.1

IntroductiontoRandomizedAlgorithms隨機(jī)算法的基本概念隨機(jī)算法的分類隨機(jī)算法的性能分析方法隨機(jī)算法的基本概念隨機(jī)算法的分類隨機(jī)算法的性能分析方法8.1IntroductiontoRandomize什么是隨機(jī)算法隨機(jī)算法是一種使用概率和統(tǒng)計(jì)方法在其執(zhí)行過程中對于下一計(jì)算步驟作出隨機(jī)選擇的算法隨機(jī)算法的優(yōu)越性對于有些問題:算法簡單對于有些問題:時(shí)間復(fù)雜性低對于有些問題:同時(shí)兼有簡單和時(shí)間復(fù)雜性低隨機(jī)算法的隨機(jī)性對于同一實(shí)例的多次執(zhí)行,效果可能完全不同時(shí)間復(fù)雜性的一個(gè)隨機(jī)變量解的正確性和準(zhǔn)確性也是隨機(jī)的隨機(jī)算法的基本概念什么是隨機(jī)算法隨機(jī)算法的基本概念隨機(jī)算法的分類隨機(jī)數(shù)值算法主要用于數(shù)值問題求解算法的輸出往往是近似解近似解的精確度與算法執(zhí)行時(shí)間成正比MonteCarlo算法主要用于求解需要準(zhǔn)確解的問題算法可能給出錯(cuò)誤解獲得精確解概率與算法執(zhí)行時(shí)間成正比隨機(jī)算法的分類隨機(jī)數(shù)值算法LasVegas算法一旦找到一個(gè)解,該解一定是正確的找到解的概率與算法執(zhí)行時(shí)間成正比增加對問題反復(fù)求解次數(shù),可是求解無效的概率任意小Sherwood算法一定能夠求得一個(gè)正確解確定算法的最壞與平均復(fù)雜性差別大時(shí),加入隨機(jī)性,即得到Sherwood算法消除最壞行為與特定實(shí)例的聯(lián)系LasVegas算法隨機(jī)算法分析的特征僅依賴于隨機(jī)選擇,不依賴于輸入的分布確定算法的平均復(fù)雜性分析:

依賴于輸入的分布對于每個(gè)輸入都要考慮算法的概率統(tǒng)計(jì)性能隨機(jī)算法分析的目標(biāo)平均時(shí)間復(fù)雜性:時(shí)間復(fù)雜性隨機(jī)變量的均值獲得正確解的概率獲得優(yōu)化解的概率解的精確度估計(jì)隨機(jī)算法的性能分析

隨機(jī)算法分析的特征隨機(jī)算法的性能分析8.2

RandomizedNumericalAlgorithms計(jì)算值計(jì)算定積分8.2RandomizedNumericalAlgo計(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ì)算計(jì)算值數(shù)學(xué)基礎(chǔ)向正方形隨機(jī)地投擲n個(gè)點(diǎn),設(shè)k個(gè)點(diǎn)落入園內(nèi)算法K=0;Fori=1Ton

隨機(jī)地產(chǎn)生四邊形中的一點(diǎn)(x,y);Ifx2+y21Thenk=k+1;EndforReturn(4k)/n時(shí)間復(fù)雜性=O(n)不是輸入的大小,而是隨機(jī)樣本的大小解的精確度隨著隨機(jī)樣本大小n增加而增加

算法計(jì)算定積分問題計(jì)算積分?jǐn)?shù)學(xué)基礎(chǔ)令f(x)是區(qū)間[a,b]上的一組獨(dú)立、同分布的隨機(jī)變量{i}的任意密度函數(shù)令g*(x)=g(x)/f(x),則{g*()}是密度為f(x)的隨機(jī)變量集合,而且計(jì)算定積分問題數(shù)學(xué)基礎(chǔ)由強(qiáng)大數(shù)定律我們可以用來近似計(jì)算I令f(x)=1/(b-a)axb索求積分可以由如下I’來近似計(jì)算I由強(qiáng)大數(shù)定律我們可以用算法I=0;Fori=1Ton

隨機(jī)產(chǎn)生[a,b]中點(diǎn)x;I=I+g(x);EndforReturn(b-a)*I/n時(shí)間復(fù)雜性=O(n)不是輸入的大小,而是隨機(jī)樣本的大小解的精確度隨著隨機(jī)樣本大小n增加而增加

算法8.3

RandomizedSelectionAlgorithms問題的定義隨機(jī)算法算法的性能分析8.3RandomizedSelectionAlgo問題的定義

輸入:S={x1,x2,…,xn}，整數(shù)k，1kn.

輸出:

S中第k個(gè)最小元素.記號

Rank(Q,t)=集合Q中的元素t的rank(第k小元素的rank是k)min(Q,i)=集合Q中第i個(gè)最小元素.問題的定義輸入:S={x1,x2,…,xn}，記號隨機(jī)算法

基本思想從S中隨機(jī)地抽取n3/4個(gè)樣本存入R,排序RS中第k最小元素可能成為R中x=kn3/4/n最小元素為了解決誤差問題,我們考察區(qū)間[x-n1/2,x+n1/2]xrlrhr1rn3/4lh………………LH

把S中屬于[L,H]數(shù)據(jù)存入P

在P中查找min(S,k)隨機(jī)算法基本思想xrlrhr1rn3/4lh………………LLAZYSELECT(S,k)

R=獨(dú)立、均勻、可放回地從S隨機(jī)選取的n3/4元素;

在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={yS|LyH};Ifmin(S,k)Pand|P|4n3/4+1/*max(S,k)P可由LpkHp確定*/

9.Then排序P,min(S,k)=min(P,(k-Lp)),算法結(jié)束;10.ELSEgoto1.

LAZYSELECT(S,k)數(shù)學(xué)基礎(chǔ)數(shù)學(xué)期望離散隨機(jī)變量X的數(shù)學(xué)期望E[X]=i

iP(X=i)若f(x)是定義在整數(shù)集上的實(shí)數(shù)值函數(shù),則

E[f(X)]=i

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

x2=1inxi2,Xi是獨(dú)立隨機(jī)變量若隨機(jī)變量Xi滿足P(Xi=1)=p,P(Xi=0)=1-p,則

x2=np(1-p).

方差的性質(zhì)與Chebyshev不等式算法的性能分析定理.算法執(zhí)行1-9步一遍就可求出min(S,k)的概率是1-O(n-1/4),

即算法需要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一遍可求出min(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.于是,P(Xi=1)=k/n,P(Xi=0)=1-k/n.令X=1in3/4Xi是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)差xn3/8/2.x=xrlrhr1rn3/4lh………………LH如果L>min(S,k),X<l.如果H<min(S,k),Xh.于是

P(L>min(S,k))=P(X<l)=P(X<x-n1/2)=P(|X-x|>n1/2),

P(H<min(S,k))=P(Xh)=P(X>h)+P(X=h)=P(|X-x|n1/2)+(n3/4+1)-1.應(yīng)用Chebyshev不等式,又由2n1/8x

n1/2,我們有

P(|X-x|>n1/2)P(|X-x|>2n1/8x)1/(2n1/8)2=O(n-1/4).于是

P(L>min(S,k))=P(H<min(S,k))=O(n-1/4).A.計(jì)算條件(1)不成立的概率x=xrlrhr1rn3/B.計(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)

L<min(S,kl)或H>min(S,kh).類似與上面A中的分析，

P(L<min(S,kl))=P(H>min(S,kh))=O(n-1/4).由A和B,“算法執(zhí)行1-9一遍就可以求出min(S,k)”不成立的概率是O(n-1/4).即，“算法執(zhí)行1-9一遍就可以求出min(S,k)”的概率是1-O(n-1/4).k2n3/42n3/4khklmin(S,kh)min(S,kl)lLhHB.計(jì)算P包含min(S,k)但|P|4n3/4+1不8.4

RandomizedAlgorithmtoTestWhetherNumberisPrime問題的定義隨機(jī)算法設(shè)計(jì)算法的性能分析8.4RandomizedAlgorithmto輸入一個(gè)正整數(shù)N輸出N是否素?cái)?shù)問題的定義輸入問題的定義基本思想對N進(jìn)行m次測試如果有一次測試成功,則回答N是合數(shù)如果m次測試均失敗,則回答N是素?cái)?shù)回答N是合數(shù)時(shí),答案百分之百正確回答N是素?cái)?shù)時(shí),答案正確的概率是1-2-m隨機(jī)算法的設(shè)計(jì)基本思想隨機(jī)算法的設(shè)計(jì)隨機(jī)算法隨機(jī)地選擇m個(gè)數(shù){b1,b2,…,bm},滿足

1b1,b2,…,bmN;Fori=1TomDoIfW(bi)成立ThenReturn(N是合數(shù));Return(N是素?cái)?shù))W(bi)定義如下:(1)biN-11modN,或(2)j[(N-1)/2j=k是整數(shù),1<(bik與N的最大公因子)<N].隨機(jī)算法例1.給定N=12.選擇測試數(shù)集{2,3,7}

測試2:212-1=2048

1mod12,W(2)成立.

N是合數(shù).例1.給定N=12.選擇測試數(shù)集{2,3,7}例2.給定N=11,選擇測試數(shù)集{2,5,7}

測試2:

211-1=1024

=1mod11,

令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)不成立.

測試5:

511-1=9765625

=1mod11,

令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)不成立.

測試7:

711-1=282475249

=1mod11,

令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ù)答案正確的概率為1-2-3例2.給定N=11,選擇測試數(shù)集{2,5,7}定理1.

(1)如果對于任意1b<N,W(b)成立,則N是合數(shù).(2)如果N是合數(shù),則(N-1)/2|{b|1b<N,W(b)}|*(1)說明算法是正確的.*(2)說明,如果N是合數(shù),則至少一半b(b<N)使W(b)成立定理2.

算法的回答“N是素?cái)?shù)”正確的概率是1-2-m.算法性能的分析定理1.(1)如果對于任意1b<N,W(b)成立,

8.5

RandomizedSortingAlgorithm

問題的定義隨機(jī)算法

算法性能的分析

8.5RandomizedSortingAlg問題的定義輸入

S={x1,x2,…,xn}

輸出

排序的S問題的定義輸入基本思想采用隨機(jī)抽樣的方法確定集合的劃分點(diǎn)把集合劃分為兩個(gè)子集合分別遞歸地在每個(gè)子集合上使用隨機(jī)排序算法隨機(jī)算法基本思想隨機(jī)算法

算法1.均勻等可能地在S中隨機(jī)抽取一個(gè)樣本y;2.比較S中每個(gè)元素,把S劃分為如下兩個(gè)集合:

S1={x|xS,x<y},S2={x|xS,x>y};3.遞歸地排序S1和S2;4.順序輸出排序的S1,y,S2;算法算法性能的分析

基本概念

S(i)表示S中階為i的元素

例如,S(1)和S(n)分別是最小和最大元素隨機(jī)變量Xij定義如下:

Xij=1如果S(i)和S(j)在運(yùn)行中被比較,否則為0Xij是S(i)和S(j)的比較次數(shù)算法的比較次數(shù)為算法的平均復(fù)雜性為算法性能的分析基本概念

計(jì)算E[Xij]

設(shè)pij為S(i)和S(j)在運(yùn)行中比較的概率,則

E[Xij]=pij1+(1-pij)0=pij關(guān)鍵問題成為求解pij計(jì)算E[Xij]

求解Pij我們可以用樹表示算法的計(jì)算過程

yT1T2yxT11T12xT21T22

我們可以觀察到如下事實(shí):

一個(gè)子樹的根必須與其子樹的所有節(jié)點(diǎn)比較不同子樹中的節(jié)點(diǎn)不可能比較任意兩個(gè)節(jié)點(diǎn)至多比較一次求解PijyT1T2yxT11T12xT21T22我們可

當(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

只有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)算法設(shè)計(jì)與分析ch8隨機(jī)算法課件

現(xiàn)在我們有

定理.隨機(jī)排序算法的期望時(shí)間復(fù)雜性為O(nlogn)現(xiàn)在我們有8.6

AMin-CutAlgorithm問題定義

隨機(jī)算法算法性能的分析8.6AMin-CutAlgorithm問題定義輸入:無向多重連通圖G輸出一個(gè)Min-Cut問題定義

圖G的一個(gè)Cut是一組邊,從G中刪除這個(gè)Cut將導(dǎo)致兩個(gè)或多個(gè)連通分量

Cut的大小是其邊數(shù),多重邊重復(fù)計(jì)算最小Cut是具有最少邊的Cut輸入:問題定義圖G的一個(gè)Cut是一組邊,從G中刪除這個(gè)C隨機(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),

vV,用邊(v,z)代替邊(x,v)或(y,v),G的其余部分保持不變

例如:收縮ee1254354312隨機(jī)算法基本概念收縮ee1254354312我們用G/(x,y)表示G的邊(x,y)的收縮邊集合FG收縮記作G/F圖G/F的節(jié)點(diǎn)集合表示為V/F圖G/F的節(jié)點(diǎn)集合表示為E/F我們用G/(x,y)表示G的邊(x,y)的收縮隨機(jī)算法1.H=G;2.While|H(V)|>2Do

隨機(jī)地從H(E)中選擇一條邊(x,y);

F=F{(x,y)};

H=H/(x,y);Cut=連接H中兩個(gè)元節(jié)點(diǎn)的G的所有邊.隨機(jī)算法例收縮ee1254354312e1收縮e143125e331254收縮e3Cut={(1,3),(2,3)}例收縮ee1254354312e1收縮e143125e331定理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)化的.算法的性能分析定理1.如果算法的輸入是具有n個(gè)節(jié)點(diǎn)的多重圖,則算法的性引理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大小為k矛盾.引理2.算法輸出的cut是連接兩個(gè)剩余節(jié)點(diǎn)的沒有被收縮過的邊.

證.

從算法定義可以看到,算法輸出的cut是連接兩個(gè)剩余節(jié)點(diǎn)的沒有被收縮的邊的集合.引理1.如果k是min-cut的大小,則G至少有kn/2