高級算法概率

1、1算法設(shè)計與分析算法設(shè)計與分析黃劉生黃劉生中國科學(xué)技術(shù)大學(xué)中國科學(xué)技術(shù)大學(xué)計算機(jī)系計算機(jī)系 國家高性能計算國家高性能計算中心（合肥）中心（合肥）2008.8.192第一部分第一部分概率算法概率算法3Ch.1 緒論緒論1. 故事：想象自己是神化故事的主人公，你故事：想象自己是神化故事的主人公，你有一張不易懂的地圖，上面描述了一處寶有一張不易懂的地圖，上面描述了一處寶藏的藏寶地點。經(jīng)分析你能確定最有可能藏的藏寶地點。經(jīng)分析你能確定最有可能的兩個地點是藏寶地點，但二者相距甚遠(yuǎn)。的兩個地點是藏寶地點，但二者相距甚遠(yuǎn)。假設(shè)你如果已到達(dá)其中一處，就立即知道假設(shè)你如果已到達(dá)其中一處，就立即知道該處是否為藏寶

2、地點。你到達(dá)兩處之一地該處是否為藏寶地點。你到達(dá)兩處之一地點及從其中一處到另一處的距離是點及從其中一處到另一處的距離是5天的天的行程。進(jìn)一步假設(shè)有一條惡龍，每晚光顧行程。進(jìn)一步假設(shè)有一條惡龍，每晚光顧寶藏并從中拿走一部分財寶。假設(shè)你取寶寶藏并從中拿走一部分財寶。假設(shè)你取寶藏的方案有兩種：藏的方案有兩種：1.1 引言引言4 方案方案1. 花花4天的時間計算出準(zhǔn)確的藏寶地點，然天的時間計算出準(zhǔn)確的藏寶地點，然后出發(fā)尋寶，一旦出發(fā)不能重新計算后出發(fā)尋寶，一旦出發(fā)不能重新計算 方案方案2. 有一個小精靈告訴你地圖的秘密，但你有一個小精靈告訴你地圖的秘密，但你必須付給他報酬，相當(dāng)于龍必須付給他報酬，相當(dāng)

3、于龍3晚上拿走的財寶晚上拿走的財寶 Prob 1.1.1 若忽略可能的冒險和出發(fā)尋寶的代若忽略可能的冒險和出發(fā)尋寶的代價，你是否接受小精靈的幫助？價，你是否接受小精靈的幫助？ 顯然，應(yīng)該接受小精靈的幫助，因為你只需顯然，應(yīng)該接受小精靈的幫助，因為你只需給出給出3晚上被盜竊的財寶量，否則你將失去晚上被盜竊的財寶量，否則你將失去4晚被晚被盜財寶量。盜財寶量。 但是，若冒險，你可能做得更好！但是，若冒險，你可能做得更好！1.1 引言引言5 設(shè)設(shè)x是你決定之前當(dāng)日的寶藏價值，設(shè)是你決定之前當(dāng)日的寶藏價值，設(shè)y是惡龍每是惡龍每晚盜走的寶藏價值，并設(shè)晚盜走的寶藏價值，并設(shè)x9y 方案方案1：4天計算確定地

4、址，行程天計算確定地址，行程5天，你得到的寶天，你得到的寶藏價值為：藏價值為：x-9y 方案方案2：3y付給精靈，行程付給精靈，行程5天失去天失去5y，你得到的，你得到的寶藏價值為：寶藏價值為：x-8y 方案方案3：投硬幣決定先到一處，失敗后到另一處：投硬幣決定先到一處，失敗后到另一處(冒冒險方案險方案) 一次成功所得：一次成功所得：x-5y，機(jī)會，機(jī)會1/2 二次成功所得：二次成功所得：x-10y，機(jī)會，機(jī)會1/21.1 引言引言期望贏期望贏利：利：x-7.5y62. 意義意義 該故事告訴我們：當(dāng)一個算法面臨某種選擇該故事告訴我們：當(dāng)一個算法面臨某種選擇時，有時隨機(jī)選擇比耗時做最優(yōu)選擇更好，

5、尤其時，有時隨機(jī)選擇比耗時做最優(yōu)選擇更好，尤其是當(dāng)最優(yōu)選擇所花的時間大于隨機(jī)選擇的平均時是當(dāng)最優(yōu)選擇所花的時間大于隨機(jī)選擇的平均時間的時侯間的時侯 顯然，概率算法只能是期望的時間更有效，顯然，概率算法只能是期望的時間更有效，但它有可能遭受到最壞的可能性。但它有可能遭受到最壞的可能性。73. 期望時間和平均時間的區(qū)別期望時間和平均時間的區(qū)別確定算法的平均執(zhí)行時間確定算法的平均執(zhí)行時間 輸入規(guī)模一定的所有輸入實例是等概率出現(xiàn)時，輸入規(guī)模一定的所有輸入實例是等概率出現(xiàn)時，算法的平均執(zhí)行時間。算法的平均執(zhí)行時間。概率算法的期望執(zhí)行時間概率算法的期望執(zhí)行時間 反復(fù)解同一個輸入實例所花的平均執(zhí)行時間。反復(fù)

6、解同一個輸入實例所花的平均執(zhí)行時間。 因此，對概率算法可以討論如下兩種期望時間因此，對概率算法可以討論如下兩種期望時間平均的期望時間：所有輸入實例上平均的期望執(zhí)行平均的期望時間：所有輸入實例上平均的期望執(zhí)行時間時間最壞的期望時間：最壞的輸入實例上的期望執(zhí)行時最壞的期望時間：最壞的輸入實例上的期望執(zhí)行時間間84. 例子例子快速排序中的隨機(jī)劃分快速排序中的隨機(jī)劃分要求學(xué)生寫一算法，由老師給出輸入實例，按運行時間打分，要求學(xué)生寫一算法，由老師給出輸入實例，按運行時間打分，大部分學(xué)生均不敢用簡單的劃分，運行時間在大部分學(xué)生均不敢用簡單的劃分，運行時間在1500-2600ms，三個學(xué)生用概率的方法劃分，

