概率算法新-精品教育課件

1、1算法設(shè)計(jì)與分析黃劉生中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系 國(guó)家高性能計(jì)算中心（合肥）2019.8.192第一部分概率算法3Ch.1 緒論1. 故事：想象自己是神化故事的主人公，你有一張不易懂的地圖，上面描述了一處寶藏的藏寶地點(diǎn)。經(jīng)分析你能確定最有可能的兩個(gè)地點(diǎn)是藏寶地點(diǎn)，但二者相距甚遠(yuǎn)。假設(shè)你如果已到達(dá)其中一處，就立即知道該處是否為藏寶地點(diǎn)。你到達(dá)兩處之一地點(diǎn)及從其中一處到另一處的距離是5天的行程。進(jìn)一步假設(shè)有一條惡龍，每晚光顧寶藏并從中拿走一部分財(cái)寶。假設(shè)你取寶藏的方案有兩種：1.1 引言4 方案1. 花4天的時(shí)間計(jì)算出準(zhǔn)確的藏寶地點(diǎn)，然后出發(fā)尋寶，一旦出發(fā)不能重新計(jì)算 方案2. 有一個(gè)小精靈告訴你地

2、圖的秘密，但你必須付給他報(bào)酬，相當(dāng)于龍3晚上拿走的財(cái)寶 Prob 1.1.1 若忽略可能的冒險(xiǎn)和出發(fā)尋寶的代價(jià)，你是否接受小精靈的幫助？ 顯然，應(yīng)該接受小精靈的幫助，因?yàn)槟阒恍杞o出3晚上被盜竊的財(cái)寶量，否則你將失去4晚被盜財(cái)寶量。 但是，若冒險(xiǎn)，你可能做得更好！1.1 引言5 設(shè)x是你決定之前當(dāng)日的寶藏價(jià)值，設(shè)y是惡龍每晚盜走的寶藏價(jià)值，并設(shè)x9y 方案1：4天計(jì)算確定地址，行程5天，你得到的寶藏價(jià)值為：x-9y 方案2：3y付給精靈，行程5天失去5y，你得到的寶藏價(jià)值為：x-8y 方案3：投硬幣決定先到一處，失敗后到另一處(冒險(xiǎn)方案) 一次成功所得：x-5y，機(jī)會(huì)1/2 二次成功所得：x-1

3、0y，機(jī)會(huì)1/21.1 引言期望贏利：x-7.5y62. 意義 該故事告訴我們：當(dāng)一個(gè)算法面臨某種選擇時(shí)，有時(shí)隨機(jī)選擇比耗時(shí)做最優(yōu)選擇更好，尤其是當(dāng)最優(yōu)選擇所花的時(shí)間大于隨機(jī)選擇的平均時(shí)間的時(shí)侯 顯然，概率算法只能是期望的時(shí)間更有效，但它有可能遭受到最壞的可能性。73. 期望時(shí)間和平均時(shí)間的區(qū)別確定算法的平均執(zhí)行時(shí)間 輸入規(guī)模一定的所有輸入實(shí)例是等概率出現(xiàn)時(shí)，算法的平均執(zhí)行時(shí)間。概率算法的期望執(zhí)行時(shí)間 反復(fù)解同一個(gè)輸入實(shí)例所花的平均執(zhí)行時(shí)間。 因此，對(duì)概率算法可以討論如下兩種期望時(shí)間平均的期望時(shí)間：所有輸入實(shí)例上平均的期望執(zhí)行時(shí)間最壞的期望時(shí)間：最壞的輸入實(shí)例上的期望執(zhí)行時(shí)間84. 例子快速排

4、序中的隨機(jī)劃分要求學(xué)生寫一算法，由老師給出輸入實(shí)例，按運(yùn)行時(shí)間打分，大部分學(xué)生均不敢用簡(jiǎn)單的劃分，運(yùn)行時(shí)間在1500-2600ms，三個(gè)學(xué)生用概率的方法劃分，運(yùn)行時(shí)間平均為300ms。8皇后問題系統(tǒng)的方法放置皇后(回溯法)較合適，找出所有92個(gè)解 O(2n)，若只找92個(gè)其中的任何一個(gè)解可在線性時(shí)間內(nèi)完成O(n)。 隨機(jī)法：隨機(jī)地放置若干皇后能夠改進(jìn)回溯法，特別是當(dāng)n較大時(shí)判斷大整數(shù)是否為素?cái)?shù)確定算法無(wú)法在可行的時(shí)間內(nèi)判斷一個(gè)數(shù)百位十進(jìn)制數(shù)是否素?cái)?shù)，否則密碼就不安全。 概率算法將有所作為：若能接受一個(gè)任意小的錯(cuò)誤的概率95. 概率算法的特點(diǎn) (1) 不可再現(xiàn)性 在同一個(gè)輸入實(shí)例上，每次執(zhí)行結(jié)果

5、不盡相同，例如N-皇后問題概率算法運(yùn)行不同次將會(huì)找到不同的正確解找一給定合數(shù)的非平凡因子每次運(yùn)行的結(jié)果不盡相同，但確定算法每次運(yùn)行結(jié)果必定相同 (2) 分析困難 要求有概率論，統(tǒng)計(jì)學(xué)和數(shù)論的知識(shí)106. 約定 隨機(jī)函數(shù)uniform：隨機(jī)，均勻，獨(dú)立設(shè)a，b為實(shí)數(shù)，ab, uniform(a, b) 返回x，a x b 設(shè)i，j為整數(shù)，ij, uniform(i.j)=k, i k j 設(shè)X是非空有限集， uniform(X) X 11例1：設(shè)p是一個(gè)素?cái)?shù)，a是一個(gè)整數(shù)滿足1a0 do if (j is odd) s sa mod p;a a2 mod p;j j div 2;return s

6、;Draw (a, p) / 在X中隨機(jī)取一元素j uniform(1.p-1);return ModularExponent(a, j, p); / 在X中隨機(jī)取一元素13偽隨機(jī)數(shù)發(fā)生器在實(shí)用中不可能有真正的隨機(jī)數(shù)發(fā)生器，多數(shù)情況下是用偽隨機(jī)數(shù)發(fā)生器代替。大多數(shù)偽隨機(jī)數(shù)發(fā)生器是基于一對(duì)函數(shù)：S: X X, 這里X足夠大，它是種子的值域R: X Y, Y是偽隨機(jī)數(shù)函數(shù)的值域使用S獲得種子序列：x0=g, xi=S(xi-1), i0然后使用R獲得偽隨機(jī)序列：yi=R(xi), i 0該序列必然是周期性的，但只要S和R選的合適，該周期長(zhǎng)度會(huì)非常長(zhǎng)。TC中可用rand()和srand(time),

