第12章概率算法

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

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

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

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

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

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

7、么采用概率算法就可以快速找到問題的解。，那么采用概率算法就可以快速找到問題的解。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 例如，判斷表達(dá)式例如，判斷表達(dá)式f(x1, x2, , xn)是否恒等于是否恒等于0。概率算法首先生成一個(gè)隨機(jī)概率算法首先生成一個(gè)隨機(jī)n元向量元向量(r1, r2, , rn)，并計(jì)算并計(jì)算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ī)向量越多，這個(gè)結(jié)果出錯(cuò)的結(jié)論，并且測試的隨機(jī)向量越多，這個(gè)結(jié)果出錯(cuò)的可能性就越小。的可能性就越小。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社一般情況下，概率算法具有以下基本特征：一般情況下，概率算法具有以下基本特征：（1）概率算法的輸入包括）概率算法的輸入包括兩部分兩部分，一部分是，一部分是原問題原問題的輸入的輸入，另一部分是一個(gè)供算法進(jìn)行隨機(jī)選擇的，另一部

9、分是一個(gè)供算法進(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é)果不能保證一定是正確不能保證一定是正確的，但可的，但可以限定其以限定其出錯(cuò)概率出錯(cuò)概率；（4）概率算法在不同的運(yùn)行中，對(duì)于相同的輸入實(shí)）概率算法在不同的運(yùn)行中，對(duì)于相同的輸入實(shí)例可以有例可以有不同的結(jié)果不同的結(jié)果，因此，對(duì)于相同的輸入實(shí)例，因此，對(duì)于相同的輸入實(shí)例，概率算法的概率算法的執(zhí)行執(zhí)行時(shí)間可能不同時(shí)間可能不同。同一輸入實(shí)例運(yùn)行同一概率算法求解兩次

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

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

12、個(gè)難題，因?yàn)樵谠砩?，這個(gè)問題只能近似解決。原理上，這個(gè)問題只能近似解決。 計(jì)算機(jī)中產(chǎn)生隨機(jī)數(shù)的方法通常采用線性同余法，產(chǎn)計(jì)算機(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的值確定后，給定的值確定后，給定一個(gè)隨機(jī)種子，由式一個(gè)隨機(jī)種子，由式12.1產(chǎn)生的隨機(jī)數(shù)序列也就確定了。產(chǎn)生的隨機(jī)數(shù)序列也就確定了。, 2 , 1mod)(10nmcbaadann算法設(shè)計(jì)與分析算法

13、設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 計(jì)算機(jī)語言提供的隨機(jī)數(shù)發(fā)生器，一般會(huì)輸出一個(gè)分布計(jì)算機(jī)語言提供的隨機(jī)數(shù)發(fā)生器，一般會(huì)輸出一個(gè)分布在開區(qū)間（在開區(qū)間（0, 1）上的隨機(jī)小數(shù)，并且需要一個(gè)隨機(jī)種子，）上的隨機(jī)小數(shù)，并且需要一個(gè)隨機(jī)種子，這個(gè)隨機(jī)種子可以是這個(gè)隨機(jī)種子可以是系統(tǒng)當(dāng)前的日期或時(shí)間系統(tǒng)當(dāng)前的日期或時(shí)間。下面給出利用。下面給出利用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è)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社12.2 舍伍德舍伍德(Sherwood)型概率算法型概率算法 分析確定性算法在平均情況下的時(shí)間復(fù)雜性分析確定性算法在平均情況下的時(shí)間復(fù)雜性時(shí)，通常假定算法的輸入實(shí)例滿足某一特定的概時(shí)，通常假定算法的輸入實(shí)例滿足某一特定的概率分布。率分布。 事實(shí)上，很多算法對(duì)于不同的輸入實(shí)例，其事實(shí)上，很多算法對(duì)于不同的輸入實(shí)例，其運(yùn)行時(shí)間差別很大。此時(shí)，可以采用舍伍德型概運(yùn)行時(shí)間差別很大。此時(shí)，可以采用舍伍德型概率算法來率算法來消除消除算法的時(shí)間復(fù)雜性與輸入實(shí)例間的算法的時(shí)間復(fù)雜性與輸入實(shí)例間的這種聯(lián)系。