7、運行時間平均為，三個學(xué)生用概率的方法劃分，運行時間平均為300ms。8皇后問題皇后問題系統(tǒng)的方法放置皇后系統(tǒng)的方法放置皇后(回溯法回溯法)較合適，找出所有較合適，找出所有92個解個解 O(2n)，若只找，若只找92個其中的任何一個解可在線性時間內(nèi)完成個其中的任何一個解可在線性時間內(nèi)完成O(n)。 隨機(jī)法：隨機(jī)地放置若干皇后能夠改進(jìn)回溯法，特別是當(dāng)隨機(jī)法：隨機(jī)地放置若干皇后能夠改進(jìn)回溯法，特別是當(dāng)n較大時較大時判斷大整數(shù)是否為素數(shù)判斷大整數(shù)是否為素數(shù)確定算法無法在可行的時間內(nèi)判斷一個數(shù)百位十進(jìn)制數(shù)是否確定算法無法在可行的時間內(nèi)判斷一個數(shù)百位十進(jìn)制數(shù)是否素數(shù)，否則密碼就不安全。素數(shù)，否則密碼就不安

8、全。 概率算法將有所作為：若能接受一個任意小的錯誤的概率概率算法將有所作為：若能接受一個任意小的錯誤的概率95. 概率算法的特點概率算法的特點 (1) 不可再現(xiàn)性不可再現(xiàn)性 在同一個輸入實例上，每次執(zhí)行結(jié)果不盡相同，例在同一個輸入實例上，每次執(zhí)行結(jié)果不盡相同，例如如N-皇后問題皇后問題概率算法運行不同次將會找到不同的正確解概率算法運行不同次將會找到不同的正確解找一給定合數(shù)的非平凡因子找一給定合數(shù)的非平凡因子每次運行的結(jié)果不盡相同，但確定算法每次運行結(jié)每次運行的結(jié)果不盡相同，但確定算法每次運行結(jié)果必定相同果必定相同 (2) 分析困難分析困難 要求有概率論，統(tǒng)計學(xué)和數(shù)論的知識要求有概率論，統(tǒng)計學(xué)和

