第7章-隨機化算法

1第7章隨機化算法2學(xué)習(xí)要點理解產(chǎn)生偽隨機數(shù)的算法掌握數(shù)值隨機化算法的設(shè)計思想掌握舍伍德算法的設(shè)計思想掌握拉斯維加斯算法的設(shè)計思想掌握蒙特卡羅算法的設(shè)計思想3引言前面幾章所討論的分治、動態(tài)規(guī)劃、貪心法、回溯和分支限界等算法的每一計算步驟都是確定的，本章所討論的概率算法允許執(zhí)行過程中隨機選擇下一計算步驟。在多數(shù)情況下，當(dāng)算法在執(zhí)行過程中面臨一個選擇時，隨機性選擇常比最優(yōu)選擇省時，因此概率算法可在很大程度上降低算法復(fù)雜性。概率算法的一個基本特征是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不同的效果(所需時間或計算結(jié)果)。4引言本章將要介紹的概率算法包括：數(shù)值隨機化算法求解數(shù)值問題的近似解，精度隨計算時間增加而不斷提高。舍伍德算法消除算法最壞情況行為與特定實例之間的關(guān)聯(lián)性，并不提高平均性能，也不是刻意避免算法的最壞情況行為。拉斯維加斯算法求解問題的正確解，但可能找不到解。蒙特卡羅算法求解問題的準(zhǔn)確解，但這個解未必正確，且一般情況下無法有效判定正確性。5隨機化算法概述一個隨機化算法（randomizedalgorithm）是指需要利用隨機數(shù)發(fā)生器的算法，算法執(zhí)行的某些選擇依賴于隨機數(shù)發(fā)生器所產(chǎn)生的隨機數(shù)。

6隨機化算法有時也稱概率算法（probabilisticalgorithm），但也有人對兩者這樣區(qū)分：如果取得結(jié)果的途徑是隨機的，則稱為隨機算法，如拉斯維加斯算法；而如果取得的解是否正確存在隨機性，稱為概率算法，如蒙特卡羅算法。本書中統(tǒng)一稱為隨機化算法。隨機化算法7當(dāng)算法執(zhí)行過程中面臨選擇時，概率算法通常比最優(yōu)選擇算法省時。對所求問題的同一實例用同一概率算法求解兩次，兩次求解所需的時間甚至所得的結(jié)果可能有相當(dāng)大的差別。設(shè)計思想簡單，易于實現(xiàn)。隨機化算法的特點8數(shù)值隨機算法A舍伍德算法B蒙特卡羅算法D拉斯維加斯算法C隨機算法分類

9數(shù)值隨機算法（numericalrandomizedalgorithm）用于求數(shù)值問題的近似解。數(shù)值隨機算法10

總能求得問題的正確解。當(dāng)一個確定性算法在最壞情況下的計算復(fù)雜度與其在平均情況下的計算復(fù)雜度兩者相差較大時，可以在這個確定算法中引入隨機性將它改造成一個舍伍德算法，用來消除或減少問題的不同實例之間在計算時間上的差別。舍伍德算法的精髓不是避免算法的最壞情況行為，而是設(shè)法消除這種最壞行為與特定實例之間的關(guān)聯(lián)性。舍伍德算法11

求得的解總是正確的，但有時拉斯維加斯算法可能始終找不到解。一般情況下，求得正確解的概率隨計算時間的增加而增大。因此，為了減少求解失敗的概率，可以使用一個拉斯維加斯算法對同一實例，重復(fù)多次執(zhí)行該算法。拉斯維加斯算法12該法用于求問題的準(zhǔn)確解(或者說是精確解而不是近似解)，但不保證所求得的解是正確的，也就是說，蒙特卡羅算法求得的解有時是錯誤的。不過，由于可以設(shè)法控制這類算法得到錯誤解的概率，并因它的簡單高效，是很有價值的一類隨機算法。蒙特卡羅算法13一般情況下，蒙特卡羅算法求得正確解的概率隨計算時間的增加而增大。但無論如何不能保證解的正確性，而且通常無法有效地判斷所求得的解究竟是否正確，這是蒙特卡羅算法的缺陷。蒙特卡羅算法14隨機數(shù)

隨機數(shù)在隨機化算法設(shè)計中扮演著十分重要的角色。在現(xiàn)實計算機上無法產(chǎn)生真正的隨機數(shù)，因此在隨機化算法中使用的隨機數(shù)都是一定程度上隨機的，即偽隨機數(shù)。15用隨機投點法計算值

設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨機地投擲n個點。設(shè)落入圓內(nèi)的點數(shù)為k。由于所投入的點在正方形上均勻分布，因而所投入的點落入圓內(nèi)的概率為:

所以當(dāng)n足夠大時，k與n之比就逼近這一概率，從而16計算定積分設(shè)f(x)是[0，1]上的連續(xù)函數(shù)，且0f(x)1。需要計算的積分為,積分I等于圖中的綠色面積G。17解非線性方程組求解下面的非線性方程組其中，x1,x2,…,xn是實變量，fi是未知量x1,x2,…,xn的非線性實函數(shù)。要求確定上述方程組在指定求根范圍內(nèi)的一組解。