15、這種聯(lián)系。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(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 如果一個(gè)確定性算法無法直接改造成舍伍德型概率算法，如果一個(gè)確定性算法無法直接改造成舍伍德型概率算法，可借助于隨機(jī)預(yù)處理技術(shù)，即不改變?cè)械拇_定性算法，可借助于隨機(jī)預(yù)處理技術(shù)，即不改變?cè)械拇_定性算法，僅對(duì)其輸入實(shí)例隨機(jī)排列（稱為僅對(duì)其輸入實(shí)例隨機(jī)排列（稱為洗牌洗牌）。假設(shè)輸入實(shí)例為）。假設(shè)輸入實(shí)例為整型，下面的隨機(jī)洗牌算法可在線性時(shí)間實(shí)

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

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

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

19、的時(shí)間性能。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(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ī)選擇一個(gè)隨機(jī)選擇一個(gè) 23 13 19 6 31 35 58記錄與記錄與6交換交換(a) 以最小值以最小值6為軸值，劃分不均衡為軸值，劃分不均衡(b) 隨機(jī)選擇軸值，劃分均衡隨機(jī)選擇軸值，劃分均衡算法設(shè)計(jì)與分析算

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

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

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

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

24、須滿足約必須滿足約束條件：束條件： |i-xi|j-xj| （式（式12.3） 滿足式滿足式12.2和式和式12.3的向量的向量X=(x1, x2, , xi)表示已放置表示已放置的的i個(gè)皇后（個(gè)皇后（1i8）互不攻擊，也就是不發(fā)生沖突。）互不攻擊，也就是不發(fā)生沖突。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法算法12.5八皇后問題八皇后問題 1. 將數(shù)組將數(shù)組x8初始化為初始化為0；試探次數(shù)；試探次數(shù)count初始化為初始化為0； 2for (i=1; i=8; i+) 2.1 產(chǎn)生一個(gè)產(chǎn)生一個(gè)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放置下一個(gè)皇后；放置下一個(gè)皇后； 2.4 若若(count= =8)，則無法放置皇后，則無法放置皇后i，算法運(yùn)行失??；，算法運(yùn)行失??； 否則，轉(zhuǎn)步驟否則，轉(zhuǎn)步驟2.1重新放置皇后重新放置皇后i； 3. 將元素將元素x1x8作為八皇后問題的一個(gè)解輸出；作為八皇后問題的一個(gè)解輸出； 拉斯維加斯型概率算法通過反復(fù)調(diào)用算法拉斯維加斯型概率算法通過反復(fù)調(diào)用算法12.5，直至得到八皇后問題的一個(gè)解。直至得到八皇后問題的一個(gè)解。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)

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

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

28、卡羅(Monte Carlo)型概率算法型概率算法 對(duì)于許多問題來說，近似解毫無意義。如布對(duì)于許多問題來說，近似解毫無意義。如布爾型的解，或象整數(shù)因子劃分問題的解必須是準(zhǔn)爾型的解，或象整數(shù)因子劃分問題的解必須是準(zhǔn)確的。蒙特卡羅型概率算法用于求問題的準(zhǔn)確解。確的。蒙特卡羅型概率算法用于求問題的準(zhǔn)確解。 因?yàn)閷儆诟怕仕惴?，該算法偶爾也?huì)出錯(cuò)，因?yàn)閷儆诟怕仕惴ǎ撍惴ㄅ紶栆矔?huì)出錯(cuò)，但無論任何輸入實(shí)例，總能以很高的概率找到一但無論任何輸入實(shí)例，總能以很高的概率找到一個(gè)正確解。求得正確解的概率依賴于算法所用的個(gè)正確解。求得正確解的概率依賴于算法所用的時(shí)間，所用的時(shí)間越多，得到正確解的概率就越時(shí)間，所用的

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

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