算法設(shè)計(jì)與分析-概率算法經(jīng)典講解

1、1第一部分第一部分概率算法概率算法2Ch.1 緒論緒論1. 故事：故事：想象自己是神化故事的主人公，你想象自己是神化故事的主人公，你有一張不易懂的地圖，上面描述了一處寶有一張不易懂的地圖，上面描述了一處寶藏的藏寶地點(diǎn)。經(jīng)分析你能確定最有可能藏的藏寶地點(diǎn)。經(jīng)分析你能確定最有可能的兩個(gè)地點(diǎn)是藏寶地點(diǎn)，但二者相距甚遠(yuǎn)。的兩個(gè)地點(diǎn)是藏寶地點(diǎn)，但二者相距甚遠(yuǎn)。假設(shè)你如果已到達(dá)其中一處，就立即知道假設(shè)你如果已到達(dá)其中一處，就立即知道該處是否為藏寶地點(diǎn)。你到達(dá)兩處之一地該處是否為藏寶地點(diǎn)。你到達(dá)兩處之一地點(diǎn)及從其中一處到另一處的距離是點(diǎn)及從其中一處到另一處的距離是5天的天的行程。進(jìn)一步假設(shè)有一條惡龍，每晚光

2、顧行程。進(jìn)一步假設(shè)有一條惡龍，每晚光顧寶藏并從中拿走一部分財(cái)寶。假設(shè)你取寶寶藏并從中拿走一部分財(cái)寶。假設(shè)你取寶藏的方案有兩種：藏的方案有兩種：1.1 引言引言3 方案方案1. 花花4天的時(shí)間計(jì)算出準(zhǔn)確的藏寶地點(diǎn)，然天的時(shí)間計(jì)算出準(zhǔn)確的藏寶地點(diǎn)，然后出發(fā)尋寶，一旦出發(fā)不能重新計(jì)算后出發(fā)尋寶，一旦出發(fā)不能重新計(jì)算 方案方案2. 有一個(gè)小精靈告訴你地圖的秘密，但你有一個(gè)小精靈告訴你地圖的秘密，但你必須付給他報(bào)酬，相當(dāng)于龍必須付給他報(bào)酬，相當(dāng)于龍3晚上拿走的財(cái)寶晚上拿走的財(cái)寶 Prob 1.1.1 若忽略可能的冒險(xiǎn)和出發(fā)尋寶的代若忽略可能的冒險(xiǎn)和出發(fā)尋寶的代價(jià)，你是否接受小精靈的幫助？?jī)r(jià)，你是否接受小

3、精靈的幫助？ 顯然，應(yīng)該接受小精靈的幫助，因?yàn)槟阒恍栾@然，應(yīng)該接受小精靈的幫助，因?yàn)槟阒恍杞o出給出3晚上被盜竊的財(cái)寶量，否則你將失去晚上被盜竊的財(cái)寶量，否則你將失去4晚被晚被盜財(cái)寶量。盜財(cái)寶量。 但是，但是，若冒險(xiǎn)，你可能做得更好！若冒險(xiǎn)，你可能做得更好！1.1 引言引言4 設(shè)設(shè)x是你決定之前當(dāng)日的寶藏價(jià)值，設(shè)是你決定之前當(dāng)日的寶藏價(jià)值，設(shè)y是惡龍每是惡龍每晚盜走的寶藏價(jià)值，并設(shè)晚盜走的寶藏價(jià)值，并設(shè)x9y 方案方案1：4天計(jì)算確定地址，行程天計(jì)算確定地址，行程5天，你得到的寶天，你得到的寶藏價(jià)值為：藏價(jià)值為：x-9y 方案方案2：3y付給精靈，行程付給精靈，行程5天失去天失去5y，你得到的，

4、你得到的寶藏價(jià)值為：寶藏價(jià)值為：x-8y 方案方案3：投硬幣決定先到一處，失敗后到另一處投硬幣決定先到一處，失敗后到另一處(冒冒險(xiǎn)方案險(xiǎn)方案) 一次成功所得：一次成功所得：x-5y，機(jī)會(huì)，機(jī)會(huì)1/2 二次成功所得：二次成功所得：x-10y，機(jī)會(huì)，機(jī)會(huì)1/21.1 引言引言期望贏利：期望贏利：x-7.5y52. 意義意義 該故事告訴我們：當(dāng)一個(gè)算法面臨某種選擇該故事告訴我們：當(dāng)一個(gè)算法面臨某種選擇時(shí)，有時(shí)隨機(jī)選擇比耗時(shí)做最優(yōu)選擇更好，尤其時(shí)，有時(shí)隨機(jī)選擇比耗時(shí)做最優(yōu)選擇更好，尤其是當(dāng)最優(yōu)選擇所花的時(shí)間大于隨機(jī)選擇的平均時(shí)是當(dāng)最優(yōu)選擇所花的時(shí)間大于隨機(jī)選擇的平均時(shí)間的時(shí)侯間的時(shí)侯 顯然，概率算法只

5、能是期望的時(shí)間更有效，顯然，概率算法只能是期望的時(shí)間更有效，但它有可能遭受到最壞的可能性。但它有可能遭受到最壞的可能性。63. 期望時(shí)間和平均時(shí)間的區(qū)別期望時(shí)間和平均時(shí)間的區(qū)別v 確定算法的平均執(zhí)行時(shí)間確定算法的平均執(zhí)行時(shí)間 輸入規(guī)模一定的所有輸入實(shí)例是等概率出現(xiàn)時(shí)，算法輸入規(guī)模一定的所有輸入實(shí)例是等概率出現(xiàn)時(shí)，算法的平均執(zhí)行時(shí)間。的平均執(zhí)行時(shí)間。v 概率算法的期望執(zhí)行時(shí)間概率算法的期望執(zhí)行時(shí)間 反復(fù)解同一個(gè)輸入實(shí)例所花的平均執(zhí)行時(shí)間。反復(fù)解同一個(gè)輸入實(shí)例所花的平均執(zhí)行時(shí)間。 因此，對(duì)概率算法可以討論如下兩種期望時(shí)間因此，對(duì)概率算法可以討論如下兩種期望時(shí)間 平均的期望時(shí)間平均的期望時(shí)間：所有輸

6、入實(shí)例上平均的期望執(zhí)行時(shí)：所有輸入實(shí)例上平均的期望執(zhí)行時(shí)間間 最壞的期望時(shí)間最壞的期望時(shí)間：最壞的輸入實(shí)例上的期望執(zhí)行時(shí)間：最壞的輸入實(shí)例上的期望執(zhí)行時(shí)間74. 例子例子 快速排序中的隨機(jī)劃分快速排序中的隨機(jī)劃分要求學(xué)生寫一算法，由老師給出輸入實(shí)例，按運(yùn)行時(shí)間打分，要求學(xué)生寫一算法，由老師給出輸入實(shí)例，按運(yùn)行時(shí)間打分，大部分學(xué)生均不敢用簡(jiǎn)單的劃分，運(yùn)行時(shí)間在大部分學(xué)生均不敢用簡(jiǎn)單的劃分，運(yùn)行時(shí)間在1500-2600ms，三個(gè)學(xué)生用概率的方法劃分，運(yùn)行時(shí)間平均為三個(gè)學(xué)生用概率的方法劃分，運(yùn)行時(shí)間平均為300ms。 8皇后問題皇后問題系統(tǒng)的方法放置皇后系統(tǒng)的方法放置皇后(回溯法回溯法)較合適，找出

