[學(xué)習(xí)]算法分析與設(shè)計里的概率算法-概率算法

1、,1,算法設(shè)計與分析黃劉生中國科學(xué)技術(shù)大學(xué)計算機(jī)系 國家高性能計算中心（合肥）2008.8.19,,2,Ch.1 概率算法,1. 故事：想象自己是神化故事的主人公，你有一張不易懂的地圖，上面描述了一處寶藏的藏寶地點(diǎn)。經(jīng)分析你能確定最有可能的兩個地點(diǎn)是藏寶地點(diǎn)，但二者相距甚遠(yuǎn)。假設(shè)你如果已到達(dá)其中一處，就立即知道該處是否為藏寶地點(diǎn)。你到達(dá)兩處之一地點(diǎn)及從其中一處到另一處的距離是5天的行程。進(jìn)一步假設(shè)有一條惡龍，每晚光顧寶藏并

2、從中拿走一部分財寶。假設(shè)你取寶藏的方案有兩種：,§1.1 引言,,3,方案1. 花4天的時間計算出準(zhǔn)確的藏寶地點(diǎn)，然后出發(fā)尋寶，一旦出發(fā)不能重新計算 方案2. 有一個小精靈告訴你地圖的秘密，但你必須付給他報酬，相當(dāng)于龍3晚上拿走的財寶 Prob 1.1.1 若忽略可能的冒險和出發(fā)尋寶的代價，你是否接受小精靈的幫助？ 顯然，應(yīng)該接受小精靈的幫助，因?yàn)槟阒恍杞o出3晚上被盜竊的財寶量，否則你將失去

3、4晚被盜財寶量。 但是，若冒險，你可能做得更好！,§1.1 引言,,4,設(shè)x是你決定之前當(dāng)日的寶藏價值，設(shè)y是惡龍每晚盜走的寶藏價值，并設(shè)x>9y 方案1：4天計算確定地址，行程5天，你得到的寶藏價值為：x-9y 方案2：3y付給精靈，行程5天失去5y，你得到的寶藏價值為：x-8y 方案3：投硬幣決定先到一處，失敗后到另一處(冒險方案) 一次成功所得：x-5y，機(jī)會1/2

4、二次成功所得：x-10y，機(jī)會1/2,§1.1 引言,}期望贏利：x-7.5y,,5,2. 意義 該故事告訴我們：當(dāng)一個算法面臨某種選擇時，有時隨機(jī)選擇比耗時做最優(yōu)選擇更好，尤其是當(dāng)最優(yōu)選擇所花的時間大于隨機(jī)選擇的平均時間的時侯 顯然，概率算法只能是期望的時間更有效，但它有可能遭受到最壞的可能性。,,6,3. 期望時間和平均時間的區(qū)別確定算法的平均執(zhí)行時間 輸入規(guī)模一定的所

5、有輸入實(shí)例是等概率出現(xiàn)時，算法的平均執(zhí)行時間。概率算法的期望執(zhí)行時間 反復(fù)解同一個輸入實(shí)例所花的平均執(zhí)行時間。 因此，對概率算法可以討論如下兩種期望時間平均的期望時間：所有輸入實(shí)例上平均的期望執(zhí)行時間最壞的期望時間：最壞的輸入實(shí)例上的期望執(zhí)行時間,,7,4. 例子快速排序中的隨機(jī)劃分要求學(xué)生寫一算法，由老師給出輸入實(shí)例，按運(yùn)行時間打分，所有學(xué)生均不敢用簡單的劃分，運(yùn)行時間在1500-2600m

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

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

8、form(a, b) 返回x，a ≤ x <b② 設(shè)i，j為整數(shù)，i≤j, uniform(i, j)=k, i ≤ k ≤ j③ 設(shè)X是非空有限集， uniform(X) ∈ X,,10,例1：設(shè)p是一個素數(shù)，a是一個整數(shù)滿足1≤a<p， a模除p的指數(shù)(index)是滿足ai≡1(mod p)的最小正整數(shù)i。它等于集合X={aj mod p | j ≥ 1}的勢，即i=|X|。 例如，

9、2模除31的指數(shù)等于5：25 mod 31=1, X={21 mod 31, 22 mod 31, 23 mod 31, 24 mod 31, 25 mod 31}; 5模除31的指數(shù)是3，即53 mod 31 = 1, 3模除31的指數(shù)是30。 由費(fèi)馬(Fermat)定理(ap-1 ≡1(mod p))可知，a模p的指數(shù)總是恰好整除p-1. 例如，設(shè)p=31，若a=2，則30

