高級(jí)算法概率

1、1算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析黃劉生黃劉生中國(guó)科學(xué)技術(shù)大學(xué)中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系計(jì)算機(jī)系 國(guó)家高性能計(jì)算國(guó)家高性能計(jì)算中心（合肥）中心（合肥）2008.8.192第一部分第一部分概率算法概率算法3Ch.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á)其中一處，就立即知道該處是否為藏寶

2、地點(diǎn)。你到達(dá)兩處之一地該處是否為藏寶地點(diǎn)。你到達(dá)兩處之一地點(diǎn)及從其中一處到另一處的距離是點(diǎn)及從其中一處到另一處的距離是5天的天的行程。進(jìn)一步假設(shè)有一條惡龍，每晚光顧行程。進(jìn)一步假設(shè)有一條惡龍，每晚光顧寶藏并從中拿走一部分財(cái)寶。假設(shè)你取寶寶藏并從中拿走一部分財(cái)寶。假設(shè)你取寶藏的方案有兩種：藏的方案有兩種：1.1 引言引言4 方案方案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、于龍3晚上拿走的財(cái)寶晚上拿走的財(cái)寶 Prob 1.1.1 若忽略可能的冒險(xiǎn)和出發(fā)尋寶的代若忽略可能的冒險(xiǎn)和出發(fā)尋寶的代價(jià)，你是否接受小精靈的幫助？?jī)r(jià)，你是否接受小精靈的幫助？ 顯然，應(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 引言引言5 設(shè)設(shè)x是你決定之前當(dāng)日的寶藏價(jià)值，設(shè)是你決定之前當(dāng)日的寶藏價(jià)值，設(shè)y是惡龍每是惡龍每晚盜走的寶藏價(jià)值，并設(shè)晚盜走的寶藏價(jià)值，并設(shè)x9y 方案方案1：4天計(jì)算確定地

4、址，行程天計(jì)算確定地址，行程5天，你得到的寶天，你得到的寶藏價(jià)值為：藏價(jià)值為：x-9y 方案方案2：3y付給精靈，行程付給精靈，行程5天失去天失去5y，你得到的，你得到的寶藏價(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.5y62. 意義意義 該故事告訴我們：當(dāng)一個(gè)算法面臨某種選擇該故事告訴我們：當(dāng)一個(gè)算法面臨某種選擇時(shí)，有時(shí)隨機(jī)選擇比耗時(shí)做最優(yōu)選擇更好，

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

6、解同一個(gè)輸入實(shí)例所花的平均執(zhí)行時(shí)間。 因此，對(duì)概率算法可以討論如下兩種期望時(shí)間因此，對(duì)概率算法可以討論如下兩種期望時(shí)間平均的期望時(shí)間：所有輸入實(shí)例上平均的期望執(zhí)行平均的期望時(shí)間：所有輸入實(shí)例上平均的期望執(zhí)行時(shí)間時(shí)間最壞的期望時(shí)間：最壞的輸入實(shí)例上的期望執(zhí)行時(shí)最壞的期望時(shí)間：最壞的輸入實(shí)例上的期望執(zhí)行時(shí)間間84. 例子例子快速排序中的隨機(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é)生用概率的方法劃分，

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

8、全。 概率算法將有所作為：若能接受一個(gè)任意小的錯(cuò)誤的概率概率算法將有所作為：若能接受一個(gè)任意小的錯(cuò)誤的概率95. 概率算法的特點(diǎn)概率算法的特點(diǎn) (1) 不可再現(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é)和

9、數(shù)論的知識(shí)106. 約定約定 隨機(jī)函數(shù)隨機(jī)函數(shù)uniform：隨機(jī)，均勻，獨(dú)立：隨機(jī)，均勻，獨(dú)立設(shè)設(shè)a，b為實(shí)數(shù)，為實(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是一個(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

10、(1.p-1);return ModularExponent(a, j, p); / 在在X中隨機(jī)取一元素中隨機(jī)取一元素13n 偽隨機(jī)數(shù)發(fā)生器偽隨機(jī)數(shù)發(fā)生器n在實(shí)用中不可能有真正的隨機(jī)數(shù)發(fā)生器，多數(shù)情在實(shí)用中不可能有真正的隨機(jī)數(shù)發(fā)生器，多數(shù)情況下是用偽隨機(jī)數(shù)發(fā)生器代替。況下是用偽隨機(jī)數(shù)發(fā)生器代替。n大多數(shù)偽隨機(jī)數(shù)發(fā)生器是基于一對(duì)函數(shù)：大多數(shù)偽隨機(jī)數(shù)發(fā)生器是基于一對(duì)函數(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選的合適，選的合適，該周期長(zhǎng)度會(huì)非常長(zhǎng)。該周期長(zhǎng)度會(huì)非常長(zhǎng)。nTCTC中可用中可用rand()rand()和和srand(time), srand(time), 用用GNU CGNU C更好更好141. 基本特征基本特征2.隨機(jī)決策隨機(jī)決策3.在同一實(shí)例上執(zhí)行兩次其結(jié)果可能不同在同一實(shí)例上執(zhí)行兩次其結(jié)果可能不同4.在同一實(shí)例上執(zhí)行兩次的時(shí)間亦可能不

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

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

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

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

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

17、算法的分類概率算法的分類18這類算法主要用于找到一個(gè)數(shù)字問題的近似解這類算法主要用于找到一個(gè)數(shù)字問題的近似解2.1 值計(jì)算值計(jì)算實(shí)驗(yàn)：將實(shí)驗(yàn)：將n根飛鏢隨機(jī)投向一正方形的靶子，計(jì)算落入此正方形的根飛鏢隨機(jī)投向一正方形的靶子，計(jì)算落入此正方形的內(nèi)切圓中的飛鏢數(shù)目?jī)?nèi)切圓中的飛鏢數(shù)目k。假定飛鏢擊中方形靶子任一點(diǎn)的概率相等假定飛鏢擊中方形靶子任一點(diǎn)的概率相等(用計(jì)算機(jī)模擬比任用計(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為簡(jiǎn)單起見，只以上圖的右上為簡(jiǎn)單起見，只以上圖的右上1/4象限為樣本象限為樣本nDarts (n) nk 0;nfor i 1 to n do nx uniform(0, 1);ny uniform(0, 1); / 隨機(jī)產(chǎn)生點(diǎn)隨機(jī)產(chǎn)生點(diǎn)(x,y)nif (x2 + y2 1) then k+; /圓內(nèi)圓內(nèi)nnreturn 4k/n;nn實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)結(jié)果： =3.141592654nn = 1000萬(wàn)萬(wàn): 3.140740, 3.

19、142568 (2位精確位精確)nn = 1億億: 3.141691, 3.141363 (3位精確位精確)nn = 10億億: 3.141527, 3.141507 (4位精確位精確)2.1 值計(jì)算值計(jì)算20求求近似值的算法近似值的算法Ex.1 若將若將y uniform(0, 1) 改為改為 y x, 則上則上述的算法估計(jì)的值是什么？述的算法估計(jì)的值是什么？2.1 值計(jì)算值計(jì)算21Monte Carlo積分積分(但不是指我們定義的但不是指我們定義的MC算法算法)1、概率算法、概率算法1設(shè)設(shè)f: 0, 1 0, 1是一個(gè)連續(xù)函數(shù)，則由曲線是一個(gè)連續(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ù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)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ù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)1201x dx12041x dx231. 概率算法概率算法12.Ex2. 在機(jī)器上用在機(jī)器上用 估計(jì)估計(jì)值，給出值，給出不同的不同的n值及精度。值及精度。3.Ex3. 設(shè)設(shè)a, b, c和和d是實(shí)數(shù)，且是實(shí)數(shù)，且a b, c d, f:a, b c, d是一個(gè)連續(xù)函數(shù)，寫一概率算是一個(gè)連續(xù)函數(shù)，寫一概率算法計(jì)算積分：法計(jì)算積分：4.5.注意，函數(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)選一連

22、續(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 dx241.概率算法概率算法12.*Ex4. 設(shè)設(shè),是是(0,1)之間的常數(shù)，證明：之間的常數(shù)，證明：3.若若I是是 的正確值，的正確值，h是由是由HitorHiss算法返回的值，算法返回的值，則當(dāng)則當(dāng)n I(1-I)/2時(shí)有：時(shí)有：4.Prob|h-I| 1 5.上述的意義告訴我們：上述的意義告訴我們：Prob|h-I| , 即：當(dāng)即：當(dāng)n I(1-I)/ 2時(shí)，算法的計(jì)算結(jié)果的絕對(duì)誤差超過時(shí)，算法的計(jì)算結(jié)果的絕對(duì)誤差超過的概率的概率不超過不超過，因此我們根

23、據(jù)給定，因此我們根據(jù)給定和和可以確定算法迭代的可以確定算法迭代的次數(shù)次數(shù)6.7.8.解此問題時(shí)可用切比雪夫不等式，將解此問題時(shí)可用切比雪夫不等式，將I看作是數(shù)學(xué)期看作是數(shù)學(xué)期望。望。2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)10( )f x dx22(1)11(1)44IInII 252.概率算法概率算法23.更有效的概率算法是：更有效的概率算法是：在積分區(qū)間上隨機(jī)均勻地產(chǎn)生在積分區(qū)間上隨機(jī)均勻地產(chǎn)生點(diǎn)，求出這些點(diǎn)上的函數(shù)值的算術(shù)平均值，再乘以區(qū)間的寬度：點(diǎn)，求出這些點(diǎn)上的函數(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ù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)11( )()( ),nbiiaif x dxbaf xaxbn262. 概率算法概率算法23.用用HitorMiss和和Crude運(yùn)行三次的結(jié)果為：運(yùn)行三次的結(jié)果為：4.5.假定假定 和和 存在，由算法求得的估存在，由算法求得的估算值的方差反比于點(diǎn)數(shù)算值的方差反比于點(diǎn)數(shù)n。當(dāng)。當(dāng)n足夠大時(shí)，估計(jì)的足夠大時(shí)，估計(jì)的分布近似為正態(tài)分布。分布近似為正態(tài)分布。6.對(duì)于給定的迭代次數(shù)對(duì)于給定的迭代次

25、數(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í)無(wú)需計(jì)算平方時(shí)無(wú)需計(jì)算平方根。根。2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)3.141855, 3.141422, 3.14143413.141662,3.141486, 3.141527hitncrude億( )baf x dx2(

26、)bafx dx273.確定的算法確定的算法4.梯形算法梯形算法5.將區(qū)間分為將區(qū)間分為n-1個(gè)子區(qū)間，每個(gè)子區(qū)間內(nèi)的長(zhǎng)度為個(gè)子區(qū)間，每個(gè)子區(qū)間內(nèi)的長(zhǎng)度為，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ù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)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. 有時(shí)確定型積分算法求不出解：例如，有時(shí)確定型積分算法求不出解：例如，10. f(x)=sin2(100)! x)， 。11. 12. 但是用梯形算法時(shí)，當(dāng)?shù)怯锰菪嗡惴〞r(shí)，當(dāng)2 n101時(shí)，返回值是時(shí)，返回值是0。若用。若用MC積分則不會(huì)發(fā)生該類問

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