7、所有較合適，找出所有92個(gè)解個(gè)解 O(2n)，若只找若只找92個(gè)其中的任何一個(gè)解可在線性時(shí)間內(nèi)完成個(gè)其中的任何一個(gè)解可在線性時(shí)間內(nèi)完成O(n)。 隨機(jī)法：隨機(jī)法：隨機(jī)地放置若干皇后能夠改進(jìn)回溯法，特別是當(dāng)隨機(jī)地放置若干皇后能夠改進(jìn)回溯法，特別是當(dāng)n較較大時(shí)大時(shí) 判斷大整數(shù)是否為素?cái)?shù)判斷大整數(shù)是否為素?cái)?shù)確定算法無法在可行的時(shí)間內(nèi)判斷一個(gè)數(shù)百位十進(jìn)制數(shù)是否素確定算法無法在可行的時(shí)間內(nèi)判斷一個(gè)數(shù)百位十進(jìn)制數(shù)是否素?cái)?shù)，否則密碼就不安全。數(shù)，否則密碼就不安全。 概率算法將有所作為：若能接受一個(gè)任意小的錯(cuò)誤的概率概率算法將有所作為：若能接受一個(gè)任意小的錯(cuò)誤的概率85. 概率算法的特點(diǎn)概率算法的特點(diǎn) (1)

8、 不可再現(xiàn)性不可再現(xiàn)性 在同一個(gè)輸入實(shí)例上，每次執(zhí)行結(jié)果不盡相同，例在同一個(gè)輸入實(shí)例上，每次執(zhí)行結(jié)果不盡相同，例如如 N-皇后問題皇后問題概率算法運(yùn)行不同次將會(huì)找到不同的正確解概率算法運(yùn)行不同次將會(huì)找到不同的正確解 找一給定合數(shù)的非平凡因子找一給定合數(shù)的非平凡因子每次運(yùn)行的結(jié)果不盡相同，但確定算法每次運(yùn)行結(jié)果必每次運(yùn)行的結(jié)果不盡相同，但確定算法每次運(yùn)行結(jié)果必定相同定相同 (2) 分析困難分析困難 要求有概率論，統(tǒng)計(jì)學(xué)和數(shù)論的知識(shí)要求有概率論，統(tǒng)計(jì)學(xué)和數(shù)論的知識(shí)96. 約定約定 隨機(jī)函數(shù)隨機(jī)函數(shù)uniform：隨機(jī)隨機(jī)，均勻均勻，獨(dú)立獨(dú)立 設(shè)設(shè)a，b為實(shí)數(shù)，為實(shí)數(shù)，ab, uniform(a,

9、b) 返回返回x，a x b 設(shè)設(shè)i，j為整數(shù)，為整數(shù)，ij, uniform(i.j)=k, i k j 設(shè)設(shè)X是非空有限集，是非空有限集， uniform(X) X 10例例1：設(shè)設(shè)p是一個(gè)素?cái)?shù)，是一個(gè)素?cái)?shù)，a是一個(gè)整數(shù)滿足是一個(gè)整數(shù)滿足1a0 do if (j is odd) s sa mod p;a a2 mod p;j j div 2;return s;Draw (a, p) / 在在X中隨機(jī)取一元素中隨機(jī)取一元素j uniform(1.p-1);return ModularExponent(a, j, p); / 在在X中隨機(jī)取一元素中隨機(jī)取一元素12n 偽隨機(jī)數(shù)發(fā)生器偽隨機(jī)數(shù)發(fā)生

10、器在實(shí)用中不可能有真正的隨機(jī)數(shù)發(fā)生器，多數(shù)情況在實(shí)用中不可能有真正的隨機(jī)數(shù)發(fā)生器，多數(shù)情況下是用偽隨機(jī)數(shù)發(fā)生器代替。下是用偽隨機(jī)數(shù)發(fā)生器代替。大多數(shù)偽隨機(jī)數(shù)發(fā)生器是基于一對(duì)函數(shù)：大多數(shù)偽隨機(jī)數(shù)發(fā)生器是基于一對(duì)函數(shù)：S: X X, 這里這里X足夠大，它是種子的值域足夠大，它是種子的值域R: X Y, Y是偽隨機(jī)數(shù)函數(shù)的值域是偽隨機(jī)數(shù)函數(shù)的值域使用使用S獲得種子序列：獲得種子序列：x0=g, xi=S(xi-1), i0然后使用然后使用R R獲得偽隨機(jī)序列：獲得偽隨機(jī)序列：yi=R(xi), i 0該序列必然是周期性的，但只要該序列必然是周期性的，但只要S S和和R R選的合適，該選的合適，該周期

11、長(zhǎng)度會(huì)非常長(zhǎng)。周期長(zhǎng)度會(huì)非常長(zhǎng)。TC中可用中可用rand()和和srand(time), 用用GNU C更好更好131. 基本特征基本特征隨機(jī)決策隨機(jī)決策在同一實(shí)例上執(zhí)行兩次其結(jié)果可能不同在同一實(shí)例上執(zhí)行兩次其結(jié)果可能不同在同一實(shí)例上執(zhí)行兩次的時(shí)間亦可能不太相同在同一實(shí)例上執(zhí)行兩次的時(shí)間亦可能不太相同2. 分類分類Numerical, Monte Carlo, Las Vegas, Sherwood.很多人將所有概率算法很多人將所有概率算法(尤其是數(shù)字的概率算法尤其是數(shù)字的概率算法)稱為稱為Monte Carlo算法算法1.2 概率算法的分類概率算法的分類14 數(shù)字算法數(shù)字算法隨機(jī)性被最早用于

12、求數(shù)字問題的近似解隨機(jī)性被最早用于求數(shù)字問題的近似解例如，求一個(gè)系統(tǒng)中隊(duì)列的平均長(zhǎng)度的問題，確定算例如，求一個(gè)系統(tǒng)中隊(duì)列的平均長(zhǎng)度的問題，確定算法很難得到答案法很難得到答案l 概率算法獲得的答案一般是近似的，但通常算法執(zhí)行概率算法獲得的答案一般是近似的，但通常算法執(zhí)行的時(shí)間越長(zhǎng)，精度就越高，誤差就越小的時(shí)間越長(zhǎng)，精度就越高，誤差就越小l 使用的理由使用的理由 現(xiàn)實(shí)世界中的問題在原理上可能就不存在精確解現(xiàn)實(shí)世界中的問題在原理上可能就不存在精確解例如，實(shí)驗(yàn)數(shù)據(jù)本身就是近似的，一個(gè)無理數(shù)在計(jì)例如，實(shí)驗(yàn)數(shù)據(jù)本身就是近似的，一個(gè)無理數(shù)在計(jì)算機(jī)中只能近似地表示算機(jī)中只能近似地表示 精確解存在但無法在可行的