10、7;5=6； 若a=5，則30÷3=10。 因此，X中的j至多為p-1，由此可得一種在X中隨機(jī)，均勻和獨(dú)立地取一個元素的算法。,,11,ModularExponent(a, j, p){//求方冪模s=aj mod p, 注意先求aj可能會溢出s ← 1;while j>0 do {if (j is odd) s ← s·a mod p;a

11、← a2 mod p;j ← j div 2;}return s;}Draw (a, p) {// 在X中隨機(jī)取一元素j ← uniform(1..p-1);return ModularExponent(a, j, p); // 在X中隨機(jī)取一元素},,12,偽隨機(jī)數(shù)發(fā)生器在實(shí)用中不可能有真正的隨機(jī)數(shù)發(fā)生器，多數(shù)情況下是用偽隨機(jī)數(shù)發(fā)生器代替。大多數(shù)偽隨機(jī)數(shù)發(fā)生器是基于一對函數(shù)：S: X →

12、 X, 這里X足夠大，它是種子的值域R: X → Y, Y是偽隨機(jī)數(shù)函數(shù)的值域使用S獲得種子序列：x0=g, xi=S(xi-1), i>0然后使用R獲得偽隨機(jī)序列：yi=R(xi), i ≥ 0該序列必然是周期性的，但只要S和R選的合適，該周期長度會非常長。TC中可用rand()和srand(time), 用GNU C更好,,13,基本特征隨機(jī)決策在同一實(shí)例上執(zhí)行兩次其結(jié)果可能不同在同一實(shí)例上執(zhí)

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

14、使用的理由現(xiàn)實(shí)世界中的問題在原理上可能就不存在精確解例如，實(shí)驗(yàn)數(shù)據(jù)本身就是近似的，一個無理數(shù)在計算機(jī)中只能近似地表示精確解存在但無法在可行的時間內(nèi)求得有時答案是以置信區(qū)間的形式給出的,§1.2 概率算法的分類,,15,Monte Carlo算法 (MC算法)蒙特卡洛算法1945年由J. Von Neumann進(jìn)行核武模擬提出的。它是以概率和統(tǒng)計的理論與方法為基礎(chǔ)的一種數(shù)值計算方法，它是雙重近似：一是用概率模型

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

16、,16,Las Vegas算法 (LV算法)LV算法絕不返回錯誤的答案。特點(diǎn)：獲得的答案必定正確，但有時它仍根本就找不到答案。 和MC算法一樣，成功的概率亦隨算法執(zhí)行時間增加而增加。無論輸入何種實(shí)例，只要算法在該實(shí)例上運(yùn)行足夠的次數(shù)，則算法失敗的概率就任意小。④ Sherwood算法Sherwood算法總是給出正確的答案。當(dāng)某些確定算法解決一個特殊問題平均的時間比最壞時間快得多時，我們可以使用Sherwood算

17、法來減少，甚至是消除好的和壞的實(shí)例之間的差別。,§1.2 概率算法的分類,,17,這類算法主要用于找到一個數(shù)字問題的近似解§1.3.1 π值計算實(shí)驗(yàn)：將n根飛鏢隨機(jī)投向一正方形的靶子，計算落入此正方形的內(nèi)切圓中的飛鏢數(shù)目k。假定飛鏢擊中方形靶子任一點(diǎn)的概率相等(用計算機(jī)模擬比任一飛鏢高手更能保證此假設(shè)成立)設(shè)圓的半徑為r，面積s1= πr2, 方靶面積s2=4r2由等概率假設(shè)可知落入圓中的飛鏢和正方形

18、內(nèi)的飛鏢平均比為：由此知：,§1.3 數(shù)字概率算法,,18,求π近似值的算法為簡單起見，只以上圖的右上1/4象限為樣本Darts (n) {k ← 0;for i ← 1 to n do {x ← uniform(0, 1);y ← uniform(0, 1); // 隨機(jī)產(chǎn)生點(diǎn)(x,y)if (x2 + y2 ≤ 1) then k++; //圓內(nèi)}retur

19、n 4k/n;}實(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位精確),§1.3.1 π值計算,,19,求π近似值的算法Ex.1 若將y ← uniform(0, 1) 改為 y ← x, 則上述的算法估計的值是什么

20、？,§1.3.1 π值計算,,20,Monte Carlo積分(但不是指我們定義的MC算法)概率算法1設(shè)f: [0, 1] → [0, 1]是一個連續(xù)函數(shù)，則由曲線y=f(x), x軸, y軸和直線x=1圍成的面積由下述積分給出：向單位面積的正方形內(nèi)投鏢n次，落入陰影部分的鏢的數(shù)目為k，則顯然，只要n足夠大,§1.3.2 數(shù)字積分 (計算定積分的值),,21,概率算法1HitorMis

21、s (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, ∴,§1.3.2 數(shù)字積分 (計算定積分的值),,22,概率算法1Ex2. 在機(jī)器上用

22、 估計π值，給出不同的n值及精度。Ex3. 設(shè)a, b, c和d是實(shí)數(shù)，且a ≤ b, c ≤ d, f:[a, b] → [c, d]是一個連續(xù)函數(shù)，寫一概率算法計算積分：注意，函數(shù)的參數(shù)是a, b, c, d, n和f, 其中f用函數(shù)指針實(shí)現(xiàn)，請選一連續(xù)函數(shù)做實(shí)驗(yàn)，并給出實(shí)驗(yàn)結(jié)果。,§1.3.2 數(shù)字積分 (計算定積分的值),,23,概率算法1*Ex4. 設(shè)ε,δ是(0,

23、1)之間的常數(shù)，證明：若I是 的正確值，h是由HitorHiss算法返回的值，則當(dāng)n ≥ I(1-I)/ε2δ時有：Prob[|h-I| < ε] ≥ 1 – δ上述的意義告訴我們：Prob[|h-I| ≥ ε] ≤δ, 即：當(dāng)n ≥ I(1-I)/ ε2δ時，算法的計算結(jié)果的絕對誤差超過ε的概率不超過δ，因此我們根據(jù)給定ε和δ可以確定算法迭代的次數(shù)解此問題時可用切比雪夫不等式，將I

24、看作是數(shù)學(xué)期望。,§1.3.2 數(shù)字積分 (計算定積分的值),,24,概率算法2更有效的概率算法是：在積分區(qū)間上隨機(jī)均勻地產(chǎn)生點(diǎn)，求出這些點(diǎn)上的函數(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)s

25、um/n;},§1.3.2 數(shù)字積分 (計算定積分的值),,25,概率算法2用HitorMiss和Crude運(yùn)行三次的結(jié)果為：假定 和 存在，由算法求得的估算值的方差反比于點(diǎn)數(shù)n。當(dāng)n足夠大時，估計的分布近似為正態(tài)分布。對于給定的迭代次數(shù)n，Crude算法的方差不會大于HitorMiss的方差。但不能說，Crude算法總是優(yōu)于HitorMiss。因?yàn)楹笳咴诮o

26、定的時間內(nèi)能迭代的次數(shù)更多。例如，計算π值時，Crude需計算平方根，而用投鏢算法darts時無需計算平方根。,§1.3.2 數(shù)字積分 (計算定積分的值),,26,確定的算法梯形算法將區(qū)間分為n-1個子區(qū)間，每個子區(qū)間內(nèi)的長度為δ，Trapezoid (f, n, a, b) {// 假設(shè) n ≥ 2delta ← (b-a)/(n-1);sum ← (f(a) + f(b))/2;fo

27、r x ← a+delta step delta to b – delta dosum ← sum + f(x)return sum × delta;},§1.3.2 數(shù)字積分 (計算定積分的值),,27,確定的算法當(dāng)n=100,π=3.140399當(dāng)n=1,000, π=3.141555當(dāng)n=10,000, π=3.141586當(dāng)n=100,000, π=3.141593一般地

28、，在同樣的精度下，梯形算法的迭代次數(shù)少于MC積分，但是有時候確定型積分算法求不出解例如，f(x)=sin2((100)! πx), 但是用梯形算法時，當(dāng)2 ≤ n≤101時，返回值是0。若用MC積分則不會發(fā)生該類問題，或雖然發(fā)生，但概率小得多多重積分在確定算法中，為了達(dá)到一定的精度，采樣點(diǎn)的數(shù)目隨著積分維數(shù)成指數(shù)增長，例如，一維積分若有100個點(diǎn)可達(dá)到一定的精度，則二維積分可能要計算1002個點(diǎn)才能達(dá)到同樣的精度，三維積

29、分則需計算1003個點(diǎn)。(系統(tǒng)的方法)但概率算法對維數(shù)的敏感度不大，僅是每次迭代中計算的量稍微增加一點(diǎn)，實(shí)際上，MC積分特別適合用于計算4或更高維數(shù)的定積分。若要提高精度，則可用混合技術(shù)：部分采用系統(tǒng)的方法，部分采用概率的方法,§1.3.2 數(shù)字積分 (計算定積分的值),,28,上一節(jié)可以認(rèn)為，數(shù)字概率算法被采用來近似一個實(shí)數(shù)，本節(jié)可用它們來估計一個整數(shù)值。例如，設(shè)X是有限集，若要求X的勢|X|，則當(dāng)X較大時，枚舉顯然

30、不現(xiàn)實(shí)。問題：隨機(jī)選出25人，你是否愿意賭其中至少有兩個人生日相同嗎？知覺告訴我們，一般人都不愿意賭其成立，但實(shí)際上成立的概率大于50%。 一般地，從n個對象中選出k個互不相同的對象，若考慮選擇的次序，則不同的選擇有 種。若允許重復(fù)選取同一對象，則不同的選法共有 種。 因此，從n個對象(允許同一對象重復(fù)取多次)中隨機(jī)均勻地選擇出的k個對象互不相同的概率是：

31、 ，注意a，b和b，a是不同的取法，由此可知，上述問題中，25個人生日互不相同的概率是：這里假設(shè)不考慮潤年，并假設(shè)一年中人的生日是均勻分布的。,§1.3.3 概率計數(shù),,29,由Stirling公式知：可得假定 近似地實(shí)際上，若因此，隨機(jī)選出25個人中生日互不相同的概率約43%，由此可知至少有兩人生日相同的概率約為57%此例提示：有回放抽樣，大集

32、合通過第一次重復(fù)來估計集合大小,§1.3.3 概率計數(shù),,30,求集合X的勢設(shè)X是具有n個元素的集合，我們有回放地隨機(jī)，均勻和獨(dú)立地從X中選取元素，設(shè)k是出現(xiàn)第1次重復(fù)之前所選出的元素數(shù)目，則當(dāng)n足夠大時，k的期望值趨近為 ，這里利用此結(jié)論可以得出估計|X|的概率算法：,§1.3.3 概率計數(shù),,31,求集合X的勢SetCount (X) {k ← 0; S ← Ф;

33、a ← uniform(X);do {k++;S ← S∪{a}; a ← uniform(X);} while (a S)return 2k2/π}注意：∵k的期望值是 ，∴上述算法n需足夠大，且運(yùn)行多次后才能確定n=|X|，即取多次運(yùn)行后的平均值才能是n。該算法的時間和空間均為 ，因?yàn)?§1.3.3 概率計數(shù),,32,多重集合中不同