29、對(duì)維數(shù)的敏感度不大，僅是每但概率算法對(duì)維數(shù)的敏感度不大，僅是每次迭代中計(jì)算的量稍增一點(diǎn)，實(shí)際上，次迭代中計(jì)算的量稍增一點(diǎn)，實(shí)際上，MC積分特別積分特別適合用于計(jì)算適合用于計(jì)算4或更高維數(shù)的定積分?；蚋呔S數(shù)的定積分。 若要提高精度，則可用混合技術(shù)：部分采若要提高精度，則可用混合技術(shù)：部分采用系統(tǒng)的方法，部分采用概率的方法用系統(tǒng)的方法，部分采用概率的方法2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)30 上一節(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為有限集

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

31、對(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!365nk32由由Stirling公式知：公式知

32、：可得可得 假定假定 T j ; T i T j ; 3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理52例例2 2：離散對(duì)數(shù)計(jì)算：離散對(duì)數(shù)計(jì)算離散對(duì)數(shù)計(jì)算困難使其可用于密碼算法，數(shù)字簽名等離散對(duì)數(shù)計(jì)算困難使其可用于密碼算法，數(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)對(duì)數(shù)。從對(duì)數(shù)。從p p，g g，a a計(jì)算計(jì)算x x稱為離散對(duì)數(shù)問題。稱為離散對(duì)數(shù)問題。簡(jiǎn)單算法：簡(jiǎn)單算法：x, x, 計(jì)算計(jì)算gxgx 最多計(jì)算最多計(jì)算0 x p-1 0 x p-1 或或 1xp 1x

33、p，因?yàn)閷?shí)際上離，因?yàn)閷?shí)際上離散對(duì)數(shù)散對(duì)數(shù)是循環(huán)群；是循環(huán)群； 驗(yàn)證驗(yàn)證a=gx mod p a=gx mod p 是否成立。是否成立。3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理53 算法算法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 x問題：最壞問題：最壞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次

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