13、時(shí)間內(nèi)求得精確解存在但無法在可行的時(shí)間內(nèi)求得有時(shí)答案是以置信區(qū)間的形式給出的有時(shí)答案是以置信區(qū)間的形式給出的1.2 概率算法的分類概率算法的分類15 Monte Carlo算法算法 (MC算法算法)蒙特卡洛算法蒙特卡洛算法1945年由年由J. Von Neumann進(jìn)行核武模擬提出進(jìn)行核武模擬提出的。它是以概率和統(tǒng)計(jì)的理論與方法為基礎(chǔ)的一種數(shù)值計(jì)算的。它是以概率和統(tǒng)計(jì)的理論與方法為基礎(chǔ)的一種數(shù)值計(jì)算方法，它是雙重近似：一是用概率模型模擬近似的數(shù)值計(jì)算，方法，它是雙重近似：一是用概率模型模擬近似的數(shù)值計(jì)算，二是用偽隨機(jī)數(shù)模擬真正的隨機(jī)變量的樣本。二是用偽隨機(jī)數(shù)模擬真正的隨機(jī)變量的樣本。這里我們指

14、的這里我們指的MC算法是：算法是： 若問題只有若問題只有1個(gè)正確的解，而無近個(gè)正確的解，而無近似解的可能時(shí)使用似解的可能時(shí)使用MC算法算法例如，判定問題只有真或假兩種可能性，沒有近似解例如，判定問題只有真或假兩種可能性，沒有近似解 因式分解，我們不能說某數(shù)幾乎是一個(gè)因子因式分解，我們不能說某數(shù)幾乎是一個(gè)因子n 特點(diǎn)：特點(diǎn)：MC算法總是給出一個(gè)答案算法總是給出一個(gè)答案，但該答案未必正確，但該答案未必正確，成成功功(即答案是正確的即答案是正確的)的概率正比于算法執(zhí)行的時(shí)間的概率正比于算法執(zhí)行的時(shí)間n 缺點(diǎn)：缺點(diǎn)：一般不能有效地確定算法的答案是否正確一般不能有效地確定算法的答案是否正確1.2 概率算

15、法的分類概率算法的分類16 Las Vegas算法算法 (LV算法算法)LV算法絕不返回錯(cuò)誤的答案。算法絕不返回錯(cuò)誤的答案。n 特點(diǎn)：特點(diǎn)：獲得的答案必定正確獲得的答案必定正確，但有時(shí)它仍，但有時(shí)它仍根本就找不根本就找不到答案到答案。 和和MC算法一樣，成功的概率亦隨算法執(zhí)行時(shí)間增加而增算法一樣，成功的概率亦隨算法執(zhí)行時(shí)間增加而增加。無論輸入何種實(shí)例，只要算法在該實(shí)例上運(yùn)行足夠加。無論輸入何種實(shí)例，只要算法在該實(shí)例上運(yùn)行足夠的次數(shù)，則算法失敗的概率就任意小。的次數(shù)，則算法失敗的概率就任意小。 Sherwood算法算法Sherwood算法總是給出正確的答案。算法總是給出正確的答案。當(dāng)某些確定算法

16、解決一個(gè)特殊問題平均的時(shí)間比最壞時(shí)當(dāng)某些確定算法解決一個(gè)特殊問題平均的時(shí)間比最壞時(shí)間快得多時(shí)，我們可以使用間快得多時(shí)，我們可以使用Sherwood算法來算法來減少，甚減少，甚至是消除好的和壞的實(shí)例之間的差別至是消除好的和壞的實(shí)例之間的差別。1.2 概率算法的分類概率算法的分類17這類算法主要用于找到一個(gè)數(shù)字問題的近似解這類算法主要用于找到一個(gè)數(shù)字問題的近似解2.1 值計(jì)算值計(jì)算n實(shí)驗(yàn)：將實(shí)驗(yàn)：將n根飛鏢隨機(jī)投向一正方形的靶子，計(jì)算落入此正方根飛鏢隨機(jī)投向一正方形的靶子，計(jì)算落入此正方形的內(nèi)切圓中的飛鏢數(shù)目形的內(nèi)切圓中的飛鏢數(shù)目k。假定飛鏢擊中方形靶子任一點(diǎn)的概率相等假定飛鏢擊中方形靶子任一點(diǎn)的

17、概率相等(用計(jì)算機(jī)模擬比任用計(jì)算機(jī)模擬比任一飛鏢高手更能保證此假設(shè)成立一飛鏢高手更能保證此假設(shè)成立)設(shè)圓的半徑為設(shè)圓的半徑為r，面積，面積s1= r2； 方靶面積方靶面積s2=4r2由等概率假設(shè)可知落入圓中的飛鏢和正方形內(nèi)的飛鏢平均比為：由等概率假設(shè)可知落入圓中的飛鏢和正方形內(nèi)的飛鏢平均比為：由此知：由此知： Ch.2 數(shù)字概率算法數(shù)字概率算法2244krnr4 /4nk n k18n求求近似值的算法近似值的算法為簡(jiǎn)單起見，只以上圖的右上為簡(jiǎn)單起見，只以上圖的右上1/4象限為樣本象限為樣本Darts (n) k 0;for i 1 to n do x uniform(0, 1);y unifo

18、rm(0, 1); / 隨機(jī)產(chǎn)生點(diǎn)隨機(jī)產(chǎn)生點(diǎn)(x,y)if (x2 + y2 1) then k+; /圓內(nèi)圓內(nèi)return 4k/n;實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)結(jié)果： =3.141592654n = 1000萬萬: 3.140740, 3.142568 (2位精確位精確)n = 1億億: 3.141691, 3.141363 (3位精確位精確)n = 10億億: 3.141527, 3.141507 (4位精確位精確)2.1 值計(jì)算值計(jì)算19求求近似值的算法近似值的算法Ex.1 若將若將y uniform(0, 1) 改為改為 y x, 則上則上述的算法估計(jì)的值是什么？述的算法估計(jì)的值是什么？2.1 值計(jì)

19、算值計(jì)算20Monte Carlo積分積分(但不是指我們定義的但不是指我們定義的MC算法算法)1、概率算法概率算法1設(shè)設(shè)f: 0, 1 0, 1是一個(gè)連續(xù)函數(shù)，則由曲線是一個(gè)連續(xù)函數(shù)，則由曲線y=f(x), x軸軸, y軸和直線軸和直線x=1圍成的面積由下述積分給出：圍成的面積由下述積分給出：向單位面積的正方形內(nèi)投鏢向單位面積的正方形內(nèi)投鏢n次，落入陰影部分的鏢的次，落入陰影部分的鏢的數(shù)目為數(shù)目為k，則，則顯然，只要顯然，只要n足夠大足夠大2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)10( )Sf x dx/1kSSk nn/Sk n 211.概率算法概率算法1HitorMiss

20、 (f, n) k 0;for i 1 to n do x uniform(0, 1);y uniform(0, 1);if y f(x) then k+;return k/n;Note: 是是S/4的面積，的面積， =S, 2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)1201x dx12041x dx221. 概率算法概率算法1Ex2. 在機(jī)器上用在機(jī)器上用 估計(jì)估計(jì)值，給出不值，給出不同的同的n值及精度。值及精度。Ex3. 設(shè)設(shè)a, b, c和和d是實(shí)數(shù)，且是實(shí)數(shù)，且a b, c d, f:a, b c, d是一個(gè)連續(xù)函數(shù)，寫一概率算法計(jì)是一個(gè)連續(xù)函數(shù)，寫一概率算法計(jì)算積分：