34、對象數(shù)目的估計假設(shè)磁帶上記錄有Shakespeare全集，如何統(tǒng)計其中使用了多少個不同的單詞？為簡單起見，同一詞的復(fù)數(shù)，被動語態(tài)等可作為不同項(xiàng)設(shè)N是磁帶上總的單詞數(shù)，n是其中不同的數(shù)目方法一：對磁帶上的單詞進(jìn)行外部排序，時間θ(NlgN),空間需求較大方法二：在內(nèi)存中建一散列表，表中只存儲首次出現(xiàn)的單詞，平均時間O(N)，空間Ω(n)若能忍受某種誤差及已知n或N的上界M，則存在一個時空性能更好的概率算法解此問

35、題。設(shè)U是單詞序列的集合，設(shè)參數(shù)m稍大于lgM，可令設(shè)h：U → {0, 1}m 是一個散列函數(shù)，它用偽隨機(jī)數(shù)的方法將U中的單詞映射為長度為m的位串。(目的，減少存儲量),§1.3.3 概率計數(shù),,33,多重集合中不同對象數(shù)目的估計若y是一個長度為k的位串，用y[i]表示y的第i位，1≤ i ≤ k；用π(y, b), b ∈ {0, 1}來表示滿足y[i]=b的最小的i若y的位中沒有哪一位等于b，則y

