1、1第7章 隨機(jī)化算法2 學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn)理解產(chǎn)生偽隨機(jī)數(shù)的算法理解產(chǎn)生偽隨機(jī)數(shù)的算法掌握數(shù)值隨機(jī)化算法的設(shè)計(jì)思想掌握數(shù)值隨機(jī)化算法的設(shè)計(jì)思想 掌握舍伍德算法的設(shè)計(jì)思想掌握舍伍德算法的設(shè)計(jì)思想掌握拉斯維加斯算法的設(shè)計(jì)思想掌握拉斯維加斯算法的設(shè)計(jì)思想掌握蒙特卡羅算法的設(shè)計(jì)思想掌握蒙特卡羅算法的設(shè)計(jì)思想3引言引言o 前面幾章所討論的分治、動(dòng)態(tài)規(guī)劃、貪心法、回溯和分前面幾章所討論的分治、動(dòng)態(tài)規(guī)劃、貪心法、回溯和分支限界等算法的支限界等算法的每一計(jì)算步驟都是確定的每一計(jì)算步驟都是確定的，本章所討論，本章所討論的概率算法的概率算法允許執(zhí)行過程中隨機(jī)選擇下一計(jì)算步驟允許執(zhí)行過程中隨機(jī)選擇下一計(jì)算步驟。o 在

2、多數(shù)情況下，當(dāng)算法在執(zhí)行過程中面臨一個(gè)選擇時(shí)，在多數(shù)情況下，當(dāng)算法在執(zhí)行過程中面臨一個(gè)選擇時(shí)，隨機(jī)性選擇常比最優(yōu)選擇隨機(jī)性選擇常比最優(yōu)選擇省時(shí)省時(shí)，因此概率算法可在很大，因此概率算法可在很大程度上程度上降低算法復(fù)雜性降低算法復(fù)雜性。o 概率算法的一個(gè)基本特征概率算法的一個(gè)基本特征是對所求解問題的同一實(shí)例用是對所求解問題的同一實(shí)例用同一概率算法求解兩次可能得到完全不同的效果同一概率算法求解兩次可能得到完全不同的效果( (所需所需時(shí)間或計(jì)算結(jié)果時(shí)間或計(jì)算結(jié)果) )。4引言引言o 本章將要介紹的概率算法包括：本章將要介紹的概率算法包括：n 數(shù)值隨機(jī)化算法數(shù)值隨機(jī)化算法 求解數(shù)值問題的近似解求解數(shù)值問

3、題的近似解，精度隨計(jì)，精度隨計(jì)算時(shí)間增加而不斷提高。算時(shí)間增加而不斷提高。n 舍伍德算法舍伍德算法 消除算法最壞情況行為與特定實(shí)例之間消除算法最壞情況行為與特定實(shí)例之間的關(guān)聯(lián)性，并不提高平均性能的關(guān)聯(lián)性，并不提高平均性能，也不是刻意避免算，也不是刻意避免算法的最壞情況行為。法的最壞情況行為。n 拉斯維加斯算法拉斯維加斯算法 求解問題的正確解，但可能找不到求解問題的正確解，但可能找不到解。解。n 蒙特卡羅算法蒙特卡羅算法 求解問題的準(zhǔn)確解，但這個(gè)解未必正求解問題的準(zhǔn)確解，但這個(gè)解未必正確，且一般情況下無法有效判定正確性。確，且一般情況下無法有效判定正確性。5隨機(jī)化算法概述隨機(jī)化算法概述一個(gè)一個(gè)（

4、randomized algorithm）是指）是指需要利用需要利用隨機(jī)數(shù)發(fā)生器隨機(jī)數(shù)發(fā)生器的算法，算法執(zhí)行的某些的算法，算法執(zhí)行的某些選擇依賴于選擇依賴于隨機(jī)數(shù)發(fā)生器隨機(jī)數(shù)發(fā)生器所產(chǎn)生的隨機(jī)數(shù)。所產(chǎn)生的隨機(jī)數(shù)。 6隨機(jī)化算法隨機(jī)化算法有時(shí)也稱有時(shí)也稱（probabilistic probabilistic algorithmalgorithm），但也有人對兩者這樣區(qū)分：），但也有人對兩者這樣區(qū)分：如果取得如果取得結(jié)果的途徑是隨機(jī)的結(jié)果的途徑是隨機(jī)的，則稱為，則稱為隨機(jī)算法隨機(jī)算法，如拉斯維，如拉斯維加斯算法；而加斯算法；而如果取得的解是否正確存在隨機(jī)性如果取得的解是否正確存在隨機(jī)性，稱為，稱