35、求14和和6的離散對(duì)數(shù)時(shí)，分別要循環(huán)的離散對(duì)數(shù)時(shí)，分別要循環(huán)7和和14次，執(zhí)行時(shí)間與次，執(zhí)行時(shí)間與a的取值相關(guān)。的取值相關(guān)。l 用用sherwood算法應(yīng)該使得與算法應(yīng)該使得與a無(wú)關(guān)，用隨機(jī)預(yù)處理的方無(wú)關(guān)，用隨機(jī)預(yù)處理的方法計(jì)算法計(jì)算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ì)算的可能性隨機(jī)預(yù)處理提供了一種加密計(jì)算的可能性l 假定你想計(jì)算某個(gè)實(shí)例假定你想計(jì)算

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

38、，上述過程，他人除了知道你的實(shí)例大小外，不知道不知道x的任何信息，因?yàn)榈娜魏涡畔?，因?yàn)閡(x,r)的概率分布的概率分布(只要只要r是隨是隨機(jī)均勻選擇的機(jī)均勻選擇的)是獨(dú)立于是獨(dú)立于x的。的。3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理57 設(shè)兩個(gè)數(shù)組設(shè)兩個(gè)數(shù)組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是

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

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

41、行時(shí)間，此時(shí)間與被查的執(zhí)行時(shí)間，此時(shí)間與被查找元素的秩找元素的秩k，以及，以及val的排列的排列相關(guān)。若相關(guān)。若A是一個(gè)概是一個(gè)概率算法，則率算法，則tA(n, k, )表示算法的期望值。無(wú)論算法表示算法的期望值。無(wú)論算法是確定的還是概率的，是確定的還是概率的，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è)排列的概率是601. 時(shí)間為時(shí)間為

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個(gè)元素的表中查找個(gè)元素的表中查找x所需所需的訪問數(shù)組元素的次數(shù)，顯然與的訪問數(shù)組元素的次數(shù)，顯然