36、[i]=k+1WordCount () {y[1..m+1] ← 0; // 初始化//順序讀磁帶for 磁帶上每個單詞x do {i ← π(h(x), 1); // x的散列值中等于1的最小位置，表示x是以 // 打頭的y[i] ← 1; // 將該位置置為1}return π(y, 0); // 返回y中等于0的最小位置

37、},§1.3.3 概率計數(shù),,34,多重集合中不同對象數(shù)目的估計例，不妨設(shè)m=4，h(x1)=0011, h(x2)=1010, h(x3)=0110, h(x4)=0010, 算法返回4也就是說，若算法返回4，說明磁帶上至少有3個單詞的散列地址是以1，01，001打頭的，但絕沒有以0001打頭的單詞?！咭粋€以0001開始的隨機(jī)二進(jìn)制串的概率是2-4=1/16∴在磁帶上不太可能有多

38、于16個互不相同的單詞(互不相同單詞的上界2k)因?yàn)橹灰猦的隨機(jī)性較好，則對16個不同的單詞xi，π(h(xi), 1) ≠4(這些單詞的散列值等于1的最小位置均不為4)的概率是(15/16)16 ≈ 35.6% ≈ e-1(每個xi不等于0001的概率的15/16，16個單詞均不以0001開頭的概率為35.6%)，只有此時算法才可能返回4。實(shí)際上，設(shè)算法的返回值是k，則Prob[k=4 | n=16] = 31.75%,