21、算積分：注意，函數(shù)的參數(shù)是注意，函數(shù)的參數(shù)是a, b, c, d, n和和f, 其中其中f用函用函數(shù)指針實(shí)現(xiàn)，請(qǐng)選一連續(xù)函數(shù)做實(shí)驗(yàn)，并給出數(shù)指針實(shí)現(xiàn)，請(qǐng)選一連續(xù)函數(shù)做實(shí)驗(yàn)，并給出實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果。2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)12041x dx( )baf x dx231.概率算法概率算法1*Ex4. 設(shè)設(shè),是是(0,1)之間的常數(shù)，證明：之間的常數(shù)，證明：若若I是是 的正確值，的正確值，h h是由是由HitorMissHitorMiss算法返回的算法返回的值，則當(dāng)值，則當(dāng)n I(1-I)/2時(shí)有：時(shí)有：Prob|h-I| 1 上述的意義告訴我們：上述的意義告訴我

22、們：Prob|h-I| , 即：當(dāng)即：當(dāng)n I(1-I)/ 2時(shí)，算法的計(jì)算結(jié)果的絕對(duì)誤差超過時(shí)，算法的計(jì)算結(jié)果的絕對(duì)誤差超過的概率不超的概率不超過過，因此我們根據(jù)給定，因此我們根據(jù)給定和和可以確定算法迭代的次數(shù)可以確定算法迭代的次數(shù)解此問題時(shí)可用切比雪夫不等式，將解此問題時(shí)可用切比雪夫不等式，將I看作是數(shù)學(xué)期望?？醋魇菙?shù)學(xué)期望。2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)10( )f x dx22(1)11(1)44IInII 242.概率算法概率算法2更有效的概率算法是：更有效的概率算法是： 在積分區(qū)間上隨機(jī)均勻地產(chǎn)生點(diǎn)，求在積分區(qū)間上隨機(jī)均勻地產(chǎn)生點(diǎn)，求出這些點(diǎn)上的函數(shù)值的

23、算術(shù)平均值，再乘以區(qū)間的寬度：出這些點(diǎn)上的函數(shù)值的算術(shù)平均值，再乘以區(qū)間的寬度：Crude (f, n, a, b) sum 0;for i 1 to n do x uniform(a, b);sum sum + f(x);return (b-a)sum/n;2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)11( )()( ),nbiiaif x dxbaf xaxbn252. 概率算法概率算法2用用HitorMiss和和Crude運(yùn)行三次的結(jié)果為：運(yùn)行三次的結(jié)果為：假定假定 和和 存在，由算法求得的估算存在，由算法求得的估算值的方差反比于點(diǎn)數(shù)值的方差反比于點(diǎn)數(shù)n。當(dāng)。當(dāng)n足夠大時(shí)，

24、估計(jì)的分足夠大時(shí)，估計(jì)的分布近似為正態(tài)分布。布近似為正態(tài)分布。對(duì)于給定的迭代次數(shù)對(duì)于給定的迭代次數(shù)n，Crude算法的方差不會(huì)大算法的方差不會(huì)大于于HitorMiss的方差。但不能說，的方差。但不能說，Crude算法總是算法總是優(yōu)于優(yōu)于HitorMiss。因?yàn)楹笳咴诮o定的時(shí)間內(nèi)能迭代。因?yàn)楹笳咴诮o定的時(shí)間內(nèi)能迭代的次數(shù)更多。例如，計(jì)算的次數(shù)更多。例如，計(jì)算值時(shí)，值時(shí)，Crude需計(jì)算需計(jì)算平方根，而用投鏢算法平方根，而用投鏢算法darts時(shí)無需計(jì)算平方根。時(shí)無需計(jì)算平方根。2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)3.141855, 3.141422, 3.14143413.1

25、41662,3.141486, 3.141527hitncrude億( )baf x dx2( )bafx dx263.確定的算法確定的算法梯形算法梯形算法將區(qū)間分為將區(qū)間分為n-1個(gè)子區(qū)間，每個(gè)子區(qū)間內(nèi)的長(zhǎng)度為個(gè)子區(qū)間，每個(gè)子區(qū)間內(nèi)的長(zhǎng)度為，Trapezoid (f, n, a, b) / 假設(shè)假設(shè) n 2delta (b-a)/(n-1);sum (f(a) + f(b)/2;for x a+delta step delta to b delta dosum sum + f(x)return sum delta;2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)f(a)f(b)=f

26、 af a 22積分值( ( + )+ ( +)+.+)273. 確定的算法確定的算法 當(dāng)當(dāng)n=100, =3.140399 當(dāng)當(dāng)n=1,000, =3.141555 當(dāng)當(dāng)n=10,000, =3.141586 當(dāng)當(dāng)n=100,000, =3.141593一般地，在同樣的精度下，梯形算法的迭代次數(shù)少于一般地，在同樣的精度下，梯形算法的迭代次數(shù)少于MC積分，但是積分，但是 有時(shí)確定型積分算法求不出解：有時(shí)確定型積分算法求不出解：例如，例如， f(x)=sin2(100)! x)， 。 但是用梯形算法時(shí)，當(dāng)?shù)怯锰菪嗡惴〞r(shí)，當(dāng)2 n101時(shí)，返回值是時(shí)，返回值是0。若用若用MC積分則不會(huì)發(fā)生該類問

27、題，或雖然發(fā)生，但概率小積分則不會(huì)發(fā)生該類問題，或雖然發(fā)生，但概率小得多。得多。2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)101( )2f x dx 28 多重積分多重積分 在確定算法中，為了達(dá)到一定的精度，采樣點(diǎn)的在確定算法中，為了達(dá)到一定的精度，采樣點(diǎn)的數(shù)目隨著積分維數(shù)成指數(shù)增長(zhǎng)，例如，一維積分若有數(shù)目隨著積分維數(shù)成指數(shù)增長(zhǎng)，例如，一維積分若有100個(gè)點(diǎn)可達(dá)到一定的精度，則二維積分可能要計(jì)算個(gè)點(diǎn)可達(dá)到一定的精度，則二維積分可能要計(jì)算1002個(gè)點(diǎn)才能達(dá)到同樣的精度，三維積分則需計(jì)算個(gè)點(diǎn)才能達(dá)到同樣的精度，三維積分則需計(jì)算1003個(gè)點(diǎn)。個(gè)點(diǎn)。(系統(tǒng)的方法系統(tǒng)的方法) 但概率算法

28、對(duì)維數(shù)的敏感度不大，僅是每次迭代但概率算法對(duì)維數(shù)的敏感度不大，僅是每次迭代中計(jì)算的量稍增一點(diǎn)，實(shí)際上，中計(jì)算的量稍增一點(diǎn)，實(shí)際上，MC積分特別適合用積分特別適合用于計(jì)算于計(jì)算4或更高維數(shù)的定積分?；蚋呔S數(shù)的定積分。 若要提高精度，則可用混合技術(shù)：部分采用系統(tǒng)若要提高精度，則可用混合技術(shù)：部分采用系統(tǒng)的方法，部分采用概率的方法的方法，部分采用概率的方法2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)29 上一節(jié)可以認(rèn)為，數(shù)字概率算法被用來近似上一節(jié)可以認(rèn)為，數(shù)字概率算法被用來近似一個(gè)實(shí)數(shù)，本節(jié)可用它們來估計(jì)一個(gè)整數(shù)值。例一個(gè)實(shí)數(shù)，本節(jié)可用它們來估計(jì)一個(gè)整數(shù)值。例如，設(shè)如，設(shè)X為為有限