7、 用GNU C更好14基本特征隨機(jī)決策在同一實(shí)例上執(zhí)行兩次其結(jié)果可能不同在同一實(shí)例上執(zhí)行兩次的時(shí)間亦可能不太相同分類Numerical, Monte Carlo, Las Vegas, Sherwood.很多人將所有概率算法(尤其是數(shù)字的概率算法)稱為Monte Carlo算法1.2 概率算法的分類15數(shù)字算法隨機(jī)性被最早用于求數(shù)字問題的近似解例如，求一個(gè)系統(tǒng)中隊(duì)列的平均長(zhǎng)度的問題，確定算法很難得到答案概率算法獲得的答案一般是近似的，但通常算法執(zhí)行的時(shí)間越長(zhǎng)，精度就越高，誤差就越小使用的理由現(xiàn)實(shí)世界中的問題在原理上可能就不存在精確解例如，實(shí)驗(yàn)數(shù)據(jù)本身就是近似的，一個(gè)無(wú)理數(shù)在計(jì)算機(jī)中只能近似地表

8、示精確解存在但無(wú)法在可行的時(shí)間內(nèi)求得有時(shí)答案是以置信區(qū)間的形式給出的1.2 概率算法的分類16Monte Carlo算法 (MC算法)蒙特卡洛算法1945年由J. Von Neumann進(jìn)行核武模擬提出的。它是以概率和統(tǒng)計(jì)的理論與方法為基礎(chǔ)的一種數(shù)值計(jì)算方法，它是雙重近似：一是用概率模型模擬近似的數(shù)值計(jì)算，二是用偽隨機(jī)數(shù)模擬真正的隨機(jī)變量的樣本。這里我們指的MC算法是：若問題只有1個(gè)正確的解，而無(wú)近似解的可能時(shí)使用MC算法例如，判定問題只有真或假兩種可能性，沒有近似解 因式分解，我們不能說(shuō)某數(shù)幾乎是一個(gè)因子特點(diǎn)：MC算法總是給出一個(gè)答案，但該答案未必正確，成功(即答案是正確的)的概率正比于算法

9、執(zhí)行的時(shí)間缺點(diǎn)：一般不能有效地確定算法的答案是否正確1.2 概率算法的分類17Las Vegas算法 (LV算法)LV算法絕不返回錯(cuò)誤的答案。特點(diǎn)：獲得的答案必定正確，但有時(shí)它仍根本就找不到答案。 和MC算法一樣，成功的概率亦隨算法執(zhí)行時(shí)間增加而增加。無(wú)論輸入何種實(shí)例，只要算法在該實(shí)例上運(yùn)行足夠的次數(shù)，則算法失敗的概率就任意小。 Sherwood算法Sherwood算法總是給出正確的答案。當(dāng)某些確定算法解決一個(gè)特殊問題平均的時(shí)間比最壞時(shí)間快得多時(shí)，我們可以使用Sherwood算法來(lái)減少，甚至是消除好的和壞的實(shí)例之間的差別。1.2 概率算法的分類18這類算法主要用于找到一個(gè)數(shù)字問題的近似解2.1

10、 值計(jì)算實(shí)驗(yàn)：將n根飛鏢隨機(jī)投向一正方形的靶子，計(jì)算落入此正方形的內(nèi)切圓中的飛鏢數(shù)目k。假定飛鏢擊中方形靶子任一點(diǎn)的概率相等(用計(jì)算機(jī)模擬比任一飛鏢高手更能保證此假設(shè)成立)設(shè)圓的半徑為r，面積s1= r2； 方靶面積s2=4r2由等概率假設(shè)可知落入圓中的飛鏢和正方形內(nèi)的飛鏢平均比為：由此知： Ch.2 數(shù)字概率算法19求近似值的算法為簡(jiǎn)單起見，只以上圖的右上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)return 4k/

11、n;實(shí)驗(yàn)結(jié)果： =3.141592654n = 1000萬(wàn): 3.140740, 3.142568 (2位精確)n = 1億: 3.141691, 3.141363 (3位精確)n = 10億: 3.141527, 3.141507 (4位精確)2.1 值計(jì)算20求近似值的算法Ex.1 若將y uniform(0, 1) 改為 y x, 則上述的算法估計(jì)的值是什么？2.1 值計(jì)算21Monte Carlo積分(但不是指我們定義的MC算法)1、概率算法1設(shè)f: 0, 1 0, 1是一個(gè)連續(xù)函數(shù)，則由曲線y=f(x), x軸, y軸和直線x=1圍成的面積由下述積分給出：向單位面積的正方形內(nèi)投鏢n次

12、，落入陰影部分的鏢的數(shù)目為k，則顯然，只要n足夠大2.2 數(shù)字積分 (計(jì)算定積分的值)22概率算法1HitorMiss (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ì)算定積分的值)23概率算法1Ex2. 在機(jī)器上用 估計(jì)值，給出不同的n值及精度。Ex3. 設(shè)a, b, c和d是實(shí)數(shù)，且a b, c d, f:a, b c, d是一個(gè)連續(xù)函數(shù)，寫一概率算法計(jì)算積分：注意，函數(shù)的參數(shù)是a, b, c, d, n

13、和f, 其中f用函數(shù)指針實(shí)現(xiàn)，請(qǐng)選一連續(xù)函數(shù)做實(shí)驗(yàn)，并給出實(shí)驗(yàn)結(jié)果。2.2 數(shù)字積分 (計(jì)算定積分的值)24概率算法1*Ex4. 設(shè),是(0,1)之間的常數(shù)，證明：若I是 的正確值，h是由HitorMiss算法返回的值，則當(dāng)n I(1-I)/2時(shí)有：Prob|h-I| 1 上述的意義告訴我們：Prob|h-I| , 即：當(dāng)n I(1-I)/ 2時(shí)，算法的計(jì)算結(jié)果的絕對(duì)誤差超過(guò)的概率不超過(guò)，因此我們根據(jù)給定和可以確定算法迭代的次數(shù)解此問題時(shí)可用切比雪夫不等式，將I看作是數(shù)學(xué)期望。2.2 數(shù)字積分 (計(jì)算定積分的值)25概率算法2更有效的概率算法是：在積分區(qū)間上隨機(jī)均勻地產(chǎn)生點(diǎn)，求出這些點(diǎn)上的函數(shù)