39、67;1.3.3 概率計數(shù),,35,多重集合中不同對象數(shù)目的估計相反，∵一個以001開始的隨機(jī)二進(jìn)制串的概率是2-3 ∴在磁帶上互不相同的單詞數(shù)目少于4的可能性不大(互不相同單詞的下界2k-2)因?yàn)?，?個互不相同的單詞中，至少有一個是以001打頭的概率為1-(7/8)4≈41.4%，Prob[k=4 | n=4] = 18.75%粗略的分析告訴我們：磁帶上互不相同的單詞數(shù)目為：2k-2～2k

40、實(shí)際上，算法WordCount估計的n應(yīng)等于2k/1.54703§1.3.5 線性代數(shù)中的數(shù)字問題例如，矩陣成法，求逆，計算特征值和特征向量只有一些特殊的應(yīng)用概率算法會執(zhí)行的比確定性算法要好。,§1.3.3 概率計數(shù),,36,Sherwood算法能夠平滑不同輸入對象的執(zhí)行時間設(shè)A是一個確定算法，tA(x)是解某個實(shí)例x的執(zhí)行時間，設(shè)n是一整數(shù)，Xn是大小為n的實(shí)例的集合假定Xn中每一個實(shí)例是等可能出

41、現(xiàn)的，則算法A解一個大小為n的實(shí)例的平均執(zhí)行時間是：這里無法消除這樣的可能性：存在一個size為n的實(shí)例x使得設(shè)B是一個概率算法，對每個size為n的實(shí)例x滿足這里tB(x)是算法B在實(shí)例x上的期望值，s(n)是概率算法為了取得均勻性所付出的成本。,§1.4 Sherwood算法,,37,雖然算法B的執(zhí)行時間也可能偶然地在某一個實(shí)例x上大于 ，但這種偶然性行為只是由于算法

42、所做的概率選擇引起的，與實(shí)例x本身沒有關(guān)系。因此，不再有最壞的情況的實(shí)例，但有最壞的執(zhí)行時間。算法B在一個size為n的實(shí)例集上的平均期望時間可定義為：很清楚 。也就是說Sherwood算法的平均執(zhí)行時間略為增加。,§1.4 Sherwood算法,,38,在n個元素中選擇第k個最小元素的算法關(guān)鍵在于選擇劃分元，有兩種常用的方法：精心挑選劃分元，使之是一個偽中值的元素

43、，這樣可使算法的最壞執(zhí)行時間是O(n)取當(dāng)前搜索區(qū)間的第一個元素作劃分元，平均時間為O(n)，但最壞時間是O(n2)。由于此方法簡單，故平均性能較前者好。該類確定算法的特點(diǎn)：設(shè)T[1..n]互不相同，算法的執(zhí)行時間不是依賴于數(shù)組元素的值，而是依賴于元素間的相對次序，因此，表達(dá)時間的函數(shù)不只是依賴于n，而且還依賴于δ，δ表示數(shù)組元素的排列設(shè) tp(n, δ) —— 使用偽中值算法的執(zhí)行時間 ts(n, δ)