29、集，若要求有限集，若要求X的勢(shì)的勢(shì)|X|，則當(dāng)，則當(dāng)X較大較大時(shí)，枚舉顯然不現(xiàn)實(shí)。時(shí)，枚舉顯然不現(xiàn)實(shí)。1. 問題：隨機(jī)選出問題：隨機(jī)選出25人，你是否愿意賭其中至少有人，你是否愿意賭其中至少有兩個(gè)人生日相同嗎？直覺告訴我們，一般人都不兩個(gè)人生日相同嗎？直覺告訴我們，一般人都不愿意賭其成立，但實(shí)際上成立的概率大于愿意賭其成立，但實(shí)際上成立的概率大于50%。2.3 概率計(jì)數(shù)概率計(jì)數(shù)30 一般地，從一般地，從n個(gè)對(duì)象中選出個(gè)對(duì)象中選出k個(gè)互不相同的對(duì)象，若考慮個(gè)互不相同的對(duì)象，若考慮 選擇的次序，則不同的選擇有選擇的次序，則不同的選擇有 種；若允許重復(fù)選取種；若允許重復(fù)選取同同 一對(duì)象，則不同的選法

30、共有一對(duì)象，則不同的選法共有 種。種。 因此，從因此，從n個(gè)對(duì)象個(gè)對(duì)象(允許同一對(duì)象重復(fù)取多次允許同一對(duì)象重復(fù)取多次)中隨機(jī)均中隨機(jī)均勻地選擇出的勻地選擇出的k個(gè)對(duì)象互不相同的概率是：個(gè)對(duì)象互不相同的概率是： ，注意，注意a，b和和b，a是不同的取法。由此可知，上述問題中，是不同的取法。由此可知，上述問題中，25個(gè)人生個(gè)人生日互不相同的概率是：日互不相同的概率是：這里假設(shè)：不考慮潤(rùn)年，一年中人的生日是均勻分布的。這里假設(shè)：不考慮潤(rùn)年，一年中人的生日是均勻分布的。2.3 概率計(jì)數(shù)概率計(jì)數(shù)!()!nnkkn!()!knnkn25365!365,25340!365nk31由由Stirling公式知：

31、公式知：可得可得 假定假定 Tj;3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理51例例2 2：離散對(duì)數(shù)計(jì)算：離散對(duì)數(shù)計(jì)算l離散對(duì)數(shù)計(jì)算困難使其可用于密碼算法，數(shù)字簽名等離散對(duì)數(shù)計(jì)算困難使其可用于密碼算法，數(shù)字簽名等l定義：設(shè)定義：設(shè) a=gx mod p，記，記 logg,pa=x，稱，稱x為為a的的(以以g為底模除為底模除p)對(duì)數(shù)。對(duì)數(shù)。 從從p，g，a計(jì)算計(jì)算x稱為稱為離散對(duì)數(shù)離散對(duì)數(shù)問題。問題。l簡(jiǎn)單算法簡(jiǎn)單算法 計(jì)算計(jì)算gx對(duì)所有的對(duì)所有的x，最多計(jì)算，最多計(jì)算0 x p-1 或或 1xp，因?yàn)閷?shí)際，因?yàn)閷?shí)際上離散對(duì)數(shù)上離散對(duì)數(shù)是循環(huán)群；是循環(huán)群； 驗(yàn)證驗(yàn)證a=gx mod p 是否成立。是否成立

32、。dlog(g, a, p) / 當(dāng)這樣的對(duì)數(shù)不存在時(shí)，算法返回當(dāng)這樣的對(duì)數(shù)不存在時(shí)，算法返回p x 0; y 1; do x+; y y*g; / 計(jì)算計(jì)算y=gx while ( a y mod p) and (x p); return x2,7xlog3x32 mod7例無解，不存在使52l問題：最壞問題：最壞O(p)循環(huán)次數(shù)難以預(yù)料，當(dāng)滿足一定條件時(shí)平均循環(huán)循環(huán)次數(shù)難以預(yù)料，當(dāng)滿足一定條件時(shí)平均循環(huán)p/2次次當(dāng)當(dāng)p=24位十進(jìn)制數(shù)，循環(huán)位十進(jìn)制數(shù)，循環(huán)1024次，千萬億次次，千萬億次/秒秒 (1016次次/秒秒) 大約算大約算1年年(108秒秒/年年)若若p是數(shù)百位十進(jìn)制？隨機(jī)選擇都可

33、能無法在可行的時(shí)間內(nèi)求解。是數(shù)百位十進(jìn)制？隨機(jī)選擇都可能無法在可行的時(shí)間內(nèi)求解。l假設(shè)有一個(gè)平均時(shí)間性能很好，但最壞情況差的確定算法求假設(shè)有一個(gè)平均時(shí)間性能很好，但最壞情況差的確定算法求logg,pa，怎樣用怎樣用Sherwood算法求解該問題？算法求解該問題？設(shè)設(shè)p=19, g=2當(dāng)當(dāng)a=14, 6時(shí)，時(shí)，log2,1914 = 7, log2,196=14，即用，即用dlog求求14和和6的離散的離散對(duì)數(shù)時(shí)，分別要循環(huán)對(duì)數(shù)時(shí)，分別要循環(huán)7和和14次，執(zhí)行時(shí)間與次，執(zhí)行時(shí)間與a的取值相關(guān)。的取值相關(guān)。 用用sherwood算法應(yīng)該使得與算法應(yīng)該使得與a無關(guān)，用隨機(jī)預(yù)處理的方法計(jì)算無關(guān)，用隨機(jī)

34、預(yù)處理的方法計(jì)算logg,pa例例2 2：離散對(duì)數(shù)計(jì)算：離散對(duì)數(shù)計(jì)算53l 定理定理(見見p877, 31.6) dlogRH(g, a, p) / 求求logg,pa, a = gx mod p，求，求x / Sherwood算法算法 r uniform(0.p-2); b ModularExponent(g, r, p); /求冪模求冪模b=gr mod p c ba mod p; /(gr modp)(gxmodp)modp=gr+xmodp=c y logg,pc; / 使用確定性算法求使用確定性算法求logp,gc, y=r+x return (y-r) mod (p-1); / 求

35、求xEx. 分析分析dlogRH的工作原理，指出該算法相應(yīng)的的工作原理，指出該算法相應(yīng)的u和和v3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理,log(mod)(loglog)mod(1)log(mod)for 02g pg pg prg pstpstpgprrp54l 隨機(jī)預(yù)處理提供了一種加密計(jì)算的可能性隨機(jī)預(yù)處理提供了一種加密計(jì)算的可能性 假定你想計(jì)算某個(gè)實(shí)例假定你想計(jì)算某個(gè)實(shí)例x，通過，通過f(x)計(jì)算，但你缺乏計(jì)算，但你缺乏計(jì)算能力或是缺乏有效算法，而別人有相應(yīng)的計(jì)算能力，計(jì)算能力或是缺乏有效算法，而別人有相應(yīng)的計(jì)算能力，愿意為你計(jì)算愿意為你計(jì)算(可能會(huì)收費(fèi)可能會(huì)收費(fèi))，若你愿意別人幫你計(jì)算，若你愿

