《8-1 隨機(jī)算法.pdf》由會員分享，可在線閱讀，更多相關(guān)《8-1 隨機(jī)算法.pdf（9頁珍藏版）》請在匯文網(wǎng)上搜索。

1、概率計算概率計算就是在算法中可采用隨機(jī)選擇計算的步驟、元素或參數(shù)等。它的基本特征是計算具有不確定性。它的解也不一定是最優(yōu)解。它在很大程度上能降低算法的復(fù)雜度。非標(biāo)準(zhǔn)算法中普遍應(yīng)用概率方法，主要有：(1)直接用概率進(jìn)行數(shù)值計算；(2)用概率/隨機(jī)進(jìn)行選擇；(3)利用概率加速搜索或避免陷于局部最優(yōu)。直接用概率進(jìn)行數(shù)值計算假設(shè)向單位正方形內(nèi)隨機(jī)投入n個點(diǎn)(xi,yi)，若有m個點(diǎn)落入G中，則Im/n。double Darts(int n)double x,y;int k=0;static RandomNumber dart;for(int i=1;i=n;i+)x=dart.fRandom();y=

2、dart.fRandom();if(y=f(x)k+;return k/double(n);y=f(x)G設(shè)f(x)是0,1上的連續(xù)函數(shù)，求I=f(x)dx。10劃分基準(zhǔn)的隨機(jī)選擇在快速排序算法中，若用擬中位數(shù)作為劃分標(biāo)準(zhǔn)，可保證在線性時間內(nèi)完成。但是確定擬中位數(shù)要付出額外開銷。若選用第一個元素為劃分基準(zhǔn)，最壞時的時間復(fù)雜性為O(n2)。若在算法中采用隨機(jī)選擇一個元素作為劃分標(biāo)準(zhǔn)，便可既保證算法的線性時間平均性能，又避免了計算擬中位數(shù)的麻煩。也可先對數(shù)組進(jìn)行“洗牌”，然后再進(jìn)行確定的排序算法。這樣依然可取得同樣的效果。“洗牌”后的快速排序void Shuffle(Type a,int n)/隨

3、機(jī)洗牌算法static RandomNumber md;for(int i=1;i n;i+)int j=md.Random(n i+1)+i;Swap(ai,aj);Void QuiksortByShuffle(Type a,int n)Shuffle(a,n);/將數(shù)組a洗牌Quiksort(a,n);在n個元素的集合中隨機(jī)抽取m(0mn)個無重復(fù)的元素。為簡單起見，假定所有元素的值都位于1至n之間。隨機(jī)抽樣隨機(jī)抽樣1、首先將n個元素都標(biāo)記為“未選擇”；2、重復(fù)下列步驟直到抽取了m個不同的元素(1)產(chǎn)生一個1至n間的隨機(jī)數(shù)r；(2)如果r標(biāo)記為“未選擇”，將它標(biāo)記為“已選擇”，并加入到抽樣

4、中。我們采用下面的方法進(jìn)行選擇：隨機(jī)抽樣int RandomSampling(Sn,Am,m)mark1.n=False;count=0;while(count m)r=random(1,n);if(markr=False)count+;Acount=Sr;markr=True;Las Vegas算法Las Vegas算法的特點(diǎn)是隨機(jī)性地進(jìn)行決策。例如對n后問題，Las Vegas算法是隨機(jī)地產(chǎn)生一組王后放置的位置。若成功了，便找到了一個解；若失敗了，就整個重來，再隨機(jī)產(chǎn)生另外一組王后的位置。這樣作，直至找到解。此算法能顯著地改進(jìn)算法的有效性，甚至對迄今為止找不到有效算法的問題，也能得到滿意的結(jié)果。