14、值的算術(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ì)算定積分的值)26概率算法2用HitorMiss和Crude運(yùn)行三次的結(jié)果為：假定 和 存在，由算法求得的估算值的方差反比于點(diǎn)數(shù)n。當(dāng)n足夠大時(shí)，估計(jì)的分布近似為正態(tài)分布。對(duì)于給定的迭代次數(shù)n，Crude算法的方差不會(huì)大于HitorMiss的方差。但不能說(shuō)，Crude算法總是優(yōu)于HitorMiss。因?yàn)楹笳咴诮o定的時(shí)間內(nèi)能迭代的次數(shù)更多。例如，計(jì)算值時(shí)，Crud

15、e需計(jì)算平方根，而用投鏢算法darts時(shí)無(wú)需計(jì)算平方根。2.2 數(shù)字積分 (計(jì)算定積分的值)27確定的算法梯形算法將區(qū)間分為n-1個(gè)子區(qū)間，每個(gè)子區(qū)間內(nèi)的長(zhǎng)度為，Trapezoid (f, n, a, b) / 假設(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ì)算定積分的值)28確定的算法 當(dāng)n=100, =3.140399 當(dāng)n=1,000, =3.141555 當(dāng)n=10,000, =3.1415

16、86 當(dāng)n=100,000, =3.141593一般地，在同樣的精度下，梯形算法的迭代次數(shù)少于MC積分，但是有時(shí)確定型積分算法求不出解：例如， f(x)=sin2(100)! x)， 。 但是用梯形算法時(shí)，當(dāng)2 n101時(shí)，返回值是0。若用MC積分則不會(huì)發(fā)生該類問題，或雖然發(fā)生，但概率小得多。2.2 數(shù)字積分 (計(jì)算定積分的值)29多重積分 在確定算法中，為了達(dá)到一定的精度，采樣點(diǎn)的數(shù)目隨著積分維數(shù)成指數(shù)增長(zhǎng)，例如，一維積分若有100個(gè)點(diǎn)可達(dá)到一定的精度，則二維積分可能要計(jì)算1002個(gè)點(diǎn)才能達(dá)到同樣的精度，三維積分則需計(jì)算1003個(gè)點(diǎn)。(系統(tǒng)的方法) 但概率算法對(duì)維數(shù)的敏感度不大，僅是每次迭代

17、中計(jì)算的量稍增一點(diǎn)，實(shí)際上，MC積分特別適合用于計(jì)算4或更高維數(shù)的定積分。 若要提高精度，則可用混合技術(shù)：部分采用系統(tǒng)的方法，部分采用概率的方法2.2 數(shù)字積分 (計(jì)算定積分的值)30 上一節(jié)可以認(rèn)為，數(shù)字概率算法被用來(lái)近似一個(gè)實(shí)數(shù)，本節(jié)可用它們來(lái)估計(jì)一個(gè)整數(shù)值。例如，設(shè)X為有限集，若要求X的勢(shì)|X|，則當(dāng)X較大時(shí)，枚舉顯然不現(xiàn)實(shí)。問題：隨機(jī)選出25人，你是否愿意賭其中至少有兩個(gè)人生日相同嗎？直覺告訴我們，一般人都不愿意賭其成立，但實(shí)際上成立的概率大于50%。2.3 概率計(jì)數(shù)31 一般地，從n個(gè)對(duì)象中選出k個(gè)互不相同的對(duì)象，若考慮 選擇的次序，則不同的選擇有 種；若允許重復(fù)選取同 一對(duì)象，則不

18、同的選法共有 種。 因此，從n個(gè)對(duì)象(允許同一對(duì)象重復(fù)取多次)中隨機(jī)均勻地選擇出的k個(gè)對(duì)象互不相同的概率是： ，注意a，b和b，a是不同的取法。由此可知，上述問題中，25個(gè)人生日互不相同的概率是：這里假設(shè)：不考慮潤(rùn)年，一年中人的生日是均勻分布的。2.3 概率計(jì)數(shù)32由Stirling公式知：可得 假定 Tj;3.2 隨機(jī)的預(yù)處理52例2：離散對(duì)數(shù)計(jì)算離散對(duì)數(shù)計(jì)算困難使其可用于密碼算法，數(shù)字簽名等定義：設(shè) a=gx mod p，記 logg,pa=x，稱x為a的(以g為底模除p)對(duì)數(shù)。 從p，g，a計(jì)算x稱為離散對(duì)數(shù)問題。簡(jiǎn)單算法 計(jì)算gx對(duì)所有的x，最多計(jì)算0 x p-1 或 1xp，因?yàn)閷?shí)際

19、上離散對(duì)數(shù)是循環(huán)群； 驗(yàn)證a=gx mod p 是否成立。dlog(g, a, p) / 當(dāng)這樣的對(duì)數(shù)不存在時(shí)，算法返回p x 0; y 1; do x+; y y*g; / 計(jì)算y=gx while ( a y mod p) and (x p); return x53問題：最壞O(p)循環(huán)次數(shù)難以預(yù)料，當(dāng)滿足一定條件時(shí)平均循環(huán)p/2次當(dāng)p=24位十進(jìn)制數(shù)，循環(huán)1024次，千萬(wàn)億次/秒 (1016次/秒) 大約算1年(108秒/年)若p是數(shù)百位十進(jìn)制？隨機(jī)選擇都可能無(wú)法在可行的時(shí)間內(nèi)求解。假設(shè)有一個(gè)平均時(shí)間性能很好，但最壞情況差的確定算法求logg,pa，怎樣用Sherwood算法求解該問題？

20、設(shè)p=19, g=2當(dāng)a=14, 6時(shí)，log2,1914 = 7, log2,196=14，即用dlog求14和6的離散對(duì)數(shù)時(shí)，分別要循環(huán)7和14次，執(zhí)行時(shí)間與a的取值相關(guān)。 用sherwood算法應(yīng)該使得與a無(wú)關(guān)，用隨機(jī)預(yù)處理的方法計(jì)算logg,pa例2：離散對(duì)數(shù)計(jì)算54定理(見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)(gxmod

21、p)modp=gr+xmodp=c y logg,pc; / 使用確定性算法求logp,gc, y=r+x return (y-r) mod (p-1); / 求xEx. 分析dlogRH的工作原理，指出該算法相應(yīng)的u和v3.2 隨機(jī)的預(yù)處理55隨機(jī)預(yù)處理提供了一種加密計(jì)算的可能性 假定你想計(jì)算某個(gè)實(shí)例x，通過(guò)f(x)計(jì)算，但你缺乏計(jì)算能力或是缺乏有效算法，而別人有相應(yīng)的計(jì)算能力，愿意為你計(jì)算(可能會(huì)收費(fèi))，若你愿意別人幫你計(jì)算，但你不愿意泄露你的輸入實(shí)例x，你將如何做？可將隨機(jī)預(yù)處理使用到f的計(jì)算上： 使用函數(shù)u將x加密為某一隨機(jī)實(shí)例y 將y提交給f計(jì)算出f(y)的值 使用函數(shù)v轉(zhuǎn)換為f(x

22、) 上述過(guò)程，他人除了知道你的實(shí)例大小外，不知道x的任何信息，因?yàn)閡(x,r)的概率分布(只要r是隨機(jī)均勻選擇的)是獨(dú)立于x的。3.2 隨機(jī)的預(yù)處理56 設(shè)兩個(gè)數(shù)組val1.n和ptr1.n及head構(gòu)成一個(gè)有序的靜態(tài)鏈表：valhead valptrhead valptrptrhead valptrn-1head例：3.3 搜索有序表 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 57折半查找： 若val1.n本身有序，可用折半查找找某個(gè)給定的