36、意別人幫你計(jì)算，但你不愿意泄露你的輸入實(shí)例但你不愿意泄露你的輸入實(shí)例x，你將如何做？，你將如何做？可將隨機(jī)預(yù)處理使用到可將隨機(jī)預(yù)處理使用到f的計(jì)算上：的計(jì)算上： 使用函數(shù)使用函數(shù)u將將x加密為某一隨機(jī)實(shí)例加密為某一隨機(jī)實(shí)例y 將將y提交給提交給f計(jì)算出計(jì)算出f(y)的值的值 使用函數(shù)使用函數(shù)v轉(zhuǎn)換為轉(zhuǎn)換為f(x) 上述過程，他人除了知道你的實(shí)例大小外，不知道上述過程，他人除了知道你的實(shí)例大小外，不知道x的任何信息，因?yàn)榈娜魏涡畔?，因?yàn)閡(x,r)的概率分布的概率分布(只要只要r是隨機(jī)均勻是隨機(jī)均勻選擇的選擇的)是獨(dú)立于是獨(dú)立于x的。的。3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理55 設(shè)兩個(gè)數(shù)組設(shè)兩個(gè)數(shù)組

37、val1.n和和ptr1.n及及head構(gòu)成一構(gòu)成一個(gè)有序的靜態(tài)鏈表：個(gè)有序的靜態(tài)鏈表：valhead valptrhead valptrptrhead valptrn-1head例：例：3.3 搜索有序表搜索有序表:ptri給個(gè)關(guān)鍵標(biāo)非關(guān)鍵即關(guān)鍵出出下下一一字字的的下下if vali最if vali最大大字字0 if vali是0 if vali是最最大大字字 i 1 2 3 4 5 6 7vali 2 3 13 1 5 21 8ptri 2 5 6 1 7 0 3rank 2 3 6 1 4 7 5head=4 有序表：有序表：1，2，3，5，8，13，21 56n 折半查找：折半查找：

38、若若val1.n本身有序，可用折半查找找某本身有序，可用折半查找找某個(gè)給定的個(gè)給定的key，時(shí)間為，時(shí)間為O(lgn)。n 順序查找：順序查找：但此表為鏈?zhǔn)浇Y(jié)構(gòu)，故最壞時(shí)間是但此表為鏈?zhǔn)浇Y(jié)構(gòu)，故最壞時(shí)間是(n)(n)。盡管如此，我們能夠找到一個(gè)確定性算法，平均時(shí)間盡管如此，我們能夠找到一個(gè)確定性算法，平均時(shí)間為為 。 相應(yīng)的相應(yīng)的SherwoodSherwood算法的期望時(shí)間是算法的期望時(shí)間是 ，它雖，它雖然并不比確定性算法快，但他消除了最壞實(shí)例。然并不比確定性算法快，但他消除了最壞實(shí)例。 假定表中元素互不相同，且所求的關(guān)鍵字在表中假定表中元素互不相同，且所求的關(guān)鍵字在表中存在，則給定存在，則

39、給定x x，我們是求下標(biāo)，我們是求下標(biāo)i i，使，使vali=x, 這里這里1i n。任何實(shí)例可以由兩個(gè)參數(shù)刻畫：任何實(shí)例可以由兩個(gè)參數(shù)刻畫： 前前n n個(gè)整數(shù)的排列個(gè)整數(shù)的排列 x x的的rank3.3 搜索有序表搜索有序表()On()On57設(shè)設(shè)Sn是所有是所有n!個(gè)排列的集合，設(shè)個(gè)排列的集合，設(shè)A是一個(gè)確定性算法是一個(gè)確定性算法 tA(n, k, )表示算法表示算法A的執(zhí)行時(shí)間，此時(shí)間與被查的執(zhí)行時(shí)間，此時(shí)間與被查找元素的秩找元素的秩k，以及，以及val的排列的排列相關(guān)。若相關(guān)。若A A是一個(gè)概是一個(gè)概率算法，則率算法，則tA(n, k, )表示算法的期望值。無論算法表示算法的期望值。無

40、論算法是確定的還是概率的，是確定的還是概率的，wA(n)和和mA(n)分別表示最壞分別表示最壞時(shí)間和平均時(shí)間，因此有：時(shí)間和平均時(shí)間，因此有： 3.3 搜索有序表搜索有序表1( )max ( , , )|1 1( )( , , )!11,2,.,1/!nAnnAASknw nt n kkn andSm ntn kn nknnSn的概率是，在 中每個(gè)排列的概率是581. 時(shí)間為時(shí)間為O(n)的確定算法的確定算法n 算法算法設(shè)設(shè)xvali且且x在表中，則從位置在表中，則從位置i開始查找開始查找x的算法為的算法為Search(x, i) /仍可改進(jìn)仍可改進(jìn)while x vali do i ptri

41、;return i;在表在表val1.n中查找中查找x的算法為：的算法為：A(x) return Search(x, head);3.3 搜索有序表搜索有序表59n 性能分析性能分析設(shè)設(shè)rank(x)=k, 則：則： 算法算法A在在n個(gè)元素的表中查找個(gè)元素的表中查找x所需的訪問數(shù)組所需的訪問數(shù)組元素的次數(shù)，元素的次數(shù)，顯然與顯然與無關(guān)無關(guān) 算法算法A A最壞時(shí)的訪問次數(shù)最壞時(shí)的訪問次數(shù) 算法算法A A平均的訪問次數(shù)平均的訪問次數(shù) 3.3 搜索有序表搜索有序表( , )Atn kw ( )Anm ( )An1,1, ,( , ),( ),1,2,.,11( )( , )2( )( )AAnAAk

42、nNkn tn kknNknwnnnNknnmntn knT nO n 若時(shí)為最壞情況，此時(shí)設(shè)的概率相等，則綜上所述，602.時(shí)間為時(shí)間為O(n)的概率算法的概率算法n算法算法 D(x) i uniform(1.n);y vali;case x y: return Search(x, ptri); / case2 otherwise: return i; / case3， x = y3.3 搜索有序表搜索有序表61n性能分析性能分析(D訪問數(shù)組次數(shù)訪問數(shù)組次數(shù)) 一般情況一般情況 設(shè)設(shè)rank(x)=k, rank(vali)=j 若若 k j, 則則 ，屬于，屬于case2，從，從jth最小

43、元之后搜索最小元之后搜索若若 k = j, 則則 ，屬于，屬于case3 最壞情況最壞情況3.3 搜索有序表搜索有序表( , ) Dtn kk( , )-Dtn kkj( , )0Dtn kDDnN,w (n)?j 1,knSearchn-1w (n)n 1 當(dāng)時(shí)，執(zhí)行次數(shù)為， 62 平均情況平均情況3.3 搜索有序表搜索有序表121111121,( )?11,2,.,1,2,.,11( )( , )()1(1)(1)()11()22333 DjnnnnDDjkjkkjnjnN mnjnknnmntn kkkjnnnj jnjnjnnnn及的概率均為顯然平均時(shí)間性能優(yōu)于確定算法633.平均時(shí)間

44、為平均時(shí)間為 的確定算法的確定算法n算法算法B(x) /設(shè)設(shè)x在在val1.n中中i head;max vali; / max初值是表初值是表val中最小值中最小值for j 1 to do / 在在val的前的前 個(gè)數(shù)中找不大于個(gè)數(shù)中找不大于x y val j ; / 的最大整數(shù)的最大整數(shù)y相應(yīng)的下標(biāo)相應(yīng)的下標(biāo)i if max y x then i j; max y; /endif / endforreturn Search(x, i); / 從從y開始繼續(xù)搜索開始繼續(xù)搜索3.3 搜索有序表搜索有序表()Onnn64n性能分析性能分析 for循環(huán)的目的：找不超過循環(huán)的目的：找不超過x的最大整