9、數(shù)論的知識106. 約定約定 隨機(jī)函數(shù)隨機(jī)函數(shù)uniform：隨機(jī)，均勻，獨立：隨機(jī)，均勻，獨立設(shè)設(shè)a，b為實數(shù)，為實數(shù)，ab, uniform(a, 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 11例例1：設(shè)：設(shè)p是一個素數(shù)，是一個素數(shù)，a是一個整數(shù)滿足是一個整數(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

10、(1.p-1);return ModularExponent(a, j, p); / 在在X中隨機(jī)取一元素中隨機(jī)取一元素13n 偽隨機(jī)數(shù)發(fā)生器偽隨機(jī)數(shù)發(fā)生器n在實用中不可能有真正的隨機(jī)數(shù)發(fā)生器，多數(shù)情在實用中不可能有真正的隨機(jī)數(shù)發(fā)生器，多數(shù)情況下是用偽隨機(jī)數(shù)發(fā)生器代替。況下是用偽隨機(jī)數(shù)發(fā)生器代替。n大多數(shù)偽隨機(jī)數(shù)發(fā)生器是基于一對函數(shù)：大多數(shù)偽隨機(jī)數(shù)發(fā)生器是基于一對函數(shù)：nS: X X, S: X X, 這里這里X X足夠大，它是種子的值足夠大，它是種子的值域域nR: X Y, YR: X Y, Y是偽隨機(jī)數(shù)函數(shù)的值域是偽隨機(jī)數(shù)函數(shù)的值域n使用使用S S獲得種子序列：獲得種子序列：x0=g, x

11、i=S(xi-1), i0 x0=g, xi=S(xi-1), i0n然后使用然后使用R R獲得偽隨機(jī)序列：獲得偽隨機(jī)序列：yi=R(xi), i 0yi=R(xi), i 0n該序列必然是周期性的，但只要該序列必然是周期性的，但只要S S和和R R選的合適，選的合適，該周期長度會非常長。該周期長度會非常長。nTCTC中可用中可用rand()rand()和和srand(time), srand(time), 用用GNU CGNU C更好更好141. 基本特征基本特征2.隨機(jī)決策隨機(jī)決策3.在同一實例上執(zhí)行兩次其結(jié)果可能不同在同一實例上執(zhí)行兩次其結(jié)果可能不同4.在同一實例上執(zhí)行兩次的時間亦可能不

12、太相在同一實例上執(zhí)行兩次的時間亦可能不太相同同5. 分類分類6.Numerical, Monte Carlo, Las Vegas, Sherwood.7.很多人將所有概率算法很多人將所有概率算法(尤其是數(shù)字的概率算尤其是數(shù)字的概率算法法)稱為稱為Monte Carlo算法算法1.2 概率算法的分類概率算法的分類15 數(shù)字算法數(shù)字算法隨機(jī)性被最早用于求數(shù)字問題的近似解隨機(jī)性被最早用于求數(shù)字問題的近似解例如，求一個系統(tǒng)中隊列的平均長度的問例如，求一個系統(tǒng)中隊列的平均長度的問題，確定算法很難得到答案題，確定算法很難得到答案 概率算法獲得的答案一般是近似的，但通常算法概率算法獲得的答案一般是近似的，

13、但通常算法執(zhí)行的時間越長，精度就越高，誤差就越小執(zhí)行的時間越長，精度就越高，誤差就越小 使用的理由使用的理由 現(xiàn)實世界中的問題在原理上可能就不存在精確解現(xiàn)實世界中的問題在原理上可能就不存在精確解例如，實驗數(shù)據(jù)本身就是近似的，一個無例如，實驗數(shù)據(jù)本身就是近似的，一個無理數(shù)在計算機(jī)中只能近似地表示理數(shù)在計算機(jī)中只能近似地表示 精確解存在但無法在可行的時間內(nèi)求得精確解存在但無法在可行的時間內(nèi)求得有時答案是以置信區(qū)間的形式給出的有時答案是以置信區(qū)間的形式給出的1.2 概率算法的分類概率算法的分類16 Monte Carlo算法算法 (MC算法算法)蒙特卡洛算法蒙特卡洛算法1945年由年由J. Von

14、Neumann進(jìn)行核武模擬進(jìn)行核武模擬提出的。它是以概率和統(tǒng)計的理論與方法為基礎(chǔ)的一種數(shù)值提出的。它是以概率和統(tǒng)計的理論與方法為基礎(chǔ)的一種數(shù)值計算方法，它是雙重近似：一是用概率模型模擬近似的數(shù)值計算方法，它是雙重近似：一是用概率模型模擬近似的數(shù)值計算，二是用偽隨機(jī)數(shù)模擬真正的隨機(jī)變量的樣本。計算，二是用偽隨機(jī)數(shù)模擬真正的隨機(jī)變量的樣本。這里我們指的這里我們指的MC算法是：算法是： 若問題只有若問題只有1個正確的解，個正確的解，而無近似解的可能時使用而無近似解的可能時使用MC算法算法例如，判定問題只有真或假兩種可能性，沒有近似解例如，判定問題只有真或假兩種可能性，沒有近似解 因式分解，我們不能說

15、某數(shù)幾乎是一個因子因式分解，我們不能說某數(shù)幾乎是一個因子 特點：特點：MC算法總是給出一個答案，但該答案未必正確，成功算法總是給出一個答案，但該答案未必正確，成功(即答案是正確的即答案是正確的)的概率正比于算法執(zhí)行的時間的概率正比于算法執(zhí)行的時間 缺點：一般不能有效地確定算法的答案是否正確缺點：一般不能有效地確定算法的答案是否正確1.2 概率算法的分類概率算法的分類17 Las Vegas算法算法 (LV算法算法)LV算法絕不返回錯誤的答案。算法絕不返回錯誤的答案。 特點：獲得的答案必定正確，但有時它仍根本就找不到特點：獲得的答案必定正確，但有時它仍根本就找不到答案。答案。 和和MC算法一樣，

16、成功的概率亦隨算法執(zhí)行時間增加算法一樣，成功的概率亦隨算法執(zhí)行時間增加而增加。無論輸入何種實例，只要算法在該實例上運行而增加。無論輸入何種實例，只要算法在該實例上運行足夠的次數(shù)，則算法失敗的概率就任意小。足夠的次數(shù)，則算法失敗的概率就任意小。 Sherwood算法算法Sherwood算法總是給出正確的答案。算法總是給出正確的答案。當(dāng)某些確定算法解決一個特殊問題平均的時間比當(dāng)某些確定算法解決一個特殊問題平均的時間比最壞時間快得多時，我們可以使用最壞時間快得多時，我們可以使用Sherwood算法來減算法來減少，甚至是消除好的和壞的實例之間的差別。少，甚至是消除好的和壞的實例之間的差別。1.2 概率

17、算法的分類概率算法的分類18這類算法主要用于找到一個數(shù)字問題的近似解這類算法主要用于找到一個數(shù)字問題的近似解2.1 值計算值計算實驗：將實驗：將n根飛鏢隨機(jī)投向一正方形的靶子，計算落入此正方形的根飛鏢隨機(jī)投向一正方形的靶子，計算落入此正方形的內(nèi)切圓中的飛鏢數(shù)目內(nèi)切圓中的飛鏢數(shù)目k。假定飛鏢擊中方形靶子任一點的概率相等假定飛鏢擊中方形靶子任一點的概率相等(用計算機(jī)模擬比任用計算機(jī)模擬比任一飛鏢高手更能保證此假設(shè)成立一飛鏢高手更能保證此假設(shè)成立)設(shè)圓的半徑為設(shè)圓的半徑為r，面積，面積s1= r2； 方靶面積方靶面積s2=4r2由等概率假設(shè)可知落入圓中的飛鏢和正方形內(nèi)的飛鏢平均比為：由等概率假設(shè)可知

18、落入圓中的飛鏢和正方形內(nèi)的飛鏢平均比為：由此知：由此知： Ch.2 數(shù)字概率算法數(shù)字概率算法2244krnr4 /4nk n k19n求求近似值的算法近似值的算法n為簡單起見，只以上圖的右上為簡單起見，只以上圖的右上1/4象限為樣本象限為樣本nDarts (n) nk 0;nfor i 1 to n do nx uniform(0, 1);ny uniform(0, 1); / 隨機(jī)產(chǎn)生點隨機(jī)產(chǎn)生點(x,y)nif (x2 + y2 1) then k+; /圓內(nèi)圓內(nèi)nnreturn 4k/n;nn實驗結(jié)果：實驗結(jié)果： =3.141592654nn = 1000萬萬: 3.140740, 3.

19、142568 (2位精確位精確)nn = 1億億: 3.141691, 3.141363 (3位精確位精確)nn = 10億億: 3.141527, 3.141507 (4位精確位精確)2.1 值計算值計算20求求近似值的算法近似值的算法Ex.1 若將若將y uniform(0, 1) 改為改為 y x, 則上則上述的算法估計的值是什么？述的算法估計的值是什么？2.1 值計算值計算21Monte Carlo積分積分(但不是指我們定義的但不是指我們定義的MC算法算法)1、概率算法、概率算法1設(shè)設(shè)f: 0, 1 0, 1是一個連續(xù)函數(shù)，則由曲線是一個連續(xù)函數(shù)，則由曲線y=f(x), x軸軸, y軸

20、和直線軸和直線x=1圍成的面積由下述積分給出：圍成的面積由下述積分給出：向單位面積的正方形內(nèi)投鏢向單位面積的正方形內(nèi)投鏢n次，落入陰影部分的鏢的次，落入陰影部分的鏢的數(shù)目為數(shù)目為k，則，則顯然，只要顯然，只要n足夠大足夠大2.2 數(shù)字積分?jǐn)?shù)字積分 (計算定積分的值計算定積分的值)10( )Sf x dx/1kSSk nn/Sk n 221.概率算法概率算法12.HitorMiss (f, n) 3.k 0;4.for i 1 to n do 5.x uniform(0, 1);6.y uniform(0, 1);7.if y f(x) then k+;8.9.return k/n;10.11.