23、key，時(shí)間為O(lgn)。順序查找：但此表為鏈?zhǔn)浇Y(jié)構(gòu)，故最壞時(shí)間是(n)。盡管如此，我們能夠找到一個(gè)確定性算法，平均時(shí)間為 。 相應(yīng)的Sherwood算法的期望時(shí)間是 ，它雖然并不比確定性算法快，但他消除了最壞實(shí)例。 假定表中元素互不相同，且所求的關(guān)鍵字在表中存在，則給定x，我們是求下標(biāo)i，使vali=x, 這里1i n。任何實(shí)例可以由兩個(gè)參數(shù)刻畫： 前n個(gè)整數(shù)的排列 x的rank3.3 搜索有序表58設(shè)Sn是所有n!個(gè)排列的集合，設(shè)A是一個(gè)確定性算法 tA(n, k, )表示算法A的執(zhí)行時(shí)間，此時(shí)間與被查找元素的秩k，以及val的排列相關(guān)。若A是一個(gè)概率算法，則tA(n, k, )表示算法

24、的期望值。無(wú)論算法是確定的還是概率的，wA(n)和mA(n)分別表示最壞時(shí)間和平均時(shí)間，因此有： 3.3 搜索有序表59時(shí)間為O(n)的確定算法算法設(shè)xvali且x在表中，則從位置i開始查找x的算法為Search(x, i) /仍可改進(jìn)while x vali do i ptri;return i;在表val1.n中查找x的算法為：A(x) return Search(x, head);3.3 搜索有序表60性能分析設(shè)rank(x)=k, 則： 算法A在n個(gè)元素的表中查找x所需的訪問數(shù)組元素的次數(shù)，顯然與無(wú)關(guān) 算法A最壞時(shí)的訪問次數(shù) 算法A平均的訪問次數(shù) 3.3 搜索有序表61時(shí)間為O(n)的

25、概率算法算法 D(x) i uniform(1.n);y vali;case x y: return Search(x, ptri); / case2 otherwise: return i; / case3， x = y3.3 搜索有序表62性能分析(D訪問數(shù)組次數(shù)) 一般情況 設(shè)rank(x)=k, rank(vali)=j 若 k j, 則 ，屬于case2，從jth最小元之后搜索若 k = j, 則 ，屬于case3 最壞情況3.3 搜索有序表63 平均情況3.3 搜索有序表64平均時(shí)間為 的確定算法算法B(x) /設(shè)x在val1.n中i head;max vali; / max初值是

26、表val中最小值for j 1 to do / 在val的前 個(gè)數(shù)中找不大于x y val j ; / 的最大整數(shù)y相應(yīng)的下標(biāo)i if max y x then i j; max y; /endif / endforreturn Search(x, i); / 從y開始繼續(xù)搜索3.3 搜索有序表65性能分析 for循環(huán)的目的：找不超過(guò)x的最大整數(shù)y，使搜索從y開始，若將val1.n中的n個(gè)整數(shù)看作是均勻隨機(jī)分布的，則在val1.L中求y值就相當(dāng)于在n個(gè)整數(shù)中，隨機(jī)地取L個(gè)整數(shù)，求這L個(gè)整數(shù)中不大于x的最大整數(shù)y。 可用一個(gè)與L和n相關(guān)的隨機(jī)變量來(lái)分析，更簡(jiǎn)單的分析如下：設(shè)n個(gè)整數(shù)的排列滿足：a

27、1 a2 0，更好的情況是：Ch.4 Las Vegas 算法70Obstinate(x) repeatLV(x, y, success);until success;return y; 設(shè)t(x)是算法obstinate找到一個(gè)正確解的期望時(shí)間，則 若要最小化t(x)，則需在p(x), s(x)和e(x)之間進(jìn)行某種折衷，例如，若要減少失敗的時(shí)間，則可降低成功的概率p(x)。Ch.4 Las Vegas 算法71傳統(tǒng)的回溯法4.1 8后問題72置當(dāng)前行為第1行，當(dāng)前列為第1列，即ij1;while i 8 do / 當(dāng)前行號(hào) 8檢查當(dāng)前行：從當(dāng)前列j起向后逐列試探，尋找安全列號(hào)；if 找到安

28、全列號(hào) then 放置皇后，將列號(hào)記入棧，并將下一行置為當(dāng)前行(i+); j1; /當(dāng)前列置為1 else 退?；厮莸缴弦恍?，即i-； 移去該行已放置的皇后，以該皇后所在列的下一列作為當(dāng) 前列；4.1 8后問題73734.1 8后問題2.Las Vegas方法向量try1.8中存放結(jié)果tryi表示第i個(gè)皇后放在（i，tryi)位置上try1.k稱為k-promising是指：若k個(gè)皇后的位置(0k 8): (1,try1), (2,try2), , (k,tryk)互相不攻擊，則稱try1.k是k-promising的.形式化：對(duì) ，若 有 (式1)若式1成立，則：無(wú)行沖突：無(wú)須考慮，因?yàn)榈趇

29、個(gè)皇后放在第i行，故同一行不會(huì)有兩皇后74744.1 8后問題無(wú)列沖突：若對(duì)任意不同的兩行i、j，因?yàn)槠淞袛?shù)之差不為0，故任意兩皇后不可能在同一列上。135對(duì)角線無(wú)沖突： 和 沖突時(shí)有： 即 故任兩皇后不會(huì)在135對(duì)角線上沖突。45對(duì)角線無(wú)沖突： 和 沖突時(shí)有：即tryi-tryj=i-j故任兩皇后不會(huì)在45對(duì)角線上沖突。綜上所述，式1成立時(shí)try1.k是k-promising。顯然，若k 1，則向量try1.k是k-promising的，對(duì)8后問題，解是8-promising的。算法7575 QueensLv (success) /貪心的LV算法，所有皇后都是隨機(jī)放置/若Success=tr