45、數(shù)的最大整數(shù)y，使搜索從，使搜索從y開開始，若將始，若將val1.n中的中的n個(gè)整數(shù)看作是均勻隨機(jī)分布的，則個(gè)整數(shù)看作是均勻隨機(jī)分布的，則在在val1.L中求中求y值就相當(dāng)于在值就相當(dāng)于在n個(gè)整數(shù)中，隨機(jī)地取個(gè)整數(shù)中，隨機(jī)地取L個(gè)整個(gè)整數(shù)，求這數(shù)，求這L個(gè)整數(shù)中不大于個(gè)整數(shù)中不大于x的最大整數(shù)的最大整數(shù)y。 可用一個(gè)與可用一個(gè)與L和和n相關(guān)的隨機(jī)變量來分析，更簡(jiǎn)單的分析相關(guān)的隨機(jī)變量來分析，更簡(jiǎn)單的分析如下：如下：設(shè)設(shè)n個(gè)整數(shù)的排列滿足：個(gè)整數(shù)的排列滿足：a1 a2 0，更，更好的情況是：好的情況是：Ch.4 Las Vegas 算法算法0,( )p x常數(shù)69Obstinate(x) rep

46、eatLV(x, y, success);until success;return y; 設(shè)設(shè)t(x)是算法是算法obstinate找到一個(gè)正確解的期望時(shí)間，則找到一個(gè)正確解的期望時(shí)間，則 若要最小化若要最小化t(x)，則需在，則需在p(x), s(x)和和e(x)之間進(jìn)行某種折衷，之間進(jìn)行某種折衷，例如，若要減少失敗的時(shí)間，則可降低成功的概率例如，若要減少失敗的時(shí)間，則可降低成功的概率p(x)。Ch.4 Las Vegas 算法算法( )( ) ( )(1( )( ( )( )LV1( )( )( )( )( )t xp x s xp xe xt xLVp xt xs xe xp x成功的概

47、率失敗的概率701. 傳統(tǒng)的回溯法傳統(tǒng)的回溯法4.1 8后問題后問題12341234iji+j 135度度對(duì)對(duì)角角線線：同同一一條條對(duì)對(duì)角角線線上上的的元元素素的的行行列列號(hào)號(hào)之之和和相相等等 i-j或或j-i 45度度對(duì)對(duì)角角線線：同同一一條條對(duì)對(duì)角角線線上上的的元元素素的的行行列列號(hào)號(hào)之之差差相相等等 71置當(dāng)前行為第置當(dāng)前行為第1行，當(dāng)前列為第行，當(dāng)前列為第1列，即列，即ij1;while i 8 do / 當(dāng)前行號(hào)當(dāng)前行號(hào) 8檢查當(dāng)前行：從當(dāng)前列檢查當(dāng)前行：從當(dāng)前列j起向后逐列試探，尋找安全列號(hào)；起向后逐列試探，尋找安全列號(hào)；if 找到安全列號(hào)找到安全列號(hào) then 放置皇后，將列號(hào)記

48、入棧，并將下一行置為當(dāng)前行放置皇后，將列號(hào)記入棧，并將下一行置為當(dāng)前行(i+); j1; /當(dāng)前列置為當(dāng)前列置為1 else 退?；厮莸缴弦恍?，即退?；厮莸缴弦恍?，即i-； 移去該行已放置的皇后，以該皇后所在列的下一列作為當(dāng)移去該行已放置的皇后，以該皇后所在列的下一列作為當(dāng) 前列；前列；4.1 8后問題后問題72724.1 8后問題后問題2.Las Vegas方法方法v向量向量try1.8中存放結(jié)果中存放結(jié)果tryi表示第表示第i個(gè)皇后放在（個(gè)皇后放在（i，tryi)位置上位置上vtry1.k稱為稱為k-promising是指：是指：若若k個(gè)皇后的位置個(gè)皇后的位置(0k 8): (1,try1

49、), (2,try2), , (k,tryk)互相不攻擊，則稱互相不攻擊，則稱try1.k是是k-promising的的.形式化：對(duì)形式化：對(duì) ，若，若 有有 (式式1)若式若式1成立，則：成立，則： 無行沖突：無行沖突：無須考慮，因?yàn)榈跓o須考慮，因?yàn)榈趇個(gè)皇后放在第個(gè)皇后放在第i行，故行，故同一行不會(huì)有兩皇后同一行不會(huì)有兩皇后,1, i jkijtryi-tryj i-j,0,j-i73734.1 8后問題后問題 無列沖突：無列沖突：若對(duì)任意不同的兩行若對(duì)任意不同的兩行i、j，因?yàn)槠淞袛?shù)，因?yàn)槠淞袛?shù)之差不為之差不為0，故任意兩皇后不可能在同一列上。，故任意兩皇后不可能在同一列上。 135對(duì)角

50、線無沖突：對(duì)角線無沖突： 和和 沖突時(shí)有：沖突時(shí)有： 即即 故任兩皇后不會(huì)在故任兩皇后不會(huì)在135對(duì)角線上沖突。對(duì)角線上沖突。 45對(duì)角線無沖突：對(duì)角線無沖突： 和和 沖突時(shí)有：沖突時(shí)有：即即tryi-tryj=i-j故任兩皇后不會(huì)在故任兩皇后不會(huì)在45對(duì)角線上沖突。對(duì)角線上沖突。綜上所述，式綜上所述，式1成立時(shí)成立時(shí)try1.k是是k-promising。顯然，若顯然，若k 1，則向量，則向量try1.k是是k-promising的，對(duì)的，對(duì)8后問題，解是后問題，解是8-promising的。的。v 算法算法, i try ia i try ijtry j , j try ja try it

51、ry jji, i try ia, j try ja i try ij try j 7474 QueensLv (success) /貪心的貪心的LV算法，所有皇后都是隨機(jī)放置算法，所有皇后都是隨機(jī)放置/若若Success=true，則，則try1.8包含包含8后問題的一個(gè)解。后問題的一個(gè)解。 col,diag45,diag135；/列及兩對(duì)角線集合初值為空列及兩對(duì)角線集合初值為空 k 0；/行號(hào)行號(hào) repeat /try1.k是是k-promising，考慮放第，考慮放第k+1個(gè)皇后個(gè)皇后 nb 0；/計(jì)數(shù)器，計(jì)數(shù)器，nb值為（值為（k+1)th皇后的皇后的open位置總數(shù)位置總數(shù) for

52、 i 1 to 8 do /i是列號(hào)是列號(hào) if (i col) and (i-k-1 diag45) and (i+k+1 diag135) then /列列i對(duì)（對(duì)（k+1）th皇后可用，但不一定馬上將其放在第皇后可用，但不一定馬上將其放在第i列列 nb nb+1； if uniform(1.nb)=1 then /或許放在第或許放在第i列列 j i；/注意第一次注意第一次uniform一定返回一定返回1，即，即j一定有值一定有值1 /endif /endfor，在在nb個(gè)安全的位置上隨機(jī)選擇個(gè)安全的位置上隨機(jī)選擇1個(gè)位置個(gè)位置j放置之放置之75754.1 8后問題后問題if(nb 0)

