第12章概率算法

1、算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社第第12章章 概率算法概率算法 12.1 概概 述述 12.2 舍伍德舍伍德(Sherwood)型概率算法型概率算法12.3 拉斯維加斯拉斯維加斯(Las Vegas)型概率算法型概率算法12.4 蒙特卡羅蒙特卡羅(Monte Carlo)型概率算法型概率算法12.5 實驗項目實驗項目隨機(jī)數(shù)發(fā)生器隨機(jī)數(shù)發(fā)生器算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社12.1 概概 述述 前面討論的算法都是針對確定性算法，即算前面討論的算法都是針對確定性算法，即算法的每一步都明確指定下一步該如何進(jìn)行，對于任法的每一步都明確指定下一步該如何進(jìn)行

2、，對于任何合理的輸入，確定性算法都必須給出正確的輸出。何合理的輸入，確定性算法都必須給出正確的輸出。概率算法把概率算法把“對于所有合理的輸入都必須給對于所有合理的輸入都必須給出正確的輸出出正確的輸出”這一求解問題的條件放寬，允許算這一求解問題的條件放寬，允許算法在執(zhí)行過程中隨機(jī)選擇下一步該如何進(jìn)行，同時法在執(zhí)行過程中隨機(jī)選擇下一步該如何進(jìn)行，同時允許結(jié)果以較小的概率出現(xiàn)錯誤，并以此為代價，允許結(jié)果以較小的概率出現(xiàn)錯誤，并以此為代價，獲得算法運(yùn)行時間的大幅度減少。獲得算法運(yùn)行時間的大幅度減少。算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社12.1.1 概率算法的設(shè)計思想概率算法的設(shè)計思

3、想解讀藏寶圖要解讀藏寶圖要4天，不允許出發(fā)后解讀；天，不允許出發(fā)后解讀；另外一個人每天會拿走一部分寶藏；另外一個人每天會拿走一部分寶藏；有一個小精靈可告訴你如何解讀，但需支付相有一個小精靈可告訴你如何解讀，但需支付相當(dāng)于那個人當(dāng)于那個人3天拿走的寶藏。天拿走的寶藏。問題：如何做才能得到更多的寶藏？問題：如何做才能得到更多的寶藏？5天5天5天算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社12.1.1 概率算法的設(shè)計思想概率算法的設(shè)計思想假設(shè)得到藏寶圖時剩余寶藏價值是假設(shè)得到藏寶圖時剩余寶藏價值是x，知道藏寶地點，知道藏寶地點的那個人每天拿走寶藏價值是的那個人每天拿走寶藏價值是y，并且，

4、并且x9y，可行方案有：，可行方案有：1.用用4天時間解讀藏寶圖，用天時間解讀藏寶圖，用5天時間到達(dá)藏寶地點，可獲天時間到達(dá)藏寶地點，可獲得寶藏價值得寶藏價值x-9y;2.接受小精靈的條件，用接受小精靈的條件，用5天時間到達(dá)藏寶地點，并支付天時間到達(dá)藏寶地點，并支付給小精靈寶藏價值給小精靈寶藏價值3y，則可獲寶藏價值，則可獲寶藏價值x-5y-3y=x-8y;3.投擲硬幣決定首先前往哪個地點，如果發(fā)現(xiàn)地點是錯的，投擲硬幣決定首先前往哪個地點，如果發(fā)現(xiàn)地點是錯的，就前往另一個地點。這樣有一半的機(jī)會獲得寶藏價值就前往另一個地點。這樣有一半的機(jī)會獲得寶藏價值x-5y，另一半機(jī)會獲得寶藏價值，另一半機(jī)會