44、 —— 使用簡單算法的執(zhí)行時間對多數(shù)的δ ，,§1.4.1 選擇與排序,,39,更精確地，設(shè)Sn是T中前n個數(shù)的排列的集合，|Sn|=n！，定義 ，于是有：但是：概率算法：隨機(jī)選擇T中的元素作為劃分元期望時間為O(n)，獨(dú)立于輸入實(shí)例注意：算法的某次執(zhí)行有可能達(dá)到O(n2)，但這種可能性與實(shí)例無關(guān)隨著n的增大

45、，這種可能性會很小。設(shè)tr(n, δ)是Sherwood算法的平均時間，則,§1.4.1 選擇與排序,,40,將選擇和排序的確定算法修改為Sherwood算法很簡單，但是當(dāng)算法較復(fù)雜，例如它是一個缺乏文檔資料的軟件包的一部分時，就很難對其進(jìn)行修改。注意，只有當(dāng)該算法平均時間性能較優(yōu)，但最壞性能較差時，才有修改的價值（一般情況如此）一個技巧是：將被解的實(shí)例變換到一個隨機(jī)實(shí)例。// 預(yù)處理用確定算法解此隨機(jī)實(shí)例，得到一

46、個解。將此解變換為對原實(shí)例的解。 // 后處理,§1.4.2 隨機(jī)的預(yù)處理,,41,設(shè)： f: X → Y 是解某問題用到的一個函數(shù)，且平均性能較優(yōu)(指相應(yīng)的算法)； n∈N，Xn是size為n的實(shí)例的集合 An是一個大小和Xn大小相同的集合，假定在An中能夠有效地均勻隨機(jī)抽樣A=∪An則隨機(jī)的預(yù)處理由一對函數(shù)構(gòu)成：u和v滿足三個性質(zhì)：①②③ 函數(shù)u

47、和v在最壞情況下能夠有效計算,§1.4.2 隨機(jī)的預(yù)處理,,42,于是確定算法f(x)可改造為Sherwood算法：RH(x) { // 用Sherwood算法計算f(x) n ← length[x]; // x的size為n r ← uniform(An); // 隨機(jī)取一元素 y ← u(x, r); //將原實(shí)例x轉(zhuǎn)化為隨機(jī)實(shí)例y s ← f(y); /

48、/ 用確定算法求y的解s return v(r, s); // 將s的解變換為x的解},§1.4.2 隨機(jī)的預(yù)處理,,43,例1：選擇和排序的Sherwood算法只需進(jìn)行隨機(jī)預(yù)處理將輸入實(shí)例中元素打亂即可，相當(dāng)于洗牌后處理無需進(jìn)行只需調(diào)用確定的算法前先調(diào)用：Shuffle (T) {n ← length[T];for i ← 1 to n-1 do { // 在T[i

49、..n]中隨機(jī)選1元素放在T[i]上 j ← uniform(1..n); T[i] ←> T[j];}},§1.4.2 隨機(jī)的預(yù)處理,,44,例2：離散對數(shù)計算離散對數(shù)計算困難使其可用于密碼算法，數(shù)字簽名等定義：設(shè) a=gx mod p記 logg,pa=x，稱x為a的(以g為底模除p)對數(shù)從p，g，a計算稱x為離散對數(shù)問題。簡單算法：① 計算gx對所有的x，最多計算

