算法設計與分析-概率算法經(jīng)典講解_第1頁
算法設計與分析-概率算法經(jīng)典講解_第2頁
算法設計與分析-概率算法經(jīng)典講解_第3頁
算法設計與分析-概率算法經(jīng)典講解_第4頁
算法設計與分析-概率算法經(jīng)典講解_第5頁
已閱讀5頁,還剩141頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

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

2、顧行程。進一步假設有一條惡龍,每晚光顧寶藏并從中拿走一部分財寶。假設你取寶寶藏并從中拿走一部分財寶。假設你取寶藏的方案有兩種:藏的方案有兩種:1.1 引言引言3 方案方案1. 花花4天的時間計算出準確的藏寶地點,然天的時間計算出準確的藏寶地點,然后出發(fā)尋寶,一旦出發(fā)不能重新計算后出發(fā)尋寶,一旦出發(fā)不能重新計算 方案方案2. 有一個小精靈告訴你地圖的秘密,但你有一個小精靈告訴你地圖的秘密,但你必須付給他報酬,相當于龍必須付給他報酬,相當于龍3晚上拿走的財寶晚上拿走的財寶 Prob 1.1.1 若忽略可能的冒險和出發(fā)尋寶的代若忽略可能的冒險和出發(fā)尋寶的代價,你是否接受小精靈的幫助?價,你是否接受小

3、精靈的幫助? 顯然,應該接受小精靈的幫助,因為你只需顯然,應該接受小精靈的幫助,因為你只需給出給出3晚上被盜竊的財寶量,否則你將失去晚上被盜竊的財寶量,否則你將失去4晚被晚被盜財寶量。盜財寶量。 但是,但是,若冒險,你可能做得更好!若冒險,你可能做得更好!1.1 引言引言4 設設x是你決定之前當日的寶藏價值,設是你決定之前當日的寶藏價值,設y是惡龍每是惡龍每晚盜走的寶藏價值,并設晚盜走的寶藏價值,并設x9y 方案方案1:4天計算確定地址,行程天計算確定地址,行程5天,你得到的寶天,你得到的寶藏價值為:藏價值為:x-9y 方案方案2:3y付給精靈,行程付給精靈,行程5天失去天失去5y,你得到的,

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

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

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

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

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

9、b) 返回返回x,a x b 設設i,j為整數(shù),為整數(shù),ij, uniform(i.j)=k, i k j 設設X是非空有限集,是非空有限集, uniform(X) X 10例例1:設設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 uniform(1.p-1);return ModularExponent(a, j, p); / 在在X中隨機取一元素中隨機取一元素12n 偽隨機數(shù)發(fā)生器偽隨機數(shù)發(fā)生

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

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

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

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

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

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

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

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

18、rm(0, 1); / 隨機產(chǎn)生點隨機產(chǎn)生點(x,y)if (x2 + y2 1) then k+; /圓內(nèi)圓內(nèi)return 4k/n;實驗結(jié)果實驗結(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 值計算值計算19求求近似值的算法近似值的算法Ex.1 若將若將y uniform(0, 1) 改為改為 y x, 則上則上述的算法估計的值是什么?述的算法估計的值是什么?2.1 值計

19、算值計算20Monte Carlo積分積分(但不是指我們定義的但不是指我們定義的MC算法算法)1、概率算法概率算法1設設f: 0, 1 0, 1是一個連續(xù)函數(shù),則由曲線是一個連續(xù)函數(shù),則由曲線y=f(x), x軸軸, y軸和直線軸和直線x=1圍成的面積由下述積分給出:圍成的面積由下述積分給出:向單位面積的正方形內(nèi)投鏢向單位面積的正方形內(nèi)投鏢n次,落入陰影部分的鏢的次,落入陰影部分的鏢的數(shù)目為數(shù)目為k,則,則顯然,只要顯然,只要n足夠大足夠大2.2 數(shù)字積分數(shù)字積分 (計算定積分的值計算定積分的值)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ù)字積分數(shù)字積分 (計算定積分的值計算定積分的值)1201x dx12041x dx221. 概率算法概率算法1Ex2. 在機器上用在機器上用 估計估計值,給出不值,給出不同的同的n值及精度。值及精度。Ex3. 設設a, b, c和和d是實數(shù),且是實數(shù),且a b, c d, f:a, b c, d是一個連續(xù)函數(shù),寫一概率算法計是一個連續(xù)函數(shù),寫一概率算法計算積分:

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

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