5、獲得寶藏價值x-10y，這樣最終可獲寶，這樣最終可獲寶藏價值是藏價值是x-7.5y。當(dāng)面臨選擇時，當(dāng)面臨選擇時，如計算正確選擇的時間大于隨機(jī)確定一個選擇的時如計算正確選擇的時間大于隨機(jī)確定一個選擇的時間，那么應(yīng)該隨機(jī)選擇一個間，那么應(yīng)該隨機(jī)選擇一個。當(dāng)算法執(zhí)行過程中面臨一個選擇，有時候。當(dāng)算法執(zhí)行過程中面臨一個選擇，有時候隨機(jī)選擇算法的執(zhí)行動作可能比花費(fèi)時間計算哪個是最優(yōu)選擇更好。隨機(jī)選擇算法的執(zhí)行動作可能比花費(fèi)時間計算哪個是最優(yōu)選擇更好。算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社12.1.1 概率算法的設(shè)計思想概率算法的設(shè)計思想 概率算法把概率算法把“對于所有合理的輸入都必須給

6、出對于所有合理的輸入都必須給出正確的輸出正確的輸出”這一求解問題的條件放寬，把這一求解問題的條件放寬，把隨機(jī)性的隨機(jī)性的選擇選擇注入到算法中，在算法執(zhí)行某些步驟時，可以隨注入到算法中，在算法執(zhí)行某些步驟時，可以隨機(jī)地選擇下一步該如何進(jìn)行，同時允許機(jī)地選擇下一步該如何進(jìn)行，同時允許結(jié)果以較小的結(jié)果以較小的概率出現(xiàn)錯誤概率出現(xiàn)錯誤，并以此為代價，獲得算法運(yùn)行時間的，并以此為代價，獲得算法運(yùn)行時間的大幅度減少。大幅度減少。如果一個問題沒有有效的確定性算法可以在一如果一個問題沒有有效的確定性算法可以在一個合理的時間內(nèi)求解，但是該問題個合理的時間內(nèi)求解，但是該問題能接受小概率的錯能接受小概率的錯誤誤，那

7、么采用概率算法就可以快速找到問題的解。，那么采用概率算法就可以快速找到問題的解。 算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社 例如，判斷表達(dá)式例如，判斷表達(dá)式f(x1, x2, , xn)是否恒等于是否恒等于0。概率算法首先生成一個隨機(jī)概率算法首先生成一個隨機(jī)n元向量元向量(r1, r2, , rn)，并計算并計算f(r1, r2, , rn)的值，如果的值，如果f(r1, r2, , rn)0，則則f(x1, x2, , xn)不恒等于不恒等于0；如果；如果f(r1, r2, , rn)0，則或者則或者f(x1, x2, , xn)恒等于恒等于0，或者是，或者是(r1, r2,

8、 , rn)比較特殊，如果這樣重復(fù)幾次，繼續(xù)得到比較特殊，如果這樣重復(fù)幾次，繼續(xù)得到f(r1, r2, , rn)0的結(jié)果，那么就可以得出的結(jié)果，那么就可以得出f(x1, x2, , xn)恒等于恒等于0的結(jié)論，并且測試的隨機(jī)向量越多，這個結(jié)果出錯的結(jié)論，并且測試的隨機(jī)向量越多，這個結(jié)果出錯的可能性就越小。的可能性就越小。算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社一般情況下，概率算法具有以下基本特征：一般情況下，概率算法具有以下基本特征：（1）概率算法的輸入包括）概率算法的輸入包括兩部分兩部分，一部分是，一部分是原問題原問題的輸入的輸入，另一部分是一個供算法進(jìn)行隨機(jī)選擇的，另一部

9、分是一個供算法進(jìn)行隨機(jī)選擇的隨隨機(jī)數(shù)序列機(jī)數(shù)序列；（2）概率算法在運(yùn)行過程中，包括一處或若干處）概率算法在運(yùn)行過程中，包括一處或若干處隨隨機(jī)選擇機(jī)選擇，根據(jù)隨機(jī)值來決定算法的運(yùn)行；，根據(jù)隨機(jī)值來決定算法的運(yùn)行；（3）概率算法的結(jié)果）概率算法的結(jié)果不能保證一定是正確不能保證一定是正確的，但可的，但可以限定其以限定其出錯概率出錯概率；（4）概率算法在不同的運(yùn)行中，對于相同的輸入實）概率算法在不同的運(yùn)行中，對于相同的輸入實例可以有例可以有不同的結(jié)果不同的結(jié)果，因此，對于相同的輸入實例，因此，對于相同的輸入實例，概率算法的概率算法的執(zhí)行執(zhí)行時間可能不同時間可能不同。同一輸入實例運(yùn)行同一概率算法求解兩次