50、0≤x≤ p-1 或 1≤x≤p，實(shí)際上離散對數(shù)是循環(huán)群。② 驗(yàn)證a=gx mod p 是否成立。dlog(g, a, p) { // 當(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},§1.4.2 隨機(jī)的預(yù)處理,,4

51、5,問題：最壞O(p)循環(huán)次數(shù)難以預(yù)料當(dāng)滿足一定條件時平均循環(huán)p/2次當(dāng)p=24位十進(jìn)制數(shù)，循環(huán)1024次千萬億次/秒 (1016次/秒) 大約算1年(108秒/年)若p是數(shù)百位十進(jìn)制？隨機(jī)選擇都可能無法在可行的時間內(nèi)求解。假設(shè)有一個平均時間性能很好，但最壞情況差的確定算法求logp,ga，怎樣用Sherwood算法求解該問題？設(shè)p=19, g=2當(dāng)a=14, 6時，log2,1914 = 7, log

52、2,196=14，與a的取值相關(guān)當(dāng)用dlog求14的離散對數(shù)時，循環(huán)7次，求6的對數(shù)時要執(zhí)行14次，用sherwood算法應(yīng)該使得與a無關(guān)，用隨機(jī)預(yù)處理的方法計算logg,pa,§1.4.2 隨機(jī)的預(yù)處理,,46,定理(見p877, § 31.6) ① ②dlogRH(g, a p) { // 求logg,pa, a = gx mod p，求x // Sherwood算法 r ←

53、 uniform(0..p-2); b ← ModularExponent(g, r, p); //求冪模b=gr mod p c ← ba mod p; // y ← logg,pc; // 使用確定性算法求logp,gc, y=r+x return (y-r) mod (p-1); // 求x}Ex. 分析dlogRH的工作原理，指出該算法相應(yīng)的u和v,§1.4.2 隨機(jī)的預(yù)處

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

55、x的任何信息，因?yàn)閡(x,r)的概率分布(只要r是隨機(jī)均勻選擇的)是獨(dú)立于x的。,§1.4.2 隨機(jī)的預(yù)處理,,48,設(shè)兩個數(shù)組val[1..n]和ptr[1..n]及head構(gòu)成一個有序的靜態(tài)鏈表：val[head] ≤ val[ptr[head]] ≤ val[ptr[ptr[head]]] ≤ … ≤ val[ptrn-1[head]]例：,§1.4.3 搜索有序表,,49,若val[1..n]本身

56、有序，可用折半查找找某個給定的key，時間為O(lgn)。但因此處理鏈?zhǔn)浇Y(jié)構(gòu)，故最壞時間是Ω(n)。盡管如此，我們能夠找到一個確定性算法，平均時間為 。相應(yīng)的Sherwood算法的期望時間是 ，它雖然并不比確定性算法快，但他消除了最壞實(shí)例。假定表中元素互不相同，且所求的關(guān)鍵字表中存在，則給定x，我們是求下標(biāo)i，使val[i]=x,這里1≤i≤ n。任何實(shí)例可以有兩個參數(shù)刻畫：①前n個整數(shù)的排列δ

57、②x的rank,§1.4.3 搜索有序表,,50,設(shè)Sn是所有n!個排列的集合，設(shè)A是一個確定性算法⑴ tA(n, k, δ)表示算法A的執(zhí)行時間，此時間與被查找元素的秩k，以及val的排序δ相關(guān)。若A是一個概率算法，則tA(n, k, δ)表示算法的期望值。無論算法是確定的還是概率的，wA(n)和mA(n)表示最壞時間和平均時間，因此有：⑵ ⑶,§1.4.3 搜索有序表,,51,時間為O(n)的確定算