21、Note: 是是S/4的面積，的面積， =S, 12.2.2 數(shù)字積分?jǐn)?shù)字積分 (計算定積分的值計算定積分的值)1201x dx12041x dx231. 概率算法概率算法12.Ex2. 在機(jī)器上用在機(jī)器上用 估計估計值，給出值，給出不同的不同的n值及精度。值及精度。3.Ex3. 設(shè)設(shè)a, b, c和和d是實數(shù)，且是實數(shù)，且a b, c d, f:a, b c, d是一個連續(xù)函數(shù)，寫一概率算是一個連續(xù)函數(shù)，寫一概率算法計算積分：法計算積分：4.5.注意，函數(shù)的參數(shù)是注意，函數(shù)的參數(shù)是a, b, c, d, n和和f, 其中其中f用用函數(shù)指針實現(xiàn)，請選一連續(xù)函數(shù)做實驗，并給函數(shù)指針實現(xiàn)，請選一連

22、續(xù)函數(shù)做實驗，并給出實驗結(jié)果。出實驗結(jié)果。2.2 數(shù)字積分?jǐn)?shù)字積分 (計算定積分的值計算定積分的值)12041x dx( )baf x dx241.概率算法概率算法12.*Ex4. 設(shè)設(shè),是是(0,1)之間的常數(shù)，證明：之間的常數(shù)，證明：3.若若I是是 的正確值，的正確值，h是由是由HitorHiss算法返回的值，算法返回的值，則當(dāng)則當(dāng)n I(1-I)/2時有：時有：4.Prob|h-I| 1 5.上述的意義告訴我們：上述的意義告訴我們：Prob|h-I| , 即：當(dāng)即：當(dāng)n I(1-I)/ 2時，算法的計算結(jié)果的絕對誤差超過時，算法的計算結(jié)果的絕對誤差超過的概率的概率不超過不超過，因此我們根

23、據(jù)給定，因此我們根據(jù)給定和和可以確定算法迭代的可以確定算法迭代的次數(shù)次數(shù)6.7.8.解此問題時可用切比雪夫不等式，將解此問題時可用切比雪夫不等式，將I看作是數(shù)學(xué)期看作是數(shù)學(xué)期望。望。2.2 數(shù)字積分?jǐn)?shù)字積分 (計算定積分的值計算定積分的值)10( )f x dx22(1)11(1)44IInII 252.概率算法概率算法23.更有效的概率算法是：更有效的概率算法是：在積分區(qū)間上隨機(jī)均勻地產(chǎn)生在積分區(qū)間上隨機(jī)均勻地產(chǎn)生點，求出這些點上的函數(shù)值的算術(shù)平均值，再乘以區(qū)間的寬度：點，求出這些點上的函數(shù)值的算術(shù)平均值，再乘以區(qū)間的寬度：4.Crude (f, n, a, b) 5.sum 0;6.for

24、 i 1 to n do 7.x uniform(a, b);8.sum sum + f(x);9.10.return (b-a)sum/n;11.2.2 數(shù)字積分?jǐn)?shù)字積分 (計算定積分的值計算定積分的值)11( )()( ),nbiiaif x dxbaf xaxbn262. 概率算法概率算法23.用用HitorMiss和和Crude運行三次的結(jié)果為：運行三次的結(jié)果為：4.5.假定假定 和和 存在，由算法求得的估存在，由算法求得的估算值的方差反比于點數(shù)算值的方差反比于點數(shù)n。當(dāng)。當(dāng)n足夠大時，估計的足夠大時，估計的分布近似為正態(tài)分布。分布近似為正態(tài)分布。6.對于給定的迭代次數(shù)對于給定的迭代次

25、數(shù)n，Crude算法的方差不算法的方差不會大于會大于HitorMiss的方差。但不能說，的方差。但不能說，Crude算法算法總是優(yōu)于總是優(yōu)于HitorMiss。因為后者在給定的時間內(nèi)能。因為后者在給定的時間內(nèi)能迭代的次數(shù)更多。例如，計算迭代的次數(shù)更多。例如，計算值時，值時，Crude需需計算平方根，而用投鏢算法計算平方根，而用投鏢算法darts時無需計算平方時無需計算平方根。根。2.2 數(shù)字積分?jǐn)?shù)字積分 (計算定積分的值計算定積分的值)3.141855, 3.141422, 3.14143413.141662,3.141486, 3.141527hitncrude億( )baf x dx2(

26、)bafx dx273.確定的算法確定的算法4.梯形算法梯形算法5.將區(qū)間分為將區(qū)間分為n-1個子區(qū)間，每個子區(qū)間內(nèi)的長度為個子區(qū)間，每個子區(qū)間內(nèi)的長度為，6.Trapezoid (f, n, a, b) 7./ 假設(shè)假設(shè) n 28.delta (b-a)/(n-1);9.sum (f(a) + f(b)/2;10.for x a+delta step delta to b delta do11.sum sum + f(x)12.return sum delta;13.2.2 數(shù)字積分?jǐn)?shù)字積分 (計算定積分的值計算定積分的值)f(a)f(b)=f af a 22積分值( ( + )+ ( +)

27、+.+)283. 確定的算法確定的算法 4. 當(dāng)當(dāng)n=100, =3.1403995. 當(dāng)當(dāng)n=1,000, =3.1415556. 當(dāng)當(dāng)n=10,000, =3.1415867. 當(dāng)當(dāng)n=100,000, =3.1415938.一般地，在同樣的精度下，梯形算法的迭代次數(shù)少于一般地，在同樣的精度下，梯形算法的迭代次數(shù)少于MC積分，但是積分，但是9. 有時確定型積分算法求不出解：例如，有時確定型積分算法求不出解：例如，10. f(x)=sin2(100)! x)， 。11. 12. 但是用梯形算法時，當(dāng)?shù)怯锰菪嗡惴〞r，當(dāng)2 n101時，返回值是時，返回值是0。若用。若用MC積分則不會發(fā)生該類問

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

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

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

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