10、可能得到完同一輸入實例運(yùn)行同一概率算法求解兩次可能得到完全不同的效果（結(jié)果和所需時間），所以一旦概率算法失敗全不同的效果（結(jié)果和所需時間），所以一旦概率算法失敗了，只需了，只需重啟算法重啟算法又有成功的希望。另外運(yùn)行幾次概率算法，又有成功的希望。另外運(yùn)行幾次概率算法，有可能得到幾個不同的答案。有可能得到幾個不同的答案。算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社 對于確定性算法，通常分析在平均情況下以對于確定性算法，通常分析在平均情況下以及最壞情況下的時間復(fù)雜性。對于概率算法，通及最壞情況下的時間復(fù)雜性。對于概率算法，通常分析在平均情況下以及最壞情況下的常分析在平均情況下以及最壞情

11、況下的期望期望時間時間復(fù)雜性，即由概率算法反復(fù)運(yùn)行同一輸入實例所復(fù)雜性，即由概率算法反復(fù)運(yùn)行同一輸入實例所得的平均運(yùn)行時間。得的平均運(yùn)行時間。 概率算法的時間性能概率算法的時間性能v需要強(qiáng)調(diào)的是，需要強(qiáng)調(diào)的是，“隨機(jī)隨機(jī)”并不意味著并不意味著“隨意隨意”。如手工運(yùn)行。如手工運(yùn)行算法，可通過擲骰子來得到一個隨機(jī)結(jié)果，在計算機(jī)中則通算法，可通過擲骰子來得到一個隨機(jī)結(jié)果，在計算機(jī)中則通過隨機(jī)數(shù)發(fā)生器來實現(xiàn)。過隨機(jī)數(shù)發(fā)生器來實現(xiàn)。算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社11.1.2 隨機(jī)數(shù)發(fā)生器隨機(jī)數(shù)發(fā)生器 目前，在計算機(jī)上產(chǎn)生隨機(jī)數(shù)還是一個難題，因為在目前，在計算機(jī)上產(chǎn)生隨機(jī)數(shù)還是一