5、為概率概率算法算法，如蒙特卡羅算法。，如蒙特卡羅算法。本書中統(tǒng)一稱為本書中統(tǒng)一稱為隨機(jī)化算法隨機(jī)化算法。隨機(jī)化算法隨機(jī)化算法7當(dāng)算法執(zhí)行過程中面臨選擇時(shí)，當(dāng)算法執(zhí)行過程中面臨選擇時(shí)，概率算法概率算法通通常比常比最優(yōu)選擇算法最優(yōu)選擇算法省時(shí)省時(shí)。對所求問題的對所求問題的同一實(shí)例同一實(shí)例用用同一概率算法求解同一概率算法求解兩次兩次，兩次求解兩次求解所需的所需的時(shí)間甚至所得的結(jié)果時(shí)間甚至所得的結(jié)果可能有相當(dāng)大的差別可能有相當(dāng)大的差別。設(shè)計(jì)思想簡單，易于實(shí)現(xiàn)。設(shè)計(jì)思想簡單，易于實(shí)現(xiàn)。隨機(jī)化算法的特點(diǎn)隨機(jī)化算法的特點(diǎn)8數(shù)值隨機(jī)算法數(shù)值隨機(jī)算法A A舍伍德算法舍伍德算法B B蒙特卡羅算法蒙特卡羅算法D D

6、 拉斯維加斯算法拉斯維加斯算法C C隨機(jī)算法分類隨機(jī)算法分類 9 數(shù)值隨機(jī)算法（數(shù)值隨機(jī)算法（numerical randomized algorithm）用于求數(shù)值問題的近似解。）用于求數(shù)值問題的近似解。 數(shù)值隨機(jī)算法數(shù)值隨機(jī)算法10 總能求得問題的正確解總能求得問題的正確解。當(dāng)一個(gè)確定性算法在當(dāng)一個(gè)確定性算法在最最壞情況下壞情況下的計(jì)算復(fù)雜度與其在的計(jì)算復(fù)雜度與其在平均情況下平均情況下的計(jì)算復(fù)雜的計(jì)算復(fù)雜度兩者相差較大時(shí)度兩者相差較大時(shí)，可以在這個(gè)確定算法中，可以在這個(gè)確定算法中引入隨機(jī)引入隨機(jī)性性將它改造成一個(gè)舍伍德算法，用來將它改造成一個(gè)舍伍德算法，用來消除或減少問題消除或減少問題的不

7、同實(shí)例之間在計(jì)算時(shí)間上的差別的不同實(shí)例之間在計(jì)算時(shí)間上的差別。舍伍德算法的舍伍德算法的精髓精髓不是避免算法的最壞情況行為不是避免算法的最壞情況行為，而是而是設(shè)法消除這設(shè)法消除這種最壞行為與特定實(shí)例之間的關(guān)聯(lián)性種最壞行為與特定實(shí)例之間的關(guān)聯(lián)性。舍伍德算法舍伍德算法11 求得的解總是正確的求得的解總是正確的，但有時(shí)拉斯維加斯算法但有時(shí)拉斯維加斯算法可能始終找不到解可能始終找不到解。一般情況下，。一般情況下，求得正確解的概求得正確解的概率隨計(jì)算時(shí)間的增加而增大率隨計(jì)算時(shí)間的增加而增大。因此，為了減少求解。因此，為了減少求解失敗的概率，可以使用一個(gè)拉斯維加斯算法對同一失敗的概率，可以使用一個(gè)拉斯維加斯

8、算法對同一實(shí)例，重復(fù)多次執(zhí)行該算法。實(shí)例，重復(fù)多次執(zhí)行該算法。拉斯維加斯算法拉斯維加斯算法12 該法用于求問題的該法用于求問題的準(zhǔn)確解準(zhǔn)確解( (或者說是精確解而或者說是精確解而不是近似解不是近似解) )，但不保證所求得的解是正確的，也就，但不保證所求得的解是正確的，也就是說，蒙特卡羅算法求得的解有時(shí)是錯(cuò)誤的。不過是說，蒙特卡羅算法求得的解有時(shí)是錯(cuò)誤的。不過，由于可以，由于可以設(shè)法控制這類算法得到錯(cuò)誤解的概率設(shè)法控制這類算法得到錯(cuò)誤解的概率，并并因它的簡單高效，是很有價(jià)值的一類隨機(jī)算法因它的簡單高效，是很有價(jià)值的一類隨機(jī)算法。蒙特卡羅算法蒙特卡羅算法13 一般情況下，蒙特卡羅算法求得正確解的概

