第八章

RandomizedAlgorithms第八章8.1

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

依賴于輸入的分布對于每個輸入都要考慮算法的概率統計性能隨機算法分析的目標平均時間復雜性:時間復雜性隨機變量的均值獲得正確解的概率獲得優化解的概率解的精確度估計隨機算法的性能分析

隨機算法分析的特征隨機算法的性能分析8.2

RandomizedNumericalAlgorithms計算值計算定積分8.2RandomizedNumericalAlgo計算值數學基礎設有一個半徑為r的園及其外切四邊形向正方形隨機地投擲n個點,設k個點落入園內投擲點落入園內的概率為(r2)/(4r2)=/4.用k/n逼近/4,即k/n/4,于是(4k)/n.我們可以令r=1用投擲n個點的方法計算計算值數學基礎向正方形隨機地投擲n個點,設k個點落入園內算法K=0;Fori=1Ton

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

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

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

算法8.3

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

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

輸出:

S中第k個最小元素.記號

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

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

把S中屬于[L,H]數據存入P

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

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

在O(nlogn)時間內排序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)),算法結束;10.ELSEgoto1.

LAZYSELECT(S,k)數學基礎數學期望離散隨機變量X的數學期望E[X]=i

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

E[f(X)]=i

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

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

x2=np(1-p).

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

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

其他步需O(nlogn)次比較,總需2n+O(nlogn)次比較.

往證算法執行1-9一遍可求出min(S,k)的概率是1-O(n-1/4).

算法執行1-9一遍可求出min(S,k)的條件是:(1).min(S,k)在L和H之間即P包含min(S,k),(2).|P|4n3/4+1.

我們首先來計算上述兩個條件失敗的概率.

算法的性能分析A.計算條件(1)不成立的概率條件(1)不成立當且僅當L>min(S,k)或H<min(S,k).令Xi=1如果第i個隨機樣本min(S,k),否則Xi=0.于是,P(Xi=1)=k/n,P(Xi=0)=1-k/n.令X=1in3/4Xi是R中小于等于min(S,k)

的樣本數.我們有

X的數學期望x=n3/4k/n=kn-1/4,

X的方差x2=n3/4(k/n)(1-k/n)n3/4/4,

X的標準差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.應用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.計算條件(1)不成立的概率x=xrlrhr1rn3/B.計算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不成立”發生當且僅當

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,“算法執行1-9一遍就可以求出min(S,k)”不成立的概率是O(n-1/4).即，“算法執行1-9一遍就可以求出min(S,k)”的概率是1-O(n-1/4).k2n3/42n3/4khklmin(S,kh)min(S,kl)lLhHB.計算P包含min(S,k)但|P|4n3/4+1不8.4

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

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

測試2:212-1=2048

1mod12,W(2)成立.

N是合數.例1.給定N=12.選擇測試數集{2,3,7}例2.給定N=11,選擇測試數集{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為整數的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為整數的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為整數的j,

W(5)不成立.

結論:11可能是素數答案正確的概率為1-2-3例2.給定N=11,選擇測試數集{2,5,7}定理1.

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

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

8.5

RandomizedSortingAlgorithm

問題的定義隨機算法

算法性能的分析

8.5RandomizedSortingAlg問題的定義輸入

S={x1,x2,…,xn}

輸出

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

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

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)分別是最小和最大元素隨機變量Xij定義如下:

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

計算E[Xij]

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

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

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

yT1T2yxT11T12xT21T22

我們可以觀察到如下事實:

一個子樹的根必須與其子樹的所有節點比較不同子樹中的節點不可能比較任意兩個節點至多比較一次求解PijyT1T2yxT11T12xT21T22我們可

當S(i),S(i+1),…,S(j)在同一子樹時,

S(i)和S(j)才可能比較由隨機算法的特點,S(i),S(i+1),…,S(j)在同一子樹的概率為1

只有S(i)或S(j)被選為劃分點時,S(i)和S(j)才可能比較

S(i),S(i+1),…,S(j)等可能地被選為劃分點,所以S(i)和S(j)

進行比較的概率是:2/(j-i+1),即pij=2/(j-i+1)算法設計與分析ch8隨機算法課件

現在我們有

定理.隨機排序算法的期望時間復雜性為O(nlogn)現在我們有8.6

AMin-CutAlgorithm問題定義

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

圖G的一個Cut是一組邊,從G中刪除這個Cut將導致兩個或多個連通分量

Cut的大小是其邊數,多重邊重復計算最小Cut是具有最少邊的Cut輸入:問題定義圖G的一個Cut是一組邊,從G中刪除這個C隨機算法基本概念Cut可以視為節點集的劃分V=(C,V-C),Cut是所有G中連接C和V-C的邊集合.圖G的邊(x,y)的contraction:用新節點代替節點x和y或邊(x,y),

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

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

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

F=F{(x,y)};

H=H/(x,y);Cut=連接H中兩個元節點的G的所有邊.隨機算法例收縮ee1254354312e1收縮e143125e331254收縮e3Cut={(1,3),(2,3)}例收縮ee1254354312e1收縮e143125e331定理1.如果算法的輸入是具有n個節點的多重圖,則算法的時間復雜性為O(n2).

證明.

一次邊收縮需要O(n)時間.

至多進行O(n)次收縮.

于是,算法時間復雜性為O(n2).

注意:

我們僅證明了在O(n2)時間內算法能夠求出一個Cut,

但是這個Cut不一定是優化的.算法的性能分析定理1.如果算法的輸入是具有n個節點的多重圖,則算法的性引理1.如果k是min-cut的大小,則G至少有kn/2條邊.

證.

如果|G(E)|<kn/2,則存在一個度小于k的節點p.

刪除與p相關連的k條,把G劃分為兩個連通分量,其一是僅包含p.

于是,與p相關連的邊集合是一個cut.

但是這個cut的大小<k,與min-cut大小為k矛盾.引理2.算法輸出的cut是連接兩個剩余節點的沒有被收縮過的邊.

證.

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