12、個難題，因為在原理上，這個問題只能近似解決。原理上，這個問題只能近似解決。 計算機(jī)中產(chǎn)生隨機(jī)數(shù)的方法通常采用線性同余法，產(chǎn)計算機(jī)中產(chǎn)生隨機(jī)數(shù)的方法通常采用線性同余法，產(chǎn)生的隨機(jī)數(shù)序列為生的隨機(jī)數(shù)序列為a0, a1, , an，滿足：，滿足： （式（式12.1） 其中，其中，b0，c0，m0，dm。d稱為隨機(jī)數(shù)發(fā)生器的稱為隨機(jī)數(shù)發(fā)生器的隨機(jī)種子（隨機(jī)種子（Random Seed），當(dāng)），當(dāng)b、c和和m的值確定后，給定的值確定后，給定一個隨機(jī)種子，由式一個隨機(jī)種子，由式12.1產(chǎn)生的隨機(jī)數(shù)序列也就確定了。產(chǎn)生的隨機(jī)數(shù)序列也就確定了。, 2 , 1mod)(10nmcbaadann算法設(shè)計與分析算法

13、設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社 計算機(jī)語言提供的隨機(jī)數(shù)發(fā)生器，一般會輸出一個分布計算機(jī)語言提供的隨機(jī)數(shù)發(fā)生器，一般會輸出一個分布在開區(qū)間（在開區(qū)間（0, 1）上的隨機(jī)小數(shù)，并且需要一個隨機(jī)種子，）上的隨機(jī)小數(shù)，并且需要一個隨機(jī)種子，這個隨機(jī)種子可以是這個隨機(jī)種子可以是系統(tǒng)當(dāng)前的日期或時間系統(tǒng)當(dāng)前的日期或時間。下面給出利用。下面給出利用C+語言中的隨機(jī)函數(shù)語言中的隨機(jī)函數(shù)rand產(chǎn)生的分布在任意區(qū)間產(chǎn)生的分布在任意區(qū)間a, b上的上的隨機(jī)數(shù)算法。隨機(jī)數(shù)算法。算法12.1隨機(jī)數(shù)發(fā)生器 int Random(int a, int b) return rand( )%(b-a)+a; /ran

14、d( )產(chǎn)生(0, 32767)之間的隨機(jī)整數(shù) 算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社12.2 舍伍德舍伍德(Sherwood)型概率算法型概率算法 分析確定性算法在平均情況下的時間復(fù)雜性分析確定性算法在平均情況下的時間復(fù)雜性時，通常假定算法的輸入實例滿足某一特定的概時，通常假定算法的輸入實例滿足某一特定的概率分布。率分布。 事實上，很多算法對于不同的輸入實例，其事實上，很多算法對于不同的輸入實例，其運(yùn)行時間差別很大。此時，可以采用舍伍德型概運(yùn)行時間差別很大。此時，可以采用舍伍德型概率算法來率算法來消除消除算法的時間復(fù)雜性與輸入實例間的算法的時間復(fù)雜性與輸入實例間的這種聯(lián)系。

15、這種聯(lián)系。算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社算法12.2隨機(jī)洗牌 void RandomShuffle(int n, int r ) for (i=0; in; i+) j=Random(0, n-i-1); rirj; /交換ri和rj 如果一個確定性算法無法直接改造成舍伍德型概率算法，如果一個確定性算法無法直接改造成舍伍德型概率算法，可借助于隨機(jī)預(yù)處理技術(shù)，即不改變原有的確定性算法，可借助于隨機(jī)預(yù)處理技術(shù)，即不改變原有的確定性算法，僅對其輸入實例隨機(jī)排列（稱為僅對其輸入實例隨機(jī)排列（稱為洗牌洗牌）。假設(shè)輸入實例為）。假設(shè)輸入實例為整型，下面的隨機(jī)洗牌算法可在線性時間實

16、現(xiàn)對輸入實例整型，下面的隨機(jī)洗牌算法可在線性時間實現(xiàn)對輸入實例的隨機(jī)排列。的隨機(jī)排列。 算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社 舍伍德型概率算法總能求得問題的一個解，并舍伍德型概率算法總能求得問題的一個解，并且所求得的解總是正確的。但與其相對應(yīng)的確定性且所求得的解總是正確的。但與其相對應(yīng)的確定性算法相比，舍伍德型概率算法的平均時間復(fù)雜性沒算法相比，舍伍德型概率算法的平均時間復(fù)雜性沒有改進(jìn)。換言之，舍伍德型概率算法不是避免算法有改進(jìn)。換言之，舍伍德型概率算法不是避免算法的最壞情況行為，而是的最壞情況行為，而是設(shè)法消除了算法的不同輸入設(shè)法消除了算法的不同輸入實例對算法時間性能的影

17、響實例對算法時間性能的影響，對所有輸入實例而言，對所有輸入實例而言，舍伍德型概率算法的運(yùn)行時間相對比較均勻，其時舍伍德型概率算法的運(yùn)行時間相對比較均勻，其時間復(fù)雜性與原有的確定性算法在平均情況下的時間間復(fù)雜性與原有的確定性算法在平均情況下的時間復(fù)雜性相當(dāng)。復(fù)雜性相當(dāng)。 算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社12.2.1 快速排序快速排序 快速排序算法的關(guān)鍵在于一次劃分中選擇合適快速排序算法的關(guān)鍵在于一次劃分中選擇合適的軸值作為劃分的基準(zhǔn)，如果軸值是序列中最小的軸值作為劃分的基準(zhǔn)，如果軸值是序列中最小（或最大）記錄，則一次劃分后，由軸值分割得到（或最大）記錄，則一次劃分后，由軸

18、值分割得到的兩個子序列不均衡，使得快速排序的時間性能降的兩個子序列不均衡，使得快速排序的時間性能降低。低。舍伍德型概率算法在一次劃分之前，根據(jù)舍伍德型概率算法在一次劃分之前，根據(jù)隨隨機(jī)數(shù)機(jī)數(shù)在待劃分序列中隨機(jī)確定一個記錄作為軸值，在待劃分序列中隨機(jī)確定一個記錄作為軸值，并把它與第一個記錄交換，則一次劃分后得到期望并把它與第一個記錄交換，則一次劃分后得到期望均衡的兩個子序列，從而使算法的行為不受待排序均衡的兩個子序列，從而使算法的行為不受待排序序列的不同輸入實例的影響，序列的不同輸入實例的影響，使快速排序在最壞情使快速排序在最壞情況下的時間性能趨近于平均情況的時間性能況下的時間性能趨近于平均情況

19、的時間性能。算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社一次劃分結(jié)果一次劃分結(jié)果 6 13 192331 35 28初始鍵值序列初始鍵值序列 6 13 19 23 31 35 58圖圖10.1 一次劃分引入隨機(jī)選擇的示例一次劃分引入隨機(jī)選擇的示例一次劃分結(jié)果一次劃分結(jié)果 613 19 23 31 35 58初始鍵值序列初始鍵值序列 6 13 19 23 31 35 58隨機(jī)選擇一個隨機(jī)選擇一個 23 13 19 6 31 35 58記錄與記錄與6交換交換(a) 以最小值以最小值6為軸值，劃分不均衡為軸值，劃分不均衡(b) 隨機(jī)選擇軸值，劃分均衡隨機(jī)選擇軸值，劃分均衡算法設(shè)計與分析算

20、法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社算法算法12.3隨機(jī)隨機(jī)快速排序快速排序 void QuickSort (int r , int low, int high) if (low0。在更強(qiáng)的意義下，要求存在一個正的常數(shù)。在更強(qiáng)的意義下，要求存在一個正的常數(shù)，使得對于所有的輸入實例，使得對于所有的輸入實例x均有均有p(x)。由于。由于p(x)，所以，只要有足夠的時間，對任何輸入實，所以，只要有足夠的時間，對任何輸入實例例x，拉斯維加斯型概率算法總能找到問題的一個，拉斯維加斯型概率算法總能找到問題的一個解。換言之，拉斯維加斯型概率算法找到正確解的解。換言之，拉斯維加斯型概率算法找到正確解的概率

21、隨著計算時間的增加而提高。概率隨著計算時間的增加而提高。 算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社12.3.1 八皇后問題八皇后問題 八皇后問題是在八皇后問題是在88的棋盤上擺放八個皇后，的棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上。一行、同一列或同一斜線上。 對于八皇后問題的任何一個解而言，每一個皇對于八皇后問題的任何一個解而言，每一個皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更像是隨機(jī)放置的。由此想到拉斯維加斯型概率算更像是隨機(jī)放置的。由

22、此想到拉斯維加斯型概率算法：在棋盤上相繼的各行中隨機(jī)地放置皇后，并使法：在棋盤上相繼的各行中隨機(jī)地放置皇后，并使新放置的皇后與已放置的皇后互不攻擊，直至八個新放置的皇后與已放置的皇后互不攻擊，直至八個皇后均已相容地放置好，皇后均已相容地放置好，或下一個皇后沒有可放置或下一個皇后沒有可放置的位置的位置。 算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社 由于棋盤的每一行上可以而且必須放置一個皇后，所由于棋盤的每一行上可以而且必須放置一個皇后，所以八皇后問題的可能解用一個向量以八皇后問題的可能解用一個向量X=(x1, x2, , x8)表示，表示，其中，其中，1xi8并且并且1i8，即第，

23、即第i個皇后放置在第個皇后放置在第i行第行第xi列上。列上。由于兩個皇后不能位于同一列上，所以，解向量由于兩個皇后不能位于同一列上，所以，解向量X必須滿必須滿足約束條件：足約束條件： xixj （式（式12.2） 若兩個皇后擺放的位置分別是若兩個皇后擺放的位置分別是(i, xi)和和(j, xj)，在棋盤上，在棋盤上斜率為斜率為-1的斜線上，滿足條件的斜線上，滿足條件i-j= xi-xj，在棋盤上斜率為，在棋盤上斜率為1的斜線上，滿足條件的斜線上，滿足條件ij= xixj，綜合兩種情況，由于兩，綜合兩種情況，由于兩個皇后不能位于同一斜線上，所以，解向量個皇后不能位于同一斜線上，所以，解向量X必

24、須滿足約必須滿足約束條件：束條件： |i-xi|j-xj| （式（式12.3） 滿足式滿足式12.2和式和式12.3的向量的向量X=(x1, x2, , xi)表示已放置表示已放置的的i個皇后（個皇后（1i8）互不攻擊，也就是不發(fā)生沖突。）互不攻擊，也就是不發(fā)生沖突。 算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社算法算法12.5八皇后問題八皇后問題 1. 將數(shù)組將數(shù)組x8初始化為初始化為0；試探次數(shù)；試探次數(shù)count初始化為初始化為0； 2for (i=1; i=8; i+) 2.1 產(chǎn)生一個產(chǎn)生一個1, 8 的隨機(jī)數(shù)的隨機(jī)數(shù)j； 2.2 count=count+1，進(jìn)行第，進(jìn)行

25、第count次試探；次試探； 2.3 若皇后若皇后i放置在位置放置在位置j不發(fā)生沖突，不發(fā)生沖突， 則則xi=j；count=0；轉(zhuǎn)步驟；轉(zhuǎn)步驟2放置下一個皇后；放置下一個皇后； 2.4 若若(count= =8)，則無法放置皇后，則無法放置皇后i，算法運(yùn)行失敗；，算法運(yùn)行失?。?否則，轉(zhuǎn)步驟否則，轉(zhuǎn)步驟2.1重新放置皇后重新放置皇后i； 3. 將元素將元素x1x8作為八皇后問題的一個解輸出；作為八皇后問題的一個解輸出； 拉斯維加斯型概率算法通過反復(fù)調(diào)用算法拉斯維加斯型概率算法通過反復(fù)調(diào)用算法12.5，直至得到八皇后問題的一個解。直至得到八皇后問題的一個解。算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)

26、出版社清華大學(xué)出版社 如果將上述隨機(jī)放置策略與如果將上述隨機(jī)放置策略與回溯法回溯法相結(jié)合，則會獲相結(jié)合，則會獲得更好的效果?？梢韵仍谄灞P的若干行中隨機(jī)地放置相得更好的效果?？梢韵仍谄灞P的若干行中隨機(jī)地放置相容的皇后，然后在其他行中用回溯法繼續(xù)放置，直至找容的皇后，然后在其他行中用回溯法繼續(xù)放置，直至找到一個解或宣告失敗。到一個解或宣告失敗。 在棋盤中隨機(jī)放置的皇后越多，回溯法搜索所需的在棋盤中隨機(jī)放置的皇后越多，回溯法搜索所需的時間就越少，但失敗的概率也就越大時間就越少，但失敗的概率也就越大。 例如八皇后問題，隨機(jī)地放置兩個皇后再采用回溯例如八皇后問題，隨機(jī)地放置兩個皇后再采用回溯法比完全采用

27、回溯法快大約兩倍；隨機(jī)地放置三個皇后法比完全采用回溯法快大約兩倍；隨機(jī)地放置三個皇后再采用回溯法比完全采用回溯法快大約一倍；而所有的再采用回溯法比完全采用回溯法快大約一倍；而所有的皇后都隨機(jī)放置比完全采用回溯法慢大約一倍?；屎蠖茧S機(jī)放置比完全采用回溯法慢大約一倍。 很容易解釋這個現(xiàn)象：很容易解釋這個現(xiàn)象：不能忽略產(chǎn)生隨機(jī)數(shù)所需的不能忽略產(chǎn)生隨機(jī)數(shù)所需的時間時間，當(dāng)隨機(jī)放置所有的皇后時，八皇后問題的求解大，當(dāng)隨機(jī)放置所有的皇后時，八皇后問題的求解大約有約有70%的時間都用在了產(chǎn)生隨機(jī)數(shù)上。的時間都用在了產(chǎn)生隨機(jī)數(shù)上。 算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社12.4 蒙特卡羅蒙特

28、卡羅(Monte Carlo)型概率算法型概率算法 對于許多問題來說，近似解毫無意義。如布對于許多問題來說，近似解毫無意義。如布爾型的解，或象整數(shù)因子劃分問題的解必須是準(zhǔn)爾型的解，或象整數(shù)因子劃分問題的解必須是準(zhǔn)確的。蒙特卡羅型概率算法用于求問題的準(zhǔn)確解。確的。蒙特卡羅型概率算法用于求問題的準(zhǔn)確解。 因為屬于概率算法，該算法偶爾也會出錯，因為屬于概率算法，該算法偶爾也會出錯，但無論任何輸入實例，總能以很高的概率找到一但無論任何輸入實例，總能以很高的概率找到一個正確解。求得正確解的概率依賴于算法所用的個正確解。求得正確解的概率依賴于算法所用的時間，所用的時間越多，得到正確解的概率就越時間，所用的

29、時間越多，得到正確解的概率就越高。高。算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社12.4 蒙特卡羅蒙特卡羅(Monte Carlo)型概率算法型概率算法蒙特卡羅型概率算法是蒙特卡羅型概率算法是P正確：如果該算法對于問正確：如果該算法對于問題的任一輸入實例得到正確解的概率不小于題的任一輸入實例得到正確解的概率不小于P（P是屬于是屬于(1/2, 1)間的實數(shù)）。間的實數(shù)）。蒙特卡羅型概率算法是一致：如果對于同一輸入蒙特卡羅型概率算法是一致：如果對于同一輸入實例，該算法不會給出兩個不同的正確解。實例，該算法不會給出兩個不同的正確解。蒙特卡羅型概率算法的參數(shù)除了問題輸入實例蒙特卡羅型概率

30、算法的參數(shù)除了問題輸入實例I外，外，還有描述錯誤解可接受概率的參數(shù)，其時間復(fù)雜還有描述錯誤解可接受概率的參數(shù)，其時間復(fù)雜性由函數(shù)性由函數(shù)T(n, )描述。描述。算法設(shè)計與分析算法設(shè)計與分析清華大學(xué)出版社清華大學(xué)出版社12.4.1 主元素問題主元素問題 設(shè)設(shè)Tn是一個含有是一個含有n個元素的數(shù)組，個元素的數(shù)組，x是數(shù)組是數(shù)組T的的一個元素，如果數(shù)組中有一個元素，如果數(shù)組中有一半以上一半以上的元素與的元素與x相同，相同，則稱元素則稱元素x是數(shù)組是數(shù)組T的主元素（的主元素（Major Element）。）。例如，在數(shù)組例如，在數(shù)組T7=3, 2, 3, 2, 3, 3, 5中，元素中，元素3就是主就是主元素。元素。求解主元素的簡單方法是統(tǒng)計每個元素在數(shù)組中出現(xiàn)求解主元素的簡