9、率一般情況下，蒙特卡羅算法求得正確解的概率隨計(jì)算時(shí)間的增加而增大。但隨計(jì)算時(shí)間的增加而增大。但無論如何不能保證解無論如何不能保證解的正確性，而且通常無法有效地判斷所求得的解究的正確性，而且通常無法有效地判斷所求得的解究竟是否正確竟是否正確，這是，這是蒙特卡羅算法的缺陷蒙特卡羅算法的缺陷。蒙特卡羅算法蒙特卡羅算法14隨機(jī)數(shù)隨機(jī)數(shù) 隨機(jī)數(shù)隨機(jī)數(shù)在隨機(jī)化算法設(shè)計(jì)中扮演著十分重要的角在隨機(jī)化算法設(shè)計(jì)中扮演著十分重要的角色。色。 在現(xiàn)實(shí)計(jì)算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù)，因此在在現(xiàn)實(shí)計(jì)算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù)，因此在隨機(jī)化算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，隨機(jī)化算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，

10、即即偽隨機(jī)數(shù)。偽隨機(jī)數(shù)。15用隨機(jī)投點(diǎn)法計(jì)算用隨機(jī)投點(diǎn)法計(jì)算 值值 設(shè)有一半徑為設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨機(jī)地投的圓及其外切四邊形。向該正方形隨機(jī)地投擲擲n個(gè)點(diǎn)。設(shè)落入圓內(nèi)的點(diǎn)數(shù)為個(gè)點(diǎn)。設(shè)落入圓內(nèi)的點(diǎn)數(shù)為k。由于所投入的點(diǎn)在正方形上。由于所投入的點(diǎn)在正方形上均勻分布，因而所投入的點(diǎn)落入圓內(nèi)的概率為均勻分布，因而所投入的點(diǎn)落入圓內(nèi)的概率為: 所以當(dāng)所以當(dāng)n足夠大時(shí)，足夠大時(shí)，k與與n之比就之比就逼近這一概率逼近這一概率，從而從而4422rrnk416計(jì)算定積分計(jì)算定積分設(shè)設(shè)f(x)是是0，1上的連續(xù)函數(shù)，且上的連續(xù)函數(shù)，且0 f(x) 1。需要計(jì)算的積分為需要計(jì)算的積分為 ,