18

這兩種算法的核心都在于選擇合適的劃分基準(zhǔn)。舍伍德算法隨機地選擇一個數(shù)組元素作為劃分基準(zhǔn)。線性時間選擇算法

No.1快速排序算法

No.2舍伍德(Sherwood)算法19舍伍德(Sherwood)算法有時也會遇到這樣的情況，即所給的確定性算法無法直接改造成舍伍德型算法。此時可借助于隨機預(yù)處理技術(shù)，不改變原有的確定性算法，僅對其輸入進(jìn)行隨機洗牌，同樣可收到舍伍德算法的效果。20拉斯維加斯(LasVegas)算法

拉斯維加斯算法的一個顯著特征是它所作的隨機性決策有可能導(dǎo)致算法找不到所需的解。voidobstinate(Objectx,Objecty){//反復(fù)調(diào)用拉斯維加斯算法LV(x,y)，

//直到找到問題的一個解yboolsuccess=false;while(!success)success=lv(x,y);}21拉斯維加斯(LasVegas)算法設(shè)p(x)是對輸入x調(diào)用拉斯維加斯算法獲得問題的一個解的概率。一個正確的拉斯維加斯算法應(yīng)該對所有輸入x均有p(x)>0。設(shè)t(x)是算法obstinate找到具體實例x的一個解所需的平均時間，

s(x)和e(x)分別是算法對于具體實例x求解成功或求解失敗所需的平均時間，則有：解此方程可得：22n后問題的拉斯維加斯算法對于n后問題的任何一個解而言，每一個皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機放置的。由此容易想到拉斯維加斯算法。

在棋盤上相繼的各行中隨機地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至n個皇后均已相容地放置好，或已沒有下一個皇后的可放置位置時為止。23n后問題如果將上述隨機放置策略與回溯法相結(jié)合，可能會獲得更好的效果。可以先在棋盤的若干行中隨機地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個解或宣告失敗。

隨機放置的皇后越多，后繼回溯搜索所需的時間就越少，但失敗的概率也就越大。

24蒙特卡羅(MonteCarlo)算法在實際應(yīng)用中常會遇到一些問題，不論采用確定性算法或隨機化算法都無法保證每次都能得到正確的解答。蒙特卡羅算法則在一般情況下可以保證對問題的所有實例都以高概率給出正確解，但是通常無法判定一個具體解是否正確。設(shè)p是一個實數(shù)，且1/2<p<1。如果一個蒙特卡羅算法對于問題的任一實例得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的，且稱p-1/2是該算法的優(yōu)勢。25蒙特卡羅(MonteCarlo)算法如果對于同一實例，蒙特卡羅算法不會給出2個不同的正確解答，則稱該蒙特卡羅算法是一致的。有些蒙特卡羅算法除了具有描述問題實例的輸入?yún)?shù)外，還具有描述錯誤解可接受概率的參數(shù)。這類算法的計算時間復(fù)雜性通常由問題的實例規(guī)模以及錯誤解可接受概率的函數(shù)來描述。26蒙特卡羅(MonteCarlo)算法對于一個一致的p正確蒙特卡羅算法，要提高獲得正確解的概率，只要執(zhí)行該算法若干次，并選擇出現(xiàn)頻次最高的解即可。

如果重復(fù)調(diào)用一個一致的(1/2+)正確的蒙特卡羅算法2m-1次（m=floor(n/2)+1），得到正確解的概率至少為1-，其中，27蒙特卡羅(MonteCarlo)算法對于一個解所給問題的蒙特卡羅算法MC(x)，如果存在問題實例的子集X使得：(1)當(dāng)xX時，MC(x)返回的解是正確的；(2)當(dāng)xX時，正確解是y0，但MC(x)返回的解未必是y0。稱上述算法MC(x)是偏y0的算法。重復(fù)調(diào)用一個一致的，p正確偏y0蒙特卡羅算法k次，可得到一個O(1-(1-p)k)正確的蒙特卡羅算法，且所得算法仍是一個一致的偏y0蒙特卡羅算法。

28主元素問題設(shè)T[1:n]是一個含有n個元素的數(shù)組。當(dāng)|{i|T[i]=x}|>n/2時，稱元素x是數(shù)組T的主元素。

template<classType>boolMajority(Type*T,intn){//判定主元素的蒙特卡羅算法

inti=rnd.Random(n)+1;Typex=T[i];//隨機選擇數(shù)組元素

intk=0;for(intj=1;j<=n;j++)if(T[j]==x)k++;return(k>n/2);//k>n/2時T含有主元素}template<classType>boolMajorityMC(Type*T,intn,doublee){//重復(fù)調(diào)用k次Majority算法

intk=ceil(log(1/e)/log(2));for(inti=1;i<=k;i++)if(Majority(T,n))returntrue;returnfalse;}29主元素問題對于任何給定的>0，算法MajorityMC重復(fù)調(diào)用log(1/)

次算法Majority。它是一個偏真蒙特卡羅算法，且其錯誤概率小于。算法MajorityMC所需