58、法設(shè)x≥val[i]且x在表中，則從位置i開始查找x的算法為：Search(x, i) { //仍可改進(jìn)while x > val[i] do i ← ptr[i];return i;}在表val[1..n]中查找x的算法為：A(x) {return Search(x, head);},§1.4.3 搜索有序表,,52,時間為O(n)的確定算法分析：設(shè)rank

59、(x)=k, 則： —— 算法A在n個元素的表中查找x所需的訪問數(shù)組元素的次數(shù)，顯然與δ無關(guān) —— 算法A最壞時的訪問次數(shù) —— 算法A平均的訪問次數(shù)① ②③,§1.4.3 搜索有序表,,53,時間為O(n)的概率算法D(x) {i ← uniform(1..n);y ← val[i];case { x y: return Se

60、arch(x, ptr[i]); // case2 otherwise: return i; // x = y}},§1.4.3 搜索有序表,,54,時間為O(n)的概率算法性能分析：① 設(shè)rank(x)=k, rank(val[i])=j (D訪問數(shù)組次數(shù))若 k j, 則 ，屬于case2，從第j小元素搜索若 k = j, 則

61、 ，屬于case3② ③,§1.4.3 搜索有序表,,55,平均時間為 的確定算法B(x) { //設(shè)x在val[1..n]中i ← head;max ← val[i]; // max初值是表val中最小值for j ← i to do { // 在前 個數(shù)中找不大于x

62、 // 的最大整數(shù)y相應(yīng)下標(biāo)i y ← val[j]; if max < y ≤x then {i ← j; max ← y; }} // endforreturn Search(x, i); // 從y向后搜索}for循環(huán)的目的：找不超過x的最大整數(shù)y，使搜索從y開始，若將val[1..

63、n]中的n個整數(shù)看作是均勻隨機(jī)分布的，則在val[1..l]中求y值就相當(dāng)于在n個整數(shù)中，隨機(jī)地取l個整數(shù)，求這l個整數(shù)中不大于x的最大整數(shù)y。,§1.4.3 搜索有序表,,56,平均時間為 的確定算法算法分析：可用一個與l和n相關(guān)的隨機(jī)變量來分析，更簡單的分析如下：設(shè)n個整數(shù)的排列滿足：a1 < a2 <…<an將其等分為l個區(qū)間：若均勻隨機(jī)地從表中取l

64、個數(shù)，則平均每個區(qū)間中被選到1一個元素，因此無論x是處在哪一個區(qū)間，其平均的執(zhí)行時間為：i) 若在x的同一區(qū)間中取到的數(shù)小于等于x，則Search的比較次數(shù)不超過區(qū)間長度n/l。ii) 若在x的同一區(qū)間中取到的數(shù)大于x，則在x的前一區(qū)間中的y必定小于x，且x和y的距離平均為n/l，此時Search的比較次數(shù)平均為n/l。,§1.4.3 搜索有序表,,57,平均時間為 的確定算法算法分析：注

65、意，在Search前需執(zhí)行l(wèi)次循環(huán)，故有因此，確定性算法中for的次數(shù)為 ，此時算法的平均時間 最小。Ex. 寫一Sherwood算法C，與算法A, B, D比較，給出實(shí)驗(yàn)結(jié)果。,§1.4.3 搜索有序表,,58,Las Vegas和Sherwood算法比較Sherwood算法一般并不比相應(yīng)的確定算法的平均性能優(yōu)Las Vegas一般能獲得更有效率的算法，有時甚至是對每個實(shí)例皆如

66、此Sherwood算法可以計算出一個給定實(shí)例的執(zhí)行時間上界Las Vegas算法的時間上界可能不存在，即使對每個較小實(shí)例的期望時間，以及對特別耗時的實(shí)例的概率較小可忽略不計時。Las Vegas 特點(diǎn)可能不時地要冒著找不到解的風(fēng)險，算法要么返回正確的解，要么隨機(jī)決策導(dǎo)致一個僵局。若算法陷入僵局，則使用同一實(shí)例運(yùn)行同一算法，有獨(dú)立的機(jī)會求出解。成功的概率隨著執(zhí)行時間的增加而增加。算法的一般形式LV(x, y,

67、success) —— x是輸入的實(shí)例，y是返回的參數(shù)，success是布爾值，true表示成功，false表示失敗p(x) —— 對于實(shí)例x，算法成功的概率,§1.5 Las Vegas 算法,{,{,,59,算法的一般形式s(x) —— 算法成功時的期望時間e(x) —— 算法失敗時的期望時間一個正確的算法，要求對每個實(shí)例x， p(x)>0，更好的情況是Obstinate(x) {repe

68、atLV(x, y, success);until success;return y; }設(shè)t(x)是算法obstinate找到一個正確解的期望時間，則若要最小化t(x)， 則需在p(x), s(x)和e(x)之間進(jìn)行某種折衷，例如，若要較少失敗的時間，則可降低成功的概率p(x)。,§1.5 Las Vegas 算法,,60,傳統(tǒng)的回溯法置當(dāng)前行為第1行，當(dāng)前列為第1列，即i←j←1;

69、while i ≤ 8 do { // 當(dāng)前行號≤ 8檢查當(dāng)前行：從當(dāng)前列j起向后逐列試探，尋找安全列號；if 找到安全列號 then { 放置皇后，將列號記入棧中，并將下一行置為當(dāng)前行，即i++; j←1; //當(dāng)前列置為1} else { 退?；厮莸缴弦恍?，即i--； 移去該行已已放置的皇后，以該皇后所在列的下一列作為當(dāng)前 列；}},§

70、;1.5.1 8后問題,,61,,61,§1.5.1 8后問題,2.Las Vegas方法向量try[1..8]中存放結(jié)果try[i]——表示第i個皇后放在（i，try[i])位置上try[1..k]稱為k-promising是指：若k個皇后的位置(0≤k ≤8): (1,try[1]),(2,try[2]),…,(k,try[k])互相不攻擊，則稱try[1..k]是k-promising的.形式化：對