32、：可得可得 假定假定 T j ; T i T j ; 3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理52例例2 2：離散對數(shù)計算：離散對數(shù)計算離散對數(shù)計算困難使其可用于密碼算法，數(shù)字簽名等離散對數(shù)計算困難使其可用于密碼算法，數(shù)字簽名等定義：設(shè)定義：設(shè) a=gx mod p a=gx mod p，記，記 logg,pa=x logg,pa=x，稱，稱x x為為a a的的( (以以g g為為底模除底模除p)p)對數(shù)。從對數(shù)。從p p，g g，a a計算計算x x稱為離散對數(shù)問題。稱為離散對數(shù)問題。簡單算法：簡單算法：x, x, 計算計算gxgx 最多計算最多計算0 x p-1 0 x p-1 或或 1xp 1x

33、p，因為實際上離，因為實際上離散對數(shù)散對數(shù)是循環(huán)群；是循環(huán)群； 驗證驗證a=gx mod p a=gx mod p 是否成立。是否成立。3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理53 算法算法dlog(g, a, p) / 當(dāng)這樣的對數(shù)不存在時，算法返回當(dāng)這樣的對數(shù)不存在時，算法返回p x 0; y 1; do x+; y y*g; / 計算計算y=gx while ( a y mod p) and (x p); return x問題：最壞問題：最壞O(p)循環(huán)次數(shù)難以預(yù)料，當(dāng)滿足一定條件時平均循環(huán)循環(huán)次數(shù)難以預(yù)料，當(dāng)滿足一定條件時平均循環(huán)p/2次次當(dāng)當(dāng)p=24位十進(jìn)制數(shù)，循環(huán)位十進(jìn)制數(shù)，循環(huán)1024次

34、，千萬億次次，千萬億次/秒秒 (1016次次/秒秒) 大約大約算算1年年(108秒秒/年年)若若p是數(shù)百位十進(jìn)制？隨機(jī)選擇都可能無法在可行的時間內(nèi)求解。是數(shù)百位十進(jìn)制？隨機(jī)選擇都可能無法在可行的時間內(nèi)求解。3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理2,7xlog3x32 mod7例無解，不存在使54l假設(shè)有一個平均時間性能很好，但最壞情況差的確定算法假設(shè)有一個平均時間性能很好，但最壞情況差的確定算法求求logp,ga，怎樣用，怎樣用Sherwood算法求解該問題？算法求解該問題？l設(shè)設(shè)p=19, g=2l當(dāng)當(dāng)a=14, 6時，時，log2,1914 = 7, log2,196=14，即用，即用dlog求

35、求14和和6的離散對數(shù)時，分別要循環(huán)的離散對數(shù)時，分別要循環(huán)7和和14次，執(zhí)行時間與次，執(zhí)行時間與a的取值相關(guān)。的取值相關(guān)。l 用用sherwood算法應(yīng)該使得與算法應(yīng)該使得與a無關(guān)，用隨機(jī)預(yù)處理的方無關(guān)，用隨機(jī)預(yù)處理的方法計算法計算logg,pa3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理55l 定理定理(見見p877, 31.6)l l ldlogRH(g, a p) / 求求logg,pa, a = gx mod p，求求xl / Sherwood算法算法l r uniform(0.p-2);l b ModularExponent(g, r, p); /求冪模求冪模b=gr mod pl c ba

36、mod p; /(gr modp)(gxmodp)modp=gr+xmodp=cl y logg,pc; / 使用確定性算法求使用確定性算法求logp,gc, y=r+xl return (y-r) mod (p-1); / 求求xll Ex. 分析分析dlogRH的工作原理，指出該算法相應(yīng)的的工作原理，指出該算法相應(yīng)的u和和v3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理,log(mod)(loglog)mod(1)log(mod)for 02g pg pg prg pstpstpgprrp56l 隨機(jī)預(yù)處理提供了一種加密計算的可能性隨機(jī)預(yù)處理提供了一種加密計算的可能性l 假定你想計算某個實例假定你想計算

37、某個實例x，通過，通過f(x)計算，但計算，但你缺乏計算能力或是缺乏有效算法，而別人有相應(yīng)的計你缺乏計算能力或是缺乏有效算法，而別人有相應(yīng)的計算能力，愿意為你計算算能力，愿意為你計算(可能會收費可能會收費)，若你愿意別人幫，若你愿意別人幫你計算，但你不愿意泄露你的輸入實例你計算，但你不愿意泄露你的輸入實例x，你將如何做？，你將如何做？l可將隨機(jī)預(yù)處理使用到可將隨機(jī)預(yù)處理使用到f的計算上：的計算上：l 使用函數(shù)使用函數(shù)u將將x加密為某一隨機(jī)實例加密為某一隨機(jī)實例yl 將將y提交給提交給f計算出計算出f(y)的值的值l 使用函數(shù)使用函數(shù)v轉(zhuǎn)換為轉(zhuǎn)換為f(x)l 上述過程，他人除了知道你的實例大小外