43、與無(wú)關(guān)無(wú)關(guān)n 算法算法A最壞時(shí)的訪問次數(shù)最壞時(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í)為最壞情況，此時(shí)設(shè)的概率相等，則綜上所述，622.時(shí)間為時(shí)間為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、時(shí)，執(zhí)行次數(shù)為， 64 平均情況平均情況3.3 搜索有序表搜索有序表121111121,( )?11,2,.,1,2,.,11( )( , )()1(1)(1)()11()22333 DjnnnnDDjkjkkjnjnN mnjnknnmntn kkkjnnnj jnjnjnnnn及的概率均為顯然平均時(shí)間性能優(yōu)于確定算法653.平均時(shí)間為平均時(shí)間為 的確定算法的確定算法4.算法算法5.B(x) /設(shè)設(shè)x在在val1.n中中6.i head;7.max vali; / max初值是表初值是表val中最小值中最小值8.for j 1 to do / 在在val的前的前 個(gè)數(shù)中找不大個(gè)數(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個(gè)整數(shù)看作是均勻隨機(jī)分布的，個(gè)整數(shù)看作是均勻隨機(jī)分布的，則在則在val1.L中求中求y值就相當(dāng)于在值就相當(dāng)于在n個(gè)整

47、數(shù)中，隨機(jī)地取個(gè)整數(shù)中，隨機(jī)地取L個(gè)個(gè)整數(shù)，求這整數(shù)，求這L個(gè)整數(shù)中不大于個(gè)整數(shù)中不大于x的最大整數(shù)的最大整數(shù)y。n 可用一個(gè)與可用一個(gè)與L和和n相關(guān)的隨機(jī)變量來分析，更簡(jiǎn)單的相關(guān)的隨機(jī)變量來分析，更簡(jiǎn)單的分析如下：分析如下：n設(shè)設(shè)n個(gè)整數(shù)的排列滿足：個(gè)整數(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找到一個(gè)正確解的期望時(shí)間，則找到一個(gè)正確解的期望時(shí)間，則 若

48、要最小化若要最小化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成功的概率失敗的概率721. 傳統(tǒng)的回溯法傳統(tǒng)的回溯法2.4.1 8后問題后問題12341234iji+j 135度度對(duì)對(duì)角角線線：同同一一條條對(duì)對(duì)角角線線上上的的元元素素的的行行列列號(hào)號(hào)之之和和相相

49、等等 i-j或或j-i 45度度對(duì)對(duì)角角線線：同同一一條條對(duì)對(duì)角角線線上上的的元元素素的的行行列列號(hào)號(hào)之之差差相相等等 73置當(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)記入棧，并將下一行置為當(dāng)前行放置皇后，將列號(hào)記入棧，并將下一行置為當(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個(gè)皇后放在（個(gè)皇后放在（i，tryi)位置上位置上try1.k稱為稱為k-promising是指：是指：若若k個(gè)皇后的位置個(gè)皇后的位置(0k 8): (1,try1), (2,try2), , (k,tryk)互相不攻擊，則稱互相不攻擊，則稱try1.k是是k-promising的的.形式化：對(duì)形式化：對(duì) ，若，若 有有 (式式1)若式若式1成立，則：成

51、立，則：無(wú)行沖突：無(wú)須考慮，因?yàn)榈跓o(wú)行沖突：無(wú)須考慮，因?yàn)榈趇個(gè)皇后放在第個(gè)皇后放在第i行，故行，故同一行不會(huì)有兩皇后同一行不會(huì)有兩皇后,1, i jkijtryi-tryj i-j,0,j-i75754.1 8后問題后問題 無(wú)列沖突：若對(duì)任意不同的兩行無(wú)列沖突：若對(duì)任意不同的兩行i、j，因?yàn)槠淞袛?shù)，因?yàn)槠淞袛?shù)之差不為之差不為0，故任意兩皇后不可能在同一列上。，故任意兩皇后不可能在同一列上。 135對(duì)角線無(wú)沖突：對(duì)角線無(wú)沖突： 和和 沖突時(shí)有：沖突時(shí)有： 即即 故任兩皇后不會(huì)在故任兩皇后不會(huì)在135對(duì)角線上沖突。對(duì)角線上沖突。 45對(duì)角線無(wú)沖突：對(duì)角線無(wú)沖突： 和和 沖突時(shí)有：沖突時(shí)有：即即t

52、ryi-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的。的。 算法算法, 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后問題的一個(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 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皇后可用

54、，但不一定馬上將其放在第皇后可用，但不一定馬上將其放在第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放置之放置之77774.1 8后問題后問題if(nb 0) then /nb=0時(shí)無(wú)安全位置，第k+1個(gè)皇后尚未放好/在所有nb個(gè)安全位置上，(k+1)th皇后選擇位置j的概率為1/nb kk+1；/try1.k+1是(k+1)-promising

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

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

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

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

59、放好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é)果：8181純回溯時(shí)間：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é)點(diǎn)數(shù)完全回溯完全隨機(jī)82824.1 8后