53、then /nb=0時(shí)無安全位置，第時(shí)無安全位置，第k+1個(gè)皇后尚未放好個(gè)皇后尚未放好/在所有在所有nb個(gè)安全位置上，個(gè)安全位置上，(k+1)th皇后選擇位置皇后選擇位置j的概率為的概率為1/nb kk+1；/try1.k+1是是(k+1)-promising tryk j；/放置放置(k+1)th個(gè)皇后個(gè)皇后 col col j ； diag45 diag45 j-k ； diag135 diag135 j+k ； /endif until （nb=0）or（k=8）；）；/當(dāng)前皇后找不到合適的位置或當(dāng)前皇后找不到合適的位置或try是是 / 8-promising時(shí)結(jié)束。時(shí)結(jié)束。 succe

54、ss （nb0）；）；76764.1 8后問題后問題v 分析分析設(shè)設(shè)p是成功的概率（一次成功）是成功的概率（一次成功） s：成功時(shí)搜索的結(jié)點(diǎn)的平均數(shù)：成功時(shí)搜索的結(jié)點(diǎn)的平均數(shù)(1個(gè)皇后放好算是搜索樹上的個(gè)皇后放好算是搜索樹上的1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)) e：失敗時(shí)搜索的結(jié)點(diǎn)的平均數(shù)。：失敗時(shí)搜索的結(jié)點(diǎn)的平均數(shù)。顯然顯然s=9（空向量（空向量try算在內(nèi)）算在內(nèi)）, p和和e理論上難于計(jì)算，但實(shí)驗(yàn)用計(jì)算機(jī)可以計(jì)算出：理論上難于計(jì)算，但實(shí)驗(yàn)用計(jì)算機(jī)可以計(jì)算出：p=0.1293e=6.971在重復(fù)上述算法，直至成功時(shí)在重復(fù)上述算法，直至成功時(shí)(相當(dāng)于相當(dāng)于obstinate的時(shí)間），所搜索的的時(shí)間），所搜索的

55、平均結(jié)點(diǎn)數(shù)：平均結(jié)點(diǎn)數(shù)：大大優(yōu)于回溯法，回溯法約為大大優(yōu)于回溯法，回溯法約為114個(gè)結(jié)點(diǎn)才能求出一個(gè)解。個(gè)結(jié)點(diǎn)才能求出一個(gè)解。Ex.證明：當(dāng)放置（證明：當(dāng)放置（k+1)th皇后時(shí)，若有多個(gè)位置是開放的皇后時(shí)，若有多個(gè)位置是開放的,則算法則算法QueensLV選中其中任一位置的概率相等。選中其中任一位置的概率相等。(1) /55.927.tsp e p 77774.1 8后問題后問題v 問題及改進(jìn)問題及改進(jìn) 消極：消極：LV算法過于消極，一旦失敗，從頭再來算法過于消極，一旦失敗，從頭再來 樂觀：樂觀：回溯法過于樂觀，一旦放置某個(gè)皇后失敗，就進(jìn)回溯法過于樂觀，一旦放置某個(gè)皇后失敗，就進(jìn)行系統(tǒng)回退一

56、步的策略，而這一步往往不一定有效。行系統(tǒng)回退一步的策略，而這一步往往不一定有效。 折中：折中：會(huì)更好嗎？一般情況下為此。會(huì)更好嗎？一般情況下為此。先用先用LV方法隨機(jī)地放置前若干個(gè)結(jié)點(diǎn)，例如方法隨機(jī)地放置前若干個(gè)結(jié)點(diǎn)，例如k個(gè)。個(gè)。然后使用回溯法放置后若干個(gè)結(jié)點(diǎn)，但不考慮重放前然后使用回溯法放置后若干個(gè)結(jié)點(diǎn)，但不考慮重放前k個(gè)結(jié)個(gè)結(jié)點(diǎn)。點(diǎn)。若前面的隨機(jī)選擇位置不好，可能使得后面的位置不成功，若前面的隨機(jī)選擇位置不好，可能使得后面的位置不成功，如若前兩個(gè)皇后的位置是如若前兩個(gè)皇后的位置是1、3。隨機(jī)放置的皇后越多，則后續(xù)回溯階段的平均時(shí)間就越少，隨機(jī)放置的皇后越多，則后續(xù)回溯階段的平均時(shí)間就越少

57、，失敗的概率也就越大。失敗的概率也就越大。78784.1 8后問題后問題改進(jìn)算法改進(jìn)算法 折中算法只需將折中算法只需將QueensLV的最后兩行改為：的最后兩行改為：until nb = 0 or k = stepVegas；if （nb0)then /已隨機(jī)放好已隨機(jī)放好stopVegas個(gè)皇后個(gè)皇后 backtrace (k, col, diag45, diag135,success);else success false；stepVegas控制隨機(jī)放置皇后的個(gè)數(shù)，如何選擇？控制隨機(jī)放置皇后的個(gè)數(shù)，如何選擇？ 改進(jìn)算法的試驗(yàn)結(jié)果：改進(jìn)算法的試驗(yàn)結(jié)果：7979純回溯時(shí)間：純回溯時(shí)間：40ms

58、stepVegas=2 or 3：10ms（平均）（平均）純貪心純貪心LV：23ms（平均）（平均）結(jié)論：一半略少的皇后隨機(jī)放置較好。結(jié)論：一半略少的皇后隨機(jī)放置較好。StepVegasStepVegasp ps se et t0 01 11141141141141 11 139.6339.6339.6339.632 20.8750.87522.5322.5339.6739.6728.2028.203 30.49310.493113.4813.4815.1015.1029.0129.014 40.26180.261810.3110.318.798.7935.1035.105 50.16240.

59、16249.339.337.297.2946.9246.926 60.13570.13579.059.056.986.9853.5053.507 70.12930.12939 96.976.9755.9355.938 80.12930.12939 96.976.9753.9353.93搜索的平均節(jié)點(diǎn)數(shù)完全回溯完全隨機(jī)80804.1 8后問題后問題-問題1：為什么僅隨機(jī)放一個(gè)皇后，其效果就會(huì)大大優(yōu)于純回溯方法？81814.1 8后問題后問題-問題2：預(yù)先隨機(jī)選幾個(gè)皇后放置為好？由于解缺乏規(guī)律性（至少在皇后數(shù)不等于4k+2，k為某整數(shù)時(shí)），故求出stepVegas的最優(yōu)值較難，但是找到一個(gè)較好（不

60、一定是最優(yōu)）的stepVegas還是可以的。12皇后：StepVegasStepVegasp ps se et t時(shí)間時(shí)間0 01 1262262262262125ms125ms5 50.50390.503933.8833.8847.2347.2380.3980.3937ms37ms12120.04650.0465131310.210.2222.11222.11基本與純回溯相同基本與純回溯相同82824.1 8后問題后問題在在Apple II機(jī)器上，機(jī)器上，20個(gè)皇后：個(gè)皇后： 確定性的回溯算法：找到第一個(gè)解的時(shí)間大于確定性的回溯算法：找到第一個(gè)解的時(shí)間大于2個(gè)個(gè)小時(shí)。小時(shí)。 概率算法，隨機(jī)地