第7章-隨機(jī)化算法

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

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

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

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

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

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

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

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

18

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

No.1快速排序算法

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

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

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

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

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

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

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

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

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

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

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

intk=0;for(intj=1;j<=n;j++)if(T[j]==x)k++;return(k>n/2);//k>n/2時(shí)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主元素問題對(duì)于任何給定的>0，算法MajorityMC重復(fù)調(diào)用log(1/)

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