23、算術平均值,再乘以區(qū)間的寬度:出這些點上的函數(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ù)字積分數(shù)字積分 (計算定積分的值計算定積分的值)11( )()( ),nbiiaif x dxbaf xaxbn252. 概率算法概率算法2用用HitorMiss和和Crude運行三次的結(jié)果為:運行三次的結(jié)果為:假定假定 和和 存在,由算法求得的估算存在,由算法求得的估算值的方差反比于點數(shù)值的方差反比于點數(shù)n。當。當n足夠大時,

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

25、41662,3.141486, 3.141527hitncrude億( )baf x dx2( )bafx dx263.確定的算法確定的算法梯形算法梯形算法將區(qū)間分為將區(qū)間分為n-1個子區(qū)間,每個子區(qū)間內(nèi)的長度為個子區(qū)間,每個子區(qū)間內(nèi)的長度為,Trapezoid (f, n, a, b) / 假設假設 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ù)字積分數(shù)字積分 (計算定積分的值計算定積分的值)f(a)f(b)=f

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

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

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

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

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

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

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

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

34、預處理的方法計算logg,pa例例2 2:離散對數(shù)計算:離散對數(shù)計算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的工作原理,指出該算法相應的的工作原理,指出該算法相應的u和和v3.2 隨機的預處理隨機的預處理,log(mod)(loglog)mod(1)log(mod)for 02g pg pg prg pstpstpgprrp54l 隨機預處理提供了一種加密計算的可能性隨機預處理提供了一種加密計算的可能性 假定你想計算某個實例假定你想計算某個實例x,通過,通過f(x)計算,但你缺乏計算,但你缺乏計算能力或是缺乏有效算法,而別人有相應的計算能力,計算能力或是缺乏有效算法,而別人有相應的計算能力,愿意為你計算愿意為你計算(可能會收費可能會收費),若你愿意別人幫你計算,若你愿

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

37、val1.n和和ptr1.n及及head構成一構成一個有序的靜態(tài)鏈表:個有序的靜態(tài)鏈表:valhead valptrhead valptrptrhead valptrn-1head例:例:3.3 搜索有序表搜索有序表:ptri給個關鍵標非關鍵即關鍵出出下下一一字字的的下下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本身有序,可用折半查找找某本身有序,可用折半查找找某個給定的個給定的key,時間為,時間為O(lgn)。n 順序查找:順序查找:但此表為鏈式結(jié)構,故最壞時間是但此表為鏈式結(jié)構,故最壞時間是(n)(n)。盡管如此,我們能夠找到一個確定性算法,平均時間盡管如此,我們能夠找到一個確定性算法,平均時間為為 。 相應的相應的SherwoodSherwood算法的期望時間是算法的期望時間是 ,它雖,它雖然并不比確定性算法快,但他消除了最壞實例。然并不比確定性算法快,但他消除了最壞實例。 假定表中元素互不相同,且所求的關鍵字在表中假定表中元素互不相同,且所求的關鍵字在表中存在,則給定存在,則

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

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

41、;return i;在表在表val1.n中查找中查找x的算法為:的算法為:A(x) return Search(x, head);3.3 搜索有序表搜索有序表59n 性能分析性能分析設設rank(x)=k, 則:則: 算法算法A在在n個元素的表中查找個元素的表中查找x所需的訪問數(shù)組所需的訪問數(shù)組元素的次數(shù),元素的次數(shù),顯然與顯然與無關無關 算法算法A A最壞時的訪問次數(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 若時為最壞情況,此時設的概率相等,則綜上所述,602.時間為時間為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ù)) 一般情況一般情況 設設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 當時,執(zhí)行次數(shù)為, 62 平均情況平均情況3.3 搜索有序表搜索有序表121111121,( )?11,2,.,1,2,.,11( )( , )()1(1)(1)()11()22333 DjnnnnDDjkjkkjnjnN mnjnknnmntn kkkjnnnj jnjnjnnnn及的概率均為顯然平均時間性能優(yōu)于確定算法633.平均時間