38、，上述過程，他人除了知道你的實例大小外，不知道不知道x的任何信息，因為的任何信息，因為u(x,r)的概率分布的概率分布(只要只要r是隨是隨機(jī)均勻選擇的機(jī)均勻選擇的)是獨立于是獨立于x的。的。3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理57 設(shè)兩個數(shù)組設(shè)兩個數(shù)組val1.n和和ptr1.n及及head構(gòu)成一構(gòu)成一個有序的靜態(tài)鏈表：個有序的靜態(tài)鏈表：valhead valptrhead valptrptrhead valptrn-1head例：例：3.3 搜索有序表搜索有序表:ptri給個關(guān)鍵標(biāo)非關(guān)鍵即關(guān)鍵出出下下一一字字的的下下if vali最if vali最大大字字0 if vali是0 if vali是

39、最最大大字字 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 58n 折半查找：折半查找： 若若val1.n本身有序，可用折半查找找某本身有序，可用折半查找找某個給定的個給定的key，時間為，時間為O(lgn)。n 順序查找：但此表為鏈?zhǔn)浇Y(jié)構(gòu)，故最壞時間是順序查找：但此表為鏈?zhǔn)浇Y(jié)構(gòu)，故最壞時間是(n)。盡管如此，我們能夠找到一個確定性算法，平均時間盡管如此，我們能夠找到一個確定性算法，平均時間為為 。n 相應(yīng)的相應(yīng)的Sherwood算法的期

40、望時間是算法的期望時間是 ，它雖，它雖然并不比確定性算法快，但他消除了最壞實例。然并不比確定性算法快，但他消除了最壞實例。n 假定表中元素互不相同，且所求的關(guān)鍵字在表中假定表中元素互不相同，且所求的關(guān)鍵字在表中存在，則給定存在，則給定x，我們是求下標(biāo)，我們是求下標(biāo)i，使，使vali=x, 這里這里1i n。n任何實例可以由兩個參數(shù)刻畫：任何實例可以由兩個參數(shù)刻畫：n 前前n個整數(shù)的排列個整數(shù)的排列n x的的rank3.3 搜索有序表搜索有序表()On()On59設(shè)設(shè)Sn是所有是所有n!個排列的集合，設(shè)個排列的集合，設(shè)A是一個確定性算法是一個確定性算法 tA(n, k, )表示算法表示算法A的執(zhí)

41、行時間，此時間與被查的執(zhí)行時間，此時間與被查找元素的秩找元素的秩k，以及，以及val的排列的排列相關(guān)。若相關(guān)。若A是一個概是一個概率算法，則率算法，則tA(n, k, )表示算法的期望值。無論算法表示算法的期望值。無論算法是確定的還是概率的，是確定的還是概率的，wA(n)和和mA(n)分別表示最壞分別表示最壞時間和平均時間，因此有：時間和平均時間，因此有： 3.3 搜索有序表搜索有序表1( )max ( , , )|1 1( )( , , )!11,2,.,1/!nAnnAASknw nt n kkn andSm ntn kn nknnSn的概率是，在 中每個排列的概率是601. 時間為時間為

42、O(n)的確定算法的確定算法2. 算法算法3. 設(shè)設(shè)xvali且且x在表中，則從位置在表中，則從位置i開始查找開始查找x的算法為的算法為4.Search(x, i) /仍可改進(jìn)仍可改進(jìn)5.while x vali do6. i ptri;7.return i;8.9.在表在表val1.n中查找中查找x的算法為：的算法為：10.A(x) 11.return Search(x, head);12.3.3 搜索有序表搜索有序表61n 性能分析性能分析n設(shè)設(shè)rank(x)=k, 則：則：n 算法算法A在在n個元素的表中查找個元素的表中查找x所需所需的訪問數(shù)組元素的次數(shù)，顯然與的訪問數(shù)組元素的次數(shù)，顯然

43、與無關(guān)無關(guān)n 算法算法A最壞時的訪問次數(shù)最壞時的訪問次數(shù)n 算法算法A平均的訪問次數(shù)平均的訪問次數(shù)n nnn3.3 搜索有序表搜索有序表( , )Atn kw ( )Anm ( )An1,1, ,( , ),( ),1,2,.,11( )( , )2( )( )AAnAAknNkn tn kknNknwnnnNknnmntn knT nO n 若時為最壞情況，此時設(shè)的概率相等，則綜上所述，622.時間為時間為O(n)的概率算法的概率算法3.算法算法4. D(x) 5.i uniform(1.n);6.y vali;7.case 8. x y: return Search(x, ptri); /

44、 case210. otherwise: return i; / case3， x = y.3 搜索有序表搜索有序表63n性能分析性能分析(D訪問數(shù)組次數(shù)訪問數(shù)組次數(shù))n 一般情況一般情況n 設(shè)設(shè)rank(x)=k, rank(vali)=j n若若 k j, 則則 ，屬于，屬于case2，從，從jth最小元之后搜最小元之后搜索索n若若 k = j, 則則 ，屬于，屬于case3n 最壞情況最壞情況nnn3.3 搜索有序表搜索有序表( , ) Dtn kk( , )-Dtn kkj( , )0Dtn kDDnN,w (n)?j 1,knSearchn-1w (n)n 1 當(dāng)