11、積分積分I等于圖中的等于圖中的綠色面積綠色面積G。10)(dxxfI17解非線性方程組解非線性方程組求解下面的非線性方程組求解下面的非線性方程組0),(0),(0),(21212211nnnnxxxfxxxfxxxf其中，其中，x1,x2,xn是實(shí)變量，是實(shí)變量，fi是未知量是未知量x1,x2,xn的的非線性非線性實(shí)實(shí)函數(shù)。函數(shù)。要求確定上述方程組在指定求根范圍內(nèi)的一組解要求確定上述方程組在指定求根范圍內(nèi)的一組解 。*2*1,nxxx 18 這兩種算法的這兩種算法的核心核心都在于都在于選擇合適的劃分選擇合適的劃分基準(zhǔn)基準(zhǔn)。舍伍德算法隨機(jī)地選擇一個(gè)數(shù)組元素作舍伍德算法隨機(jī)地選擇一個(gè)數(shù)組元素作為劃

12、分基準(zhǔn)為劃分基準(zhǔn)。線性時(shí)間選擇算法線性時(shí)間選擇算法 No.1快速排序算法快速排序算法 No.2舍伍德舍伍德(Sherwood)算法算法19舍伍德舍伍德(Sherwood)算法算法 有時(shí)也會遇到這樣的情況，即有時(shí)也會遇到這樣的情況，即所給的確定性算法無法直接所給的確定性算法無法直接改造成舍伍德型算法改造成舍伍德型算法。 此時(shí)可借助于此時(shí)可借助于隨機(jī)預(yù)處理技術(shù)隨機(jī)預(yù)處理技術(shù)，不改變原有的確定性算法，不改變原有的確定性算法，僅對其輸入進(jìn)行隨機(jī)洗牌僅對其輸入進(jìn)行隨機(jī)洗牌，同樣可收到舍伍德算法的效果。，同樣可收到舍伍德算法的效果。20拉斯維加斯拉斯維加斯( Las Vegas )算法算法 拉斯維加斯算法

13、拉斯維加斯算法的一個(gè)的一個(gè)顯著特征顯著特征是是它所作的隨機(jī)它所作的隨機(jī)性決策有可能導(dǎo)致算法找不到所需的解性決策有可能導(dǎo)致算法找不到所需的解。void obstinate(Object x, Object y) / 反復(fù)調(diào)用拉斯維加斯算法反復(fù)調(diào)用拉斯維加斯算法LV(x,y)， /直到找到問題的一個(gè)解直到找到問題的一個(gè)解y bool success= false; while (!success) success=lv(x,y); 21拉斯維加斯拉斯維加斯( Las Vegas )算法算法 設(shè)設(shè)p(x)是是對輸入對輸入x調(diào)用拉斯維加斯算法調(diào)用拉斯維加斯算法獲得問題的一個(gè)解的獲得問題的一個(gè)解的概率概

14、率。一個(gè)正確的拉斯維加斯算法應(yīng)該對所有輸入。一個(gè)正確的拉斯維加斯算法應(yīng)該對所有輸入x均有均有p(x)0。設(shè)設(shè)t(x)是是算法算法obstinate找到具體實(shí)例找到具體實(shí)例x的一個(gè)解所需的的一個(gè)解所需的平均時(shí)間平均時(shí)間， s(x)和和e(x)分別是算法對于具體實(shí)例分別是算法對于具體實(shí)例x求解成功或求解失敗所需求解成功或求解失敗所需的平均時(shí)間的平均時(shí)間，則有：，則有： 解此方程可得：解此方程可得： )()()(1 ()()()(xtxexpxsxpxt)()()(1)()(xexpxpxsxt22n后問題的拉斯維加斯算法后問題的拉斯維加斯算法 對于對于n后問題的任何一個(gè)解而言，后問題的任何一個(gè)解而

15、言，每一個(gè)皇后在棋盤每一個(gè)皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機(jī)放置上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機(jī)放置的的。由此容易想到。由此容易想到拉斯維加斯算法拉斯維加斯算法。 在棋盤上相繼的各行中在棋盤上相繼的各行中隨機(jī)地放置皇后隨機(jī)地放置皇后，并注意使新，并注意使新放置的皇后與已放置的皇后互不攻擊，直至放置的皇后與已放置的皇后互不攻擊，直至n個(gè)皇后均已個(gè)皇后均已相容地放置好，或已沒有下一個(gè)皇后的可放置位置時(shí)為止。相容地放置好，或已沒有下一個(gè)皇后的可放置位置時(shí)為止。23n后問題后問題 如果將上述如果將上述隨機(jī)放置策略隨機(jī)放置策略與與回溯法回溯法相相結(jié)合結(jié)合，可能，可能會

16、獲得更好的效果。會獲得更好的效果。 可以可以先在棋盤的若干行中隨機(jī)地放置皇后先在棋盤的若干行中隨機(jī)地放置皇后，然后，然后在在后繼行中用回溯法繼續(xù)放置后繼行中用回溯法繼續(xù)放置，直至找到一個(gè)解或宣告，直至找到一個(gè)解或宣告失敗。失敗。 隨機(jī)放置的皇后越多隨機(jī)放置的皇后越多，后繼回溯搜索所需的，后繼回溯搜索所需的時(shí)間就時(shí)間就越少越少，但但失敗的概率也就越大失敗的概率也就越大。 24蒙特卡羅蒙特卡羅(Monte Carlo)算法算法在實(shí)際應(yīng)用中常會遇到一些問題，在實(shí)際應(yīng)用中常會遇到一些問題，不論采用確定性算法或隨機(jī)不論采用確定性算法或隨機(jī)化算法都無法保證每次都能得到正確的解答化算法都無法保證每次都能得到

17、正確的解答。蒙特卡羅算法蒙特卡羅算法則則在一般情況下可以保證對問題的所有實(shí)例都以高概率給出正確在一般情況下可以保證對問題的所有實(shí)例都以高概率給出正確解解，但是通常，但是通常無法判定無法判定一個(gè)具體解一個(gè)具體解是否正確是否正確。設(shè)設(shè)p是一個(gè)實(shí)數(shù)，且是一個(gè)實(shí)數(shù)，且1/2pn/2n/2時(shí)，時(shí)，稱稱元素元素x x是數(shù)組是數(shù)組T T的的主元素主元素。 templatebool Majority(Type *T, int n)/ 判定主元素的蒙特卡羅算法判定主元素的蒙特卡羅算法 int i=rnd.Random(n)+1; Type x=Ti;/ 隨機(jī)選擇數(shù)組元素隨機(jī)選擇數(shù)組元素 int k=0; for (int j=1;jn/2); / kn/2 時(shí)時(shí)T含有主元素含有主元素templatebool MajorityMC(Type *T, int n, double e)/ 重復(fù)調(diào)用重復(fù)調(diào)用k次次Majority算法算法 int k=ceil(log(1/e)/log(2); for (int i=1;i0，算法，算法MajorityMC重復(fù)調(diào)用重復(fù)調(diào)用 log(1/ ) 次算法次算法M