資源描述:
《算法設計與分析ch8 隨機算法ppt課件.ppt》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第八章RandomizedAlgorithms8.1IntroductiontoRandomizedAlgorithms隨機算法的基本概念隨機算法的分類隨機算法的性能分析方法隨機算法的基本概念隨機算法的分類隨機算法的性能分析方法什么是隨機算法隨機算法是一種使用概率和統(tǒng)計方法在其執(zhí)行過程中對于下一計算步驟作出隨機選擇的算法隨機算法的優(yōu)越性對于有些問題:算法簡單對于有些問題:時間復雜性低對于有些問題:同時兼有簡單和時間復雜性低隨機算法的隨機性對于同一實例的多次執(zhí)行,效果可能完全不同時間復雜性的一個隨機變量解的正確性和準確性也是隨機的隨機算法的基本概念隨
2、機算法的分類隨機數(shù)值算法主要用于數(shù)值問題求解算法的輸出往往是近似解近似解的精確度與算法執(zhí)行時間成正比MonteCarlo算法主要用于求解需要準確解的問題算法可能給出錯誤解獲得精確解概率與算法執(zhí)行時間成正比LasVegas算法一旦找到一個解,該解一定是正確的找到解的概率與算法執(zhí)行時間成正比增加對問題反復求解次數(shù),可是求解無效的概率任意小Sherwood算法一定能夠求得一個正確解確定算法的最壞與平均復雜性差別大時,加入隨機性,即得到Sherwood算法消除最壞行為與特定實例的聯(lián)系隨機算法分析的特征僅依賴于隨機選擇,不依賴于輸入的分布確定算法的平均復雜性
3、分析:依賴于輸入的分布對于每個輸入都要考慮算法的概率統(tǒng)計性能隨機算法分析的目標平均時間復雜性:時間復雜性隨機變量的均值獲得正確解的概率獲得優(yōu)化解的概率解的精確度估計隨機算法的性能分析8.2RandomizedNumericalAlgorithms計算?值計算定積分計算?值數(shù)學基礎(chǔ)設有一個半徑為r的園及其外切四邊形向正方形隨機地投擲n個點,設k個點落入園內(nèi)投擲點落入園內(nèi)的概率為(?r2)/(4r2)=?/4.用k/n逼近?/4,即k/n??/4,于是??(4k)/n.我們可以令r=1用投擲n個點的方法計算?算法K=0;Fori=1Ton隨機地產(chǎn)生四邊
4、形中的一點(x,y);Ifx2+y2?1Thenk=k+1;EndforReturn(4k)/n時間復雜性=O(n)不是輸入的大小,而是隨機樣本的大小解的精確度隨著隨機樣本大小n增加而增加計算定積分問題計算積分數(shù)學基礎(chǔ)令f(x)是區(qū)間[a,b]上的一組獨立、同分布的隨機變量{?i}的任意密度函數(shù)令g*(x)=g(x)/f(x),則{g*(?)}是密度為f(x)的隨機變量集合,而且由強大數(shù)定律我們可以用來近似計算I令f(x)=1/(b-a)a?x?b索求積分可以由如下I’來近似計算I算法I=0;Fori=1Ton隨機產(chǎn)生[a,b]中點x;I=I+g(
5、x);EndforReturn(b-a)*I/n時間復雜性=O(n)不是輸入的大小,而是隨機樣本的大小解的精確度隨著隨機樣本大小n增加而增加8.3RandomizedSelectionAlgorithms問題的定義隨機算法算法的性能分析問題的定義輸入:S={x1,x2,…,xn},整數(shù)k,1?k?n.輸出:S中第k個最小元素.記號Rank(Q,t)=集合Q中的元素t的rank(第k小元素的rank是k)min(Q,i)=集合Q中第i個最小元素.隨機算法基本思想從S中隨機地抽取n3/4個樣本存入R,排序RS中第k最小元素可能成為R中x=kn3/4/n
6、最小元素為了解決誤差問題,我們考察區(qū)間[x-n1/2,x+n1/2]xrlrhr1rn3/4lh………………LH把S中屬于[L,H]數(shù)據(jù)存入P在P中查找min(S,k)LAZYSELECT(S,k)R=獨立、均勻、可放回地從S隨機選取的n3/4元素;在O(nlogn)時間內(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
7、L?y?H};Ifmin(
8、S,k)?Pand
9、P
10、?4n3/4+1/*max(S,k)?P可由Lp?k?Hp確定*/9.Then排序P,min(S,k)=min(P,(k-Lp)),算法結(jié)束;10.ELSEgoto1.數(shù)學基礎(chǔ)數(shù)學期望離散隨機變量X的數(shù)學期望E[X]=?ii?P(X=i)若f(x)是定義在整數(shù)集上的實數(shù)值函數(shù),則E[f(X)]=?if(i)?P(X=i).Markov不等式P(Y?t)?E[Y]/t,其中Y為非負隨機變量,t>0.算法的性能分析方差的性質(zhì)與Chebyshev不等式方差?x2=E[(X-?x)2],?x為隨機變量X的數(shù)學期望?x稱為標準差Che
11、byshev不等式:P(
12、X-?x
13、>t?x)?1/t2如果隨機變量X滿足P(X=1)=p,P(X=0)=1-p,則?x2