45、時，執(zhí)行次數(shù)為， 64 平均情況平均情況3.3 搜索有序表搜索有序表121111121,( )?11,2,.,1,2,.,11( )( , )()1(1)(1)()11()22333 DjnnnnDDjkjkkjnjnN mnjnknnmntn kkkjnnnj jnjnjnnnn及的概率均為顯然平均時間性能優(yōu)于確定算法653.平均時間為平均時間為 的確定算法的確定算法4.算法算法5.B(x) /設(shè)設(shè)x在在val1.n中中6.i head;7.max vali; / max初值是表初值是表val中最小值中最小值8.for j 1 to do / 在在val的前的前 個數(shù)中找不大個數(shù)中找不大于于

46、x 9. y val j ; / 的最大整數(shù)的最大整數(shù)y相應(yīng)的下標(biāo)相應(yīng)的下標(biāo)i10. if max y x then 11.i j;12. max y;13. /endif14. / endfor15.return Search(x, i); / 從從y開始繼續(xù)搜索開始繼續(xù)搜索16.3.3 搜索有序表搜索有序表()Onnn66n性能分析性能分析n for循環(huán)的目的：找不超過循環(huán)的目的：找不超過x的最大整數(shù)的最大整數(shù)y，使搜索從，使搜索從y開始，若將開始，若將val1.n中的中的n個整數(shù)看作是均勻隨機(jī)分布的，個整數(shù)看作是均勻隨機(jī)分布的，則在則在val1.L中求中求y值就相當(dāng)于在值就相當(dāng)于在n個整

47、數(shù)中，隨機(jī)地取個整數(shù)中，隨機(jī)地取L個個整數(shù)，求這整數(shù)，求這L個整數(shù)中不大于個整數(shù)中不大于x的最大整數(shù)的最大整數(shù)y。n 可用一個與可用一個與L和和n相關(guān)的隨機(jī)變量來分析，更簡單的相關(guān)的隨機(jī)變量來分析，更簡單的分析如下：分析如下：n設(shè)設(shè)n個整數(shù)的排列滿足：個整數(shù)的排列滿足：a1 a2 0，更好的情況是：更好的情況是：Ch.4 Las Vegas 算法算法0,( )p x常數(shù)71Obstinate(x) repeatLV(x, y, success);until success;return y; 設(shè)設(shè)t(x)是算法是算法obstinate找到一個正確解的期望時間，則找到一個正確解的期望時間，則 若

48、要最小化若要最小化t(x)，則需在，則需在p(x), s(x)和和e(x)之間進(jìn)行某種折衷，之間進(jìn)行某種折衷，例如，若要減少失敗的時間，則可降低成功的概率例如，若要減少失敗的時間，則可降低成功的概率p(x)。Ch.4 Las Vegas 算法算法( )( ) ( )(1( )( ( )( )LV1( )( )( )( )( )t xp x s xp xe xt xLVp xt xs xe xp x成功的概率失敗的概率721. 傳統(tǒng)的回溯法傳統(tǒng)的回溯法2.4.1 8后問題后問題12341234iji+j 135度度對對角角線線：同同一一條條對對角角線線上上的的元元素素的的行行列列號號之之和和相相

49、等等 i-j或或j-i 45度度對對角角線線：同同一一條條對對角角線線上上的的元元素素的的行行列列號號之之差差相相等等 73置當(dāng)前行為第置當(dāng)前行為第1行，當(dāng)前列為第行，當(dāng)前列為第1列，即列，即ij1;while i 8 do / 當(dāng)前行號當(dāng)前行號 8檢查當(dāng)前行：從當(dāng)前列檢查當(dāng)前行：從當(dāng)前列j起向后逐列試探，尋找安全列號；起向后逐列試探，尋找安全列號；if 找到安全列號找到安全列號 then 放置皇后，將列號記入棧，并將下一行置為當(dāng)前行放置皇后，將列號記入棧，并將下一行置為當(dāng)前行(i+); j1; /當(dāng)前列置為當(dāng)前列置為1 else 退?；厮莸缴弦恍?，即退棧回溯到上一行，即i-； 移去該行已放置

50、的皇后，以該皇后所在列的下一列作為當(dāng)移去該行已放置的皇后，以該皇后所在列的下一列作為當(dāng) 前列；前列；4.1 8后問題后問題74744.1 8后問題后問題2.Las Vegas方法方法向量向量try1.8中存放結(jié)果中存放結(jié)果tryi表示第表示第i個皇后放在（個皇后放在（i，tryi)位置上位置上try1.k稱為稱為k-promising是指：是指：若若k個皇后的位置個皇后的位置(0k 8): (1,try1), (2,try2), , (k,tryk)互相不攻擊，則稱互相不攻擊，則稱try1.k是是k-promising的的.形式化：對形式化：對 ，若，若 有有 (式式1)若式若式1成立，則：成

51、立，則：無行沖突：無須考慮，因為第無行沖突：無須考慮，因為第i個皇后放在第個皇后放在第i行，故行，故同一行不會有兩皇后同一行不會有兩皇后,1, i jkijtryi-tryj i-j,0,j-i75754.1 8后問題后問題 無列沖突：若對任意不同的兩行無列沖突：若對任意不同的兩行i、j，因為其列數(shù)，因為其列數(shù)之差不為之差不為0，故任意兩皇后不可能在同一列上。，故任意兩皇后不可能在同一列上。 135對角線無沖突：對角線無沖突： 和和 沖突時有：沖突時有： 即即 故任兩皇后不會在故任兩皇后不會在135對角線上沖突。對角線上沖突。 45對角線無沖突：對角線無沖突： 和和 沖突時有：沖突時有：即即t

52、ryi-tryj=i-j故任兩皇后不會在故任兩皇后不會在45對角線上沖突。對角線上沖突。 綜上所述，式綜上所述，式1成立時成立時try1.k是是k-promising。 顯然，若顯然，若k 1，則向量，則向量try1.k是是k-promising的，對的，對 8后問題，解是后問題，解是8-promising的。的。 算法算法, i try ia i try ijtry j , j try ja try itry jji, i try ia, j try ja i try ij try j 7676 QueensLv (success) /貪心的貪心的LV算法，所有皇后都是隨機(jī)放置算法，所有皇后

53、都是隨機(jī)放置/若若Success=true，則，則try1.8包含包含8后問題的一個解。后問題的一個解。 col,diag45,diag135；/列及兩對角線集合初值為空列及兩對角線集合初值為空 k 0；/行號行號 repeat /try1.k是是k-promising，考慮放第，考慮放第k+1個皇后個皇后 nb 0；/計數(shù)器，計數(shù)器，nb值為（值為（k+1)th皇后的皇后的open位置總數(shù)位置總數(shù) for i 1 to 8 do /i是列號是列號 if (i col) and (i-k-1 diag45) and (i+k+1 diag135) then /列列i對（對（k+1）th皇后可用