30、ue，則try1.8包含8后問題的一個(gè)解。 col,diag45,diag135；/列及兩對(duì)角線集合初值為空 k 0；/行號(hào) repeat /try1.k是k-promising，考慮放第k+1個(gè)皇后 nb 0；/計(jì)數(shù)器，nb值為（k+1)th皇后的open位置總數(shù) for i 1 to 8 do /i是列號(hào) if (i col) and (i-k-1 diag45) and (i+k+1 diag135) then /列i對(duì)（k+1）th皇后可用，但不一定馬上將其放在第i列 nb nb+1； if uniform(1.nb)=1 then /或許放在第i列 j i；/注意第一次uniform

31、一定返回1，即j一定有值1 /endif /endfor，在nb個(gè)安全的位置上隨機(jī)選擇1個(gè)位置j放置之76764.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 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-promisin

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

33、V算法過(guò)于消極，一旦失敗，從頭再來(lái)樂觀：回溯法過(guò)于樂觀，一旦放置某個(gè)皇后失敗，就進(jìn)行系統(tǒng)回退一步的策略，而這一步往往不一定有效。 折中：會(huì)更好嗎？一般情況下為此。先用LV方法隨機(jī)地放置前若干個(gè)結(jié)點(diǎn)，例如k個(gè)。然后使用回溯法放置后若干個(gè)結(jié)點(diǎn)，但不考慮重放前k個(gè)結(jié)點(diǎn)。若前面的隨機(jī)選擇位置不好，可能使得后面的位置不成功，如若前兩個(gè)皇后的位置是1、3。隨機(jī)放置的皇后越多，則后續(xù)回溯階段的平均時(shí)間就越少，失敗的概率也就越大。79794.1 8后問題改進(jìn)算法 折中算法只需將QueensLV的最后兩行改為：until nb = 0 or k = stepVegas；if （nb0)then /已隨機(jī)放好st

34、opVegas個(gè)皇后 backtrace (k, col, diag45, diag135,success);else success false；stepVegas控制隨機(jī)放置皇后的個(gè)數(shù)，如何選擇？ 改進(jìn)算法的試驗(yàn)結(jié)果：8080純回溯時(shí)間：40msstepVegas=2 or 3：10ms（平均）純貪心LV：23ms（平均）結(jié)論：一半略少的皇后隨機(jī)放置較好。StepVegaspset011141141139.6339.6320.87522.5339.6728.2030.493113.4815.1029.0140.261810.318.7935.1050.16249.337.2946.9260

35、.13579.056.9853.5070.129396.9755.9380.129396.9753.9381814.1 8后問題-問題1：為什么僅隨機(jī)放一個(gè)皇后，其效果就會(huì)大大優(yōu)于純回溯方法？82824.1 8后問題-問題2：預(yù)先隨機(jī)選幾個(gè)皇后放置為好？由于解缺乏規(guī)律性（至少在皇后數(shù)不等于4k+2，k為某整數(shù)時(shí)），故求出stepVegas的最優(yōu)值較難，但是找到一個(gè)較好（不一定是最優(yōu)）的stepVegas還是可以的。12皇后：StepVegaspset時(shí)間01262262125ms50.503933.8847.2380.3937ms120.04651310.2222.11基本與純回溯相同8383

36、4.1 8后問題在Apple II機(jī)器上，20個(gè)皇后：確定性的回溯算法：找到第一個(gè)解的時(shí)間大于2個(gè)小時(shí)。概率算法，隨機(jī)地放置前10個(gè)皇后：5分半鐘找到36個(gè)不同的解。后者找一個(gè)接比前者大約快1000倍！-Obstinate算法在何時(shí)無(wú)限循環(huán)？當(dāng)問題不存在解時(shí)。對(duì)于n皇后，要求n=4，即問題至少有一個(gè)解存在時(shí)，Obstinate算法才有可能結(jié)束。Ex. 寫一算法，求n=1220時(shí)最優(yōu)的StepVegas值。84844.2 模p平方根定義1：設(shè)p是一個(gè)奇素?cái)?shù)，若整數(shù)x1,p-1且存在一個(gè)整數(shù)y，使則稱x為模p的二次剩余（quadratic residue），若y 1,p-1，則y稱為x模p的平方根

37、。例：63是55模103的平方根，55是模103的二次剩余。定義2：若整數(shù) ，且z不是模p的二次剩余，則z是模p的非二次剩余。85854.2 模p平方根定理1：任何一個(gè)模p的二次剩余至少有兩個(gè)不同的平方根pf：設(shè)x是模p的二次剩余，y是x模p的平方根。因?yàn)楣手灰Cp-yy且1p-yp-1就可證明p-y是不同于y的x模p的另一個(gè)平方根。p是奇數(shù)， p-yy，否則p是偶數(shù)。另一方面， 1yp-1，p-y p (p-1)=1 /yp-1 p-yp-1 /y186864.2 模p平方根定理2：任一模p的二次剩余至多有兩個(gè)不同的平方根pf：設(shè) a和b是x模p的平方根。即 成立。若k=0，則a=b若k0，

38、則ab不妨設(shè)ab. 又 ，由Th31.7知即 即 ， 也就是說(shuō)任意兩個(gè)不同的平方根，均只有b和(p-b)兩種不同形式。87874.2 模p平方根定理3：1到p-1之間的整數(shù)恰有一半是模p的二次剩余.pf：由定理1和定理2知，任一模p的二次剩余恰有兩個(gè)不同的平方根，即：任取二次剩余 ，只有y和p-y這兩個(gè)不同的平方根 在1,p-1中恰有(p-1)/2對(duì)不同的平方根，每對(duì)平方根對(duì)應(yīng)的模p的余數(shù)必定在1,p-1中，即此區(qū)間上恰有(p-1)/2個(gè)模p的二次剩余。定理4：對(duì) ，p是任一奇素?cái)?shù)，有且x是模p的二次剩余當(dāng)且僅當(dāng)pf：略（可用費(fèi)馬定理）88884.2 模p平方根如何判定x是否為模p的二次剩余？

39、只要利用定理4和計(jì)算方冪模 即可。已知p是奇素?cái)?shù)，x是模p的二次剩余，如何計(jì)算x模p的兩個(gè)平方根？當(dāng) 時(shí)，兩平方根易求，分別是當(dāng) 時(shí)，沒有有效的確定性算法，只能借助于Las Vegas算法。89894.2 模p平方根Las Vegas算法用 表示x的兩個(gè)平方根中較小的一個(gè)。Def：模p乘法（類似于復(fù)數(shù)乘法） a，b，c，d0,p-190904.2 模p平方根例：設(shè)由定理4可知，7是模53的二次剩余，求7模53的平方根。當(dāng)省略模53符號(hào)時(shí)， 計(jì)算過(guò)程如下：91914.2 模p平方根注： 上例中， ， 由定理4知， 是模53的非二次剩余。 同樣可知 亦是模53的非二次剩余。92924.2 模p平方