44、為平均時間為 的確定算法的確定算法n算法算法B(x) /設設x在在val1.n中中i head;max vali; / max初值是表初值是表val中最小值中最小值for j 1 to do / 在在val的前的前 個數(shù)中找不大于個數(shù)中找不大于x y val j ; / 的最大整數(shù)的最大整數(shù)y相應的下標相應的下標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個整數(shù)看作是均勻隨機分布的,則個整數(shù)看作是均勻隨機分布的,則在在val1.L中求中求y值就相當于在值就相當于在n個整數(shù)中,隨機地取個整數(shù)中,隨機地取L個整個整數(shù),求這數(shù),求這L個整數(shù)中不大于個整數(shù)中不大于x的最大整數(shù)的最大整數(shù)y。 可用一個與可用一個與L和和n相關的隨機變量來分析,更簡單的分析相關的隨機變量來分析,更簡單的分析如下:如下:設設n個整數(shù)的排列滿足:個整數(shù)的排列滿足:a1 a2 0,更,更好的情況是:好的情況是:Ch.4 Las Vegas 算法算法0,( )p x常數(shù)69Obstinate(x) rep

46、eatLV(x, y, success);until success;return y; 設設t(x)是算法是算法obstinate找到一個正確解的期望時間,則找到一個正確解的期望時間,則 若要最小化若要最小化t(x),則需在,則需在p(x), s(x)和和e(x)之間進行某種折衷,之間進行某種折衷,例如,若要減少失敗的時間,則可降低成功的概率例如,若要減少失敗的時間,則可降低成功的概率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度度對對角角線線:同同一一條條對對角角線線上上的的元元素素的的行行列列號號之之和和相相等等 i-j或或j-i 45度度對對角角線線:同同一一條條對對角角線線上上的的元元素素的的行行列列號號之之差差相相等等 71置當前行為第置當前行為第1行,當前列為第行,當前列為第1列,即列,即ij1;while i 8 do / 當前行號當前行號 8檢查當前行:從當前列檢查當前行:從當前列j起向后逐列試探,尋找安全列號;起向后逐列試探,尋找安全列號;if 找到安全列號找到安全列號 then 放置皇后,將列號記

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

49、), (2,try2), , (k,tryk)互相不攻擊,則稱互相不攻擊,則稱try1.k是是k-promising的的.形式化:對形式化:對 ,若,若 有有 (式式1)若式若式1成立,則:成立,則: 無行沖突:無行沖突:無須考慮,因為第無須考慮,因為第i個皇后放在第個皇后放在第i行,故行,故同一行不會有兩皇后同一行不會有兩皇后,1, i jkijtryi-tryj i-j,0,j-i73734.1 8后問題后問題 無列沖突:無列沖突:若對任意不同的兩行若對任意不同的兩行i、j,因為其列數(shù),因為其列數(shù)之差不為之差不為0,故任意兩皇后不可能在同一列上。,故任意兩皇后不可能在同一列上。 135對角

50、線無沖突:對角線無沖突: 和和 沖突時有:沖突時有: 即即 故任兩皇后不會在故任兩皇后不會在135對角線上沖突。對角線上沖突。 45對角線無沖突:對角線無沖突: 和和 沖突時有:沖突時有:即即tryi-tryj=i-j故任兩皇后不會在故任兩皇后不會在45對角線上沖突。對角線上沖突。綜上所述,式綜上所述,式1成立時成立時try1.k是是k-promising。顯然,若顯然,若k 1,則向量,則向量try1.k是是k-promising的,對的,對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算法,所有皇后都是隨機放置算法,所有皇后都是隨機放置/若若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

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

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

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

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

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

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

58、stepVegas=2 or 3:10ms(平均)(平均)純貪心純貪心LV:23ms(平均)(平均)結(jié)論:一半略少的皇后隨機放置較好。結(jié)論:一半略少的皇后隨機放置較好。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é)點數(shù)完全回溯完全隨機80804.1 8后問題后問題-問題1:為什么僅隨機放一個皇后,其效果就會大大優(yōu)于純回溯方法?81814.1 8后問題后問題-問題2:預先隨機選幾個皇后放置為好?由于解缺乏規(guī)律性(至少在皇后數(shù)不等于4k+2,k為某整數(shù)時),故求出stepVegas的最優(yōu)值較難,但是找到一個較好(不

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論