54、，但不一定馬上將其放在第皇后可用，但不一定馬上將其放在第i列列 nb nb+1； if uniform(1.nb)=1 then /或許放在第或許放在第i列列 j i；/注意第一次注意第一次uniform一定返回一定返回1，即，即j一定有值一定有值1 /endif /endfor，在，在nb個安全的位置上隨機(jī)選擇個安全的位置上隨機(jī)選擇1個位置個位置j放置之放置之77774.1 8后問題后問題if(nb 0) then /nb=0時無安全位置，第k+1個皇后尚未放好/在所有nb個安全位置上，(k+1)th皇后選擇位置j的概率為1/nb kk+1；/try1.k+1是(k+1)-promising

55、 tryk j；/放置(k+1)th個皇后 col col j ； diag45 diag45 j-k ； diag135 diag135 j+k ； /endif until （nb=0）or（k=8）；/當(dāng)前皇后找不到合適的位置或try是 / 8-promising時結(jié)束。 success （nb0）；78784.1 8后問題后問題v 分析分析v 設(shè)設(shè)p是成功的概率（一次成功）是成功的概率（一次成功） v s：成功時搜索的結(jié)點的平均數(shù)：成功時搜索的結(jié)點的平均數(shù)(1個皇后放好算是個皇后放好算是搜索樹上的搜索樹上的1個結(jié)點個結(jié)點)v e：失敗時搜索的結(jié)點的平均數(shù)。：失敗時搜索的結(jié)點的平均數(shù)。v

56、 顯然顯然s=9（空向量（空向量try算在內(nèi)）算在內(nèi)）,v p和和e理論上難于計算，但實驗用計算機(jī)可以計理論上難于計算，但實驗用計算機(jī)可以計算出：算出：vp=0.1293ve=6.971v在重復(fù)上述算法，直至成功時在重復(fù)上述算法，直至成功時(相當(dāng)于相當(dāng)于obstinate的時間），所搜索的平均結(jié)點數(shù)：的時間），所搜索的平均結(jié)點數(shù)：v大大優(yōu)于回溯法，回溯法約為大大優(yōu)于回溯法，回溯法約為114個結(jié)點才能求個結(jié)點才能求出一個解。出一個解。v Ex.證明：當(dāng)放置（證明：當(dāng)放置（k+1)th皇后時，若有多個位置是皇后時，若有多個位置是開放的開放的,則算法則算法QueensLV選中其中任一位置的概率相選中

57、其中任一位置的概率相等。等。(1) /55.927.tsp e p 79794.1 8后問題后問題v 問題及改進(jìn)問題及改進(jìn)v 消極：消極：LV算法過于消極，一旦失敗，從頭再來算法過于消極，一旦失敗，從頭再來v 樂觀：回溯法過于樂觀，一旦放置某個皇后失敗，樂觀：回溯法過于樂觀，一旦放置某個皇后失敗，就進(jìn)行系統(tǒng)回退一步的策略，而這一步往往不一定就進(jìn)行系統(tǒng)回退一步的策略，而這一步往往不一定有效。有效。 v 折中：會更好嗎？一般情況下為此。折中：會更好嗎？一般情況下為此。v先用先用LV方法隨機(jī)地放置前若干個結(jié)點，例如方法隨機(jī)地放置前若干個結(jié)點，例如k個。個。v然后使用回溯法放置后若干個結(jié)點，但不考然后

58、使用回溯法放置后若干個結(jié)點，但不考慮重放前慮重放前k個結(jié)點。個結(jié)點。v若前面的隨機(jī)選擇位置不好，可能使得后面若前面的隨機(jī)選擇位置不好，可能使得后面的位置不成功，如若前兩個皇后的位置是的位置不成功，如若前兩個皇后的位置是1、3。v隨機(jī)放置的皇后越多，則后續(xù)回溯階段的平隨機(jī)放置的皇后越多，則后續(xù)回溯階段的平均時間就越少，失敗的概率也就越大。均時間就越少，失敗的概率也就越大。80804.1 8后問題后問題改進(jìn)算法改進(jìn)算法 折中算法只需將折中算法只需將QueensLV的最后兩行改為：的最后兩行改為：until nb = 0 or k = stepVegas；if （nb0)then /已隨機(jī)放好已隨機(jī)

59、放好stopVegas個皇個皇后后 backtrace (k, col, diag45, diag135,success);else success false；stepVegas控制隨機(jī)放置皇后的個數(shù)，如何選控制隨機(jī)放置皇后的個數(shù)，如何選擇？擇？ 改進(jìn)算法的試驗結(jié)果：改進(jìn)算法的試驗結(jié)果：8181純回溯時間：40msstepVegas=2 or 3：10ms（平均）純貪心LV：23ms（平均）結(jié)論：一半略少的皇后隨機(jī)放置較好。StepVegasStepVegasp ps se et t0 01 11141141141141 11 139.6339.6339.6339.632 20.8750.8

60、7522.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.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é)點數(shù)完全回溯完全隨機(jī)82824.1 8后