40、根若計(jì)算知當(dāng) 時(shí)，已知 和 中有一個(gè)是模p的二次剩余，而另一個(gè)不是二次剩余，會(huì)怎樣呢？例如，假定兩等式相加得： 兩式相減得： 93934.2 模p平方根例：通過(guò)計(jì)算可知為了獲得7的一個(gè)平方根，需要找唯一的一個(gè)整數(shù)y使得 ， 。 這可使用一個(gè)Euclid算法解決算法設(shè)x是模p的二次剩余，p是素?cái)?shù)且94944.2 模p平方根rootLV(x, p, y, success)/計(jì)算ya uniform(1.p-1);/我們并不知道a應(yīng)取多少if then /可能性很小 success true； y a；else 計(jì)算c，d使得 if d=0 then success false；/無(wú)法求出 else

41、/c=0 success true； 計(jì)算y使 算法成功的概率0.5,接近0.5。故平均調(diào)用兩次即可求得x的平方根95954.3 整數(shù)的因數(shù)分解 設(shè)n是一個(gè)大于1的整數(shù)，因數(shù)分解問題是找到n的一個(gè)唯一分解： 這里 是正整數(shù)，且 均為素?cái)?shù)。 若n是合數(shù)，則至少有1個(gè)非平凡的因數(shù)(不是1和n本身).設(shè)n是一個(gè)合數(shù)，n的因數(shù)分解問題，即找n的非平凡因數(shù)，它由兩部分構(gòu)成：prime(n) 判定n是否為素?cái)?shù)，可由Monte Carlo算法確定。split(n)當(dāng)n為合數(shù)時(shí)，找n的一個(gè)非平凡的因數(shù)。96964.3 整數(shù)的因數(shù)分解樸素的split算法split(n) /n是素?cái)?shù),返回1，否則返回找到的n的最

42、小非平凡因數(shù)for i2 to do if (n mod i)=0 then return i; /i2 return 1; /返回平凡因數(shù)97974.3 整數(shù)的因數(shù)分解性能分析： 最壞情況。當(dāng)n是一個(gè)中等規(guī)模的整數(shù)（如大約50位十進(jìn)制整數(shù)）時(shí)，最壞情況的計(jì)算時(shí)間亦不可接受。n的位數(shù) ，當(dāng)m=50時(shí)，上述算法的時(shí)間約為無(wú)論是確定性的還是概率的，沒有算法能夠在多項(xiàng)式時(shí)間O(p(m)內(nèi)分解n。Dixon的概率算法分解n的時(shí)間為Note：無(wú)論k和b是何正常數(shù)，均有：98984.3 整數(shù)的因數(shù)分解合數(shù)的二次剩余（模素?cái)?shù)到模合數(shù)的推廣）設(shè)n是任一正整數(shù)，整數(shù)x1,n-1。若x和n互素，且存在一整數(shù)y1,

43、n-1 使xy2(modn)，則稱x為模n的二次剩余，稱y為x模n的平方根。一個(gè)模p的二次剩余，當(dāng)p為素?cái)?shù)時(shí)，恰有兩個(gè)不同的平方根，但p為合數(shù)，且至少有兩個(gè)奇素?cái)?shù)因子時(shí)，不再為真。例： ,注意29應(yīng)與35互素，才有可能是模35的二次剩余。定理：若n=pq，p、q是兩個(gè)互不相同的素?cái)?shù)，則每一個(gè)模n的二次剩余恰有4個(gè)平方根。99994.3 整數(shù)的因數(shù)分解 上節(jié)的測(cè)試x是否是模p的二次剩余及找x的平方根的方法是一個(gè)有效的算法（指rootLV），當(dāng)n是一個(gè)合數(shù)，且n的因子分解給定時(shí)，同樣存在有效的算法。但n的因數(shù)分解未給定時(shí)，目前還沒有有效算法測(cè)試x是否為二次剩余及找x的平方根。Dixon因數(shù)分解算法

44、 基本思想，找兩個(gè)與n互素的整數(shù)a和b，使 但 蘊(yùn)含著 即 假定 ，則n的某一非平凡因子x滿足： . n和a+b的最大公因子是n的一個(gè)非平凡因子。 例如： 1001004.3 整數(shù)的因數(shù)分解Dixon (n, x, success)/找合數(shù)n的某一非平凡因子x if n是偶數(shù) then x2；success true； else for i 2 to do if 是整數(shù) then x ;success true;return; /n是合數(shù)且為奇數(shù)，現(xiàn)在知道它至少有2個(gè)不同的奇素?cái)?shù)因子 a，b 兩個(gè)使得 的整數(shù)if then success false；elsex gcd (a+b,n); su

45、ccess true; 1011014.3 整數(shù)的因數(shù)分解如何確定a和b使 ，來(lái)對(duì)n因數(shù)分解。Def. k-平滑： 若一個(gè)整數(shù)x的所有素因子均在前k個(gè)素?cái)?shù)之中，則x稱為k-平滑的。例如： 是3-平滑的 35=57不是3-平滑的， 7是第四個(gè)素?cái)?shù)它是4-平滑的，也是5-平滑的當(dāng)k較小時(shí)，k-平滑的整數(shù)可用樸素的split算法進(jìn)行有效的因數(shù)分解。Dixon算法可以分為3步確定a和b。1021024.3 整數(shù)的因數(shù)分解Step1：在1n-1之間隨機(jī)選擇xi)若x碰巧不與n互素，則已找到n的一個(gè)非平凡因子(即為x)ii)否則設(shè) ，若y是k-平滑，則將x和y的因數(shù)分解保存在表里。此過(guò)程重復(fù)直至選擇了k+

46、1個(gè)互不相同的整數(shù)，并且這些整數(shù)的平方模n的因數(shù)已分解(當(dāng)k較小時(shí)，用split(n)分解）例1：設(shè)n=2537，k=7.前7個(gè)整數(shù)為：2，3，5，7，11，13，17若隨機(jī)選取x=1769，1240不是7-平滑的1031034.3 整數(shù)的因數(shù)分解下述8個(gè)x的平方模n是7-平滑的：1041044.3 整數(shù)的因數(shù)分解Step2：在k+1個(gè)等式之中找一個(gè)非空子集，使相應(yīng)的因數(shù)分解的積中前k個(gè)素?cái)?shù)的指數(shù)均為偶數(shù)(包含0)例2：在上例的8個(gè)等式中，有7個(gè)積符合要求：可以證明，在k+1個(gè)等式中，至少存在這樣一個(gè)解，如何找到一個(gè)解？構(gòu)造一個(gè)0-1矩陣A：(k+1) k矩陣的行對(duì)應(yīng)k+1個(gè)yi，列對(duì)應(yīng)前k個(gè)

47、素?cái)?shù)。1051054.3 整數(shù)的因數(shù)分解矩陣的行數(shù)大于列數(shù)。在模2意義下，矩陣的行之間不可能均是相互獨(dú)立的。例如在例2中，第一個(gè)解就是線性相關(guān)的： 使用Gauss-Jordan消去法可找到線性相關(guān)的行。Step3：在step2中找到線性相關(guān)的行后：1）令a為相應(yīng)xi的乘積2）令b是yi的乘積開平方若 ，則只需求a+b和n的最大公因子即可獲得n的非平凡因子。1061064.3 整數(shù)的因數(shù)分解例3：對(duì)于例2中的第1個(gè)解有： a+b=3139和n=2537的最大公因子是43，它是n的一個(gè)非平凡因子，對(duì)于例2中的第2個(gè)解有： 此解不能求因子。實(shí)際上 的概率至少為1/21071074.3 整數(shù)的因數(shù)分解

48、5.時(shí)間分析如何選擇k.1)k越大， 是k-平滑的可能性越大(x是隨機(jī)選取的)2)k越小，測(cè)試k-平滑及因數(shù)分解yi的時(shí)間越小，確定yi 是否線性相關(guān)的時(shí)間也越少，但 不是k-平滑的概率也就較大。設(shè)通常取 時(shí)較好，此時(shí)Dixon算法分裂n的期望時(shí)間為 ，成功的概率至少為1/2.108108Ch.5 Monte Carlo算法存在某些問題，無(wú)論是確定的還是概率的，均找不到有效的算法獲得正確的答案。Monte Carlo算法偶然會(huì)犯錯(cuò)，但它無(wú)論對(duì)何實(shí)例均能以高概率找到正確解。當(dāng)算法出錯(cuò)時(shí)，沒有警告信息?；靖拍頓ef1：設(shè)p是一個(gè)實(shí)數(shù)，且1/2p1，若一個(gè)MC算法以不小于p的概率返回一個(gè)正確的解，

49、則該MC算法稱為p-正確，算法的優(yōu)勢(shì)（advantage）是 p-1/2.Def2：若一個(gè)MC算法對(duì)同一實(shí)例決不給出兩個(gè)不同的正確解，則該算法稱是相容的（consistent）或一致的。109109 Ch.5 Monte Carlo算法某些MC算法的參數(shù)不僅包括被解的實(shí)例，還包括錯(cuò)誤概率的上界。因此，這樣算法的時(shí)間被表示為實(shí)例大小及相關(guān)可接受的錯(cuò)誤概率的函數(shù)。基本思想：為了增加一個(gè)一致的、p-正確算法成功的概率，只需多次調(diào)用同一算法，然后選擇出現(xiàn)次數(shù)最多的解。例：設(shè)MC(x)是一個(gè)一致、75%-correct的MC算法，考慮下述算法：MC3(x) tMC(x); uMC(x); vMC(x);

50、 if t=u or t=v then return t; else return v;110110Ch.5 Monte Carlo算法該算法是一致的和27/32-correct的(約84%)pf:相容性（一致性）易證。 t、u、v正確的概率為75%=3/4=p 錯(cuò)誤的概率為q=1/4.1)若t、u、v均正確， MC是一致的 t=u=v，則MC3返回的t正確，此概率為：(3/4)32)若t、u、v恰有兩個(gè)正確則MC3返回 此概率為： 3)若t、u、v恰有一個(gè)正確，則只有v正確時(shí)，MC3返回正確答案，此概率為：111111Ch.5 Monte Carlo算法嚴(yán)格的說(shuō)，當(dāng)v正確，只有兩個(gè)錯(cuò)誤的解t

51、和u不相等時(shí)，才有可能成功，因此MC3成功的概率為： 多運(yùn)行2次（共3次）使成功率Theorem：設(shè)2個(gè)正實(shí)數(shù)之和+0是多小，均可通過(guò)反復(fù)調(diào)用來(lái)擴(kuò)大其優(yōu)勢(shì)，使得最終的算法具有可接受的錯(cuò)誤概率，可達(dá)到任意?。ㄟx定的）。pf：設(shè) 是調(diào)用MC(x)的次數(shù)， 當(dāng)重復(fù)調(diào)用MC(x)算法n次時(shí)，若正確解至少出現(xiàn)m次，則新算法返回頻度最高的解必為正確解；若正確解出現(xiàn)的次數(shù)不超過(guò)n/2時(shí)，不能保證新算法找到了正確解。因此，出錯(cuò)概率至多為：113113Ch.5 Monte Carlo算法由此可知，重復(fù)MC(x) n次成功的概率至少為1-。114114Ch.5 Monte Carlo算法例：假定有一個(gè)一致的5%贏

52、面的MC算法，若希望獲得一個(gè)錯(cuò)誤概率小于5%的算法，則相當(dāng)于將55%-correct的算法改造成95%-correct的算法。上述定理告訴我們：大約要調(diào)用MC算法600次才能達(dá)到相應(yīng)的精度（在同一實(shí)例上， ）上述證明太過(guò)粗略，更精確的證明表示：如果重復(fù)調(diào)用一個(gè)一致的，(1/2+)-correct的MC算法2m-1次，則可得到一個(gè)(1-)-correct的最終算法，其中：115115Ch.5 Monte Carlo算法2.有偏算法重復(fù)一個(gè)算法幾百次來(lái)獲得較小的出錯(cuò)概率是沒有吸引力的，幸運(yùn)地，大多數(shù)MC算法實(shí)際上隨著重復(fù)次數(shù)的增加，正確概率增長(zhǎng)會(huì)更快。Def：(偏真算法)為簡(jiǎn)單起見，設(shè)MC(x)是

53、解某個(gè)判定問題，對(duì)任何x，若當(dāng)MC(x)返回true時(shí)解總是正確的，僅當(dāng)它返回false時(shí)才有可能產(chǎn)生錯(cuò)誤的解，則稱此算法為偏真的(true-biased)。顯然，在偏真的MC算法里，沒有必要返回頻數(shù)最高的解，因?yàn)橐淮蝨rue超過(guò)任何次數(shù)的false.對(duì)于偏真的MC算法，重復(fù)調(diào)用4次，就可將55%-正確的算法改進(jìn)到95%正確。6次重復(fù)就可得到99%正確的算法，且對(duì)p1/2的要求可以放寬到p0即可。116116Ch.5 Monte Carlo算法Def：(偏y0算法)更一般的情況不再限定是判定問題，一個(gè)MC是偏y0的(y0是某個(gè)特定解)，如果存在問題實(shí)例的子集X使得：若被解實(shí)例 ，則算法MC(x

54、)返回的解總是正確的(無(wú)論返回y0還是非y0)若 ，正確解是y0 ，但MC并非對(duì)所有這樣的實(shí)例x都返回正確解。雖然y0是必須知道的，但無(wú)需測(cè)試x是否是X的成員，下面解釋若算法返回y0時(shí)，它總是正確的。 即算法返回y0時(shí)總是正確的，返回非y0時(shí)以p為概率正確。117117Ch.5 Monte Carlo算法設(shè)MC是一個(gè)一致的、p-correct和偏y0的蒙特卡洛算法，x是一個(gè)實(shí)例，y是MC(x)返回的解，可分為如下2種情形討論：case1：若 ，則算法MC總是返回正確解，因此y0確實(shí)是正確的。若 ，算法返回的正確解必定是y0這兩種情況均可得到結(jié)論： y0是一個(gè)正確解。case2：若 ，則y是正確

55、解。若 ，因?yàn)檎_解是y0 ，故y是錯(cuò)誤解，此出錯(cuò)概率不超過(guò)1-p。118118Ch.5 Monte Carlo算法有偏算法重復(fù)調(diào)用MC：優(yōu)先返回y0 若k次調(diào)用MC(x)所返回解依次是 ，則： (1) 若存在i使 ，則前面的討論已知，它是一個(gè)正確解(yi是正確解).(2) 若存在 使 ，由于MC是一致的，故必有 。因此正確解仍是y0 。(3) 若對(duì)所有的i均有 ，但 ，則y0仍有可能是正確解。實(shí)際上，若 ，則y0是正確解，此時(shí)y是錯(cuò)誤的，其錯(cuò)誤概率不超過(guò)(1-p)k。由上面的討論可知，重復(fù)調(diào)用一個(gè)一致的，p-正確的，偏y0的MC算法k次，可得到一個(gè)(1-(1-p)k)-正確的算法(對(duì)偏真算法

56、亦適合). 例：p=0.55，k=4，即可將算法正確率提高到95%1191195.1 主元素問題Def：設(shè)T1.n是n個(gè)元素的數(shù)組，若T中等于x的元素個(gè)數(shù)大于n/2(即 )，則稱x是數(shù)組T的主元素。 (Note：若存在，則只可能有1個(gè)主元素)判T是否有主元素maj(T) /測(cè)試隨機(jī)元素 是否為T的主元素 iuniform(1.n); xT i ; k0; for j1 to n do if T j =x then kk+1; return (kn/2);1201205.1 主元素問題若算法返回true，則T含有主元素，所選擇的元素即為主元素，算法一定正確。若算法返回false，則T仍有可能含有

57、主元素，只是所選元素x不是T的主元素而已。若T確實(shí)包含一個(gè)主元素，則隨機(jī)選擇到一個(gè)非主元的概率小于1/2，這是因?yàn)橹髟卣糡的一半以上。算法是一個(gè)偏真的1/2正確的算法：若maj返回true，則T必有主元素，解一定正確。因?yàn)殡S機(jī)選中主元素的概率大于1/2，故該算法是1/2-correct.若maj返回false，則T可能沒有主元素。當(dāng)然，若T沒有主元素，則必返回false。1211215.1 主元素問題實(shí)際使用時(shí)，50%的錯(cuò)誤概率是不可容忍的。而對(duì)有偏算法，可以通過(guò)重復(fù)調(diào)用技術(shù)來(lái)使錯(cuò)誤概率降低到任何值。maj2(T) if maj (T) then return true; /1次成功 els

58、e /1次失敗后調(diào)用第2次 return maj(T); /調(diào)用2次 1221225.1 主元素問題分析： 1) 若T無(wú)主元素，則maj每次均返回false，maj2亦肯定返回false。此時(shí)算法返回值正確（成功）。 2) 若T有主元素，則：第一次調(diào)用maj返回真的概率是p1/2，此時(shí)maj2亦返回真。第一次調(diào)用maj返回fasle的概率為1-p，第2次調(diào)用maj仍以概率p返回true，maj2亦返回真，其概率為:(1-p)p.此時(shí)算法返回值正確（成功）。總結(jié)：當(dāng)T有主元時(shí)，maj返回真的概率是： p+(1-p)p =1-(1-p)23/4.即：maj2是一個(gè)偏真的3/4正確的MC算法。123

59、1235.1 主元素問題3.算法改進(jìn)錯(cuò)誤的概率能夠迅速減小，主要是因?yàn)橹貜?fù)調(diào)用maj的結(jié)果是相互獨(dú)立的，即：對(duì)同一實(shí)例T，某次maj返回fasle，并不會(huì)影響繼續(xù)調(diào)用返回true的概率。因此，當(dāng)T含有主元素時(shí)，k次重復(fù)調(diào)用maj均返回false的概率小于2-k。另一方面，在k次調(diào)用中，只要有一次maj返回真，即可判定T有主元素。1241245.1 主元素問題當(dāng)需要控制算法出錯(cuò)概率小于0時(shí)，相應(yīng)算法調(diào)用maj的次數(shù)為：majMC (T, ) k for i 1 to k do if maj (T) then return true; /成功 return false; /可能失敗該算法的時(shí)間為O

60、(nlg(1/)。注意，這里只是用此問題來(lái)說(shuō)明MC算法，實(shí)際上對(duì)于判定主元素問題存在O(n)的確定性算法。1251255.2 素?cái)?shù)測(cè)定(數(shù)的素性測(cè)定)判定一個(gè)給定的整數(shù)是否為素?cái)?shù)，到目前為止尚未找到有效的確定性算法或Las Vegas算法。簡(jiǎn)單的概率算法。prime(n) d uniform(2. );return 若返回false，則算法幸運(yùn)地找到了n的一個(gè)非平凡因子，n為合數(shù)。若返回true，則未必是素?cái)?shù)。實(shí)際上，若n是合數(shù)，prime 亦以高概率返回true。1261265.2 素?cái)?shù)測(cè)定(數(shù)的素性測(cè)定)例如：prime在251內(nèi)隨機(jī)選一整數(shù)d 成功：d=43，算法返回false(概率為2