算法分析與設(shè)計里的概率算法-概率算法ppt課件

1、1算法設(shè)計與分析算法設(shè)計與分析黃劉生黃劉生中國科學(xué)技術(shù)大學(xué)中國科學(xué)技術(shù)大學(xué)計算機(jī)系計算機(jī)系 國家高性能計算國家高性能計算中心合肥中心合肥2019.8.192Ch.1 概率算法概率算法1. 故事：想象本人是神化故事的主人公，他有一張不易懂的地圖，上面描畫了一處寶藏的藏寶地點(diǎn)。經(jīng)分析他能確定最有能夠的兩個地點(diǎn)是藏寶地點(diǎn)，但二者相距甚遠(yuǎn)。假設(shè)他假設(shè)已到達(dá)其中一處，就立刻知道該處能否為藏寶地點(diǎn)。他到達(dá)兩處之一地點(diǎn)及從其中一處到另一處的間隔是5天的行程。進(jìn)一步假設(shè)有一條惡龍，每晚光臨寶藏并從中拿走一部分財寶。假設(shè)他取寶藏的方案有兩種：1.1 引言引言3 方案1. 花4天的時間計算出準(zhǔn)確的藏寶地點(diǎn)，然后出

2、發(fā)尋寶，一旦出發(fā)不能重新計算 方案2. 有一個小精靈通知他地圖的，但他必需付給他報酬，相當(dāng)于龍3晚上拿走的財寶 Prob 1.1.1 假設(shè)忽略能夠的冒險和出發(fā)尋寶的代價，他能否接受小精靈的協(xié)助？ 顯然，應(yīng)該接受小精靈的協(xié)助，由于他只需給出3晚上被盜竊的財寶量，否那么他將失去4晚被盜財寶量。 但是，假設(shè)冒險，他能夠做得更好！1.1 引言引言4 設(shè)x是他決議之前當(dāng)日的寶藏價值，設(shè)y是惡龍每晚盜走的寶藏價值，并設(shè)x9y 方案1：4天計算確定地址，行程5天，他得到的寶藏價值為：x-9y 方案2：3y付給精靈，行程5天失去5y，他得到的寶藏價值為：x-8y 方案3：投硬幣決議先到一處，失敗后到另一處(冒

3、險方案) 一次勝利所得：x-5y，時機(jī)1/2 二次勝利所得：x-10y，時機(jī)1/21.1 引言引言期望贏期望贏利：利：x-7.5y52. 意義 該故事通知我們：當(dāng)一個算法面臨某種選擇時，有時隨機(jī)選擇比耗時做最優(yōu)選擇更好，尤其是當(dāng)最優(yōu)選擇所花的時間大于隨機(jī)選擇的平均時間的時侯 顯然，概率算法只能是期望的時間更有效，但它有能夠遭遭到最壞的能夠性。63. 期望時間和平均時間的區(qū)別確定算法的平均執(zhí)行時間 輸入規(guī)模一定的一切輸入實(shí)例是等概率出現(xiàn)時，算法的平均執(zhí)行時間。概率算法的期望執(zhí)行時間 反復(fù)解同一個輸入實(shí)例所花的平均執(zhí)行時間。 因此，對概率算法可以討論如下兩種期望時間平均的期望時間：一切輸入實(shí)例上平

4、均的期望執(zhí)行時間最壞的期望時間：最壞的輸入實(shí)例上的期望執(zhí)行時間74. 例子快速排序中的隨機(jī)劃分要求學(xué)生寫一算法，由教師給出輸入實(shí)例，按運(yùn)轉(zhuǎn)時間打分，一切學(xué)生均不敢用簡單的劃分，運(yùn)轉(zhuǎn)時間在1500-2600ms，三個學(xué)生用概率的方法劃分，運(yùn)轉(zhuǎn)時間平均為300ms。8皇后問題系統(tǒng)的方法放置皇后(回溯法)較適宜，找出一切92個解 O(2n)，假設(shè)只找92個其中的任何一個解可在線性時間內(nèi)完成O(n)。 隨機(jī)法：隨機(jī)地放置假設(shè)干皇后可以改良回溯法，特別是當(dāng)n較大時判別大整數(shù)能否為素數(shù)確定算法無法在可行的時間內(nèi)判別一個數(shù)百位十進(jìn)制數(shù)能否素數(shù)，否那么密碼就不平安。 概率算法將有所作為：假設(shè)能接受一個恣意小的

5、錯誤的概率85. 概率算法的特點(diǎn) (1) 不可再現(xiàn)性 在同一個輸入實(shí)例上，每次執(zhí)行結(jié)果不盡一樣，例如N-皇后問題概率算法運(yùn)轉(zhuǎn)不同次將會找到不同的正確解找一給定合數(shù)的非平凡因子每次運(yùn)轉(zhuǎn)的結(jié)果不盡一樣，但確定算法每次運(yùn)轉(zhuǎn)結(jié)果必定一樣 (2) 分析困難 要求有概率論，統(tǒng)計學(xué)和數(shù)論的知識96. 本章商定 隨機(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 10例1：設(shè)p是一個素數(shù)，a是一個整數(shù)滿足1a0 do if (j is

6、odd) s sa mod p;a 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ī)取一元素12n 偽隨機(jī)數(shù)發(fā)生器n在適用中不能夠有真正的隨機(jī)數(shù)發(fā)生器，多數(shù)情況下是用偽隨機(jī)數(shù)發(fā)生器替代。n大多數(shù)偽隨機(jī)數(shù)發(fā)生器是基于一對函數(shù)：nS: X X, 這里X足夠大，它是種子的值域nR: X Y, Y是偽隨機(jī)數(shù)函數(shù)的值域n運(yùn)用S獲得種子序列：x0=g, xi=S(xi-1), i0n然后運(yùn)用R獲得偽隨機(jī)序列：yi=R(xi), i 0n該序

7、列必然是周期性的，但只需S和R選的適宜，該周期長度會非常長。nTC中可用rand()和srand(time), 用GNU C更好13n 根本特征n隨機(jī)決策n在同一實(shí)例上執(zhí)行兩次其結(jié)果能夠不同n在同一實(shí)例上執(zhí)行兩次的時間亦能夠不太一樣n 分類nNumerical, Monte Carlo, Las Vegas, Sherwood.n很多人將一切概率算法(尤其是數(shù)字的概率算法)稱為Monte Carlo算法1.2 概率算法的分類概率算法的分類14v 數(shù)字算法v隨機(jī)性被最早用于求數(shù)字問題的近似解v例如，求一個系統(tǒng)中隊列的平均長度的問題，確定算法很難得到答案v 概率算法獲得的答案普通是近似的，但通常算

8、法執(zhí)行的時間越長，精度就越高，誤差就越小v 運(yùn)用的理由v 現(xiàn)實(shí)世界中的問題在原理上能夠就不存在準(zhǔn)確解v例如，實(shí)驗(yàn)數(shù)據(jù)本身就是近似的，一個無理數(shù)在計算機(jī)中只能近似地表示v 準(zhǔn)確解存在但無法在可行的時間內(nèi)求得v有時答案是以置信區(qū)間的方式給出的1.2 概率算法的分類概率算法的分類15v Monte Carlo算法 (MC算法)v蒙特卡洛算法1945年由J. Von Neumann進(jìn)展核武模擬提出的。它是以概率和統(tǒng)計的實(shí)際與方法為根底的一種數(shù)值計算方法，它是雙重近似：一是用概率模型模擬近似的數(shù)值計算，二是用偽隨機(jī)數(shù)模擬真正的隨機(jī)變量的樣本。v這里我們指的MC算法是： 假設(shè)問題只需1個正確的解，而無近似

9、解的能夠時運(yùn)用MC算法v例如，斷定問題只需真或假兩種能夠性，沒有近似解v 因式分解，我們不能說某數(shù)幾乎是一個因子v 特點(diǎn)：MC算法總是給出一個答案，但該答案未必正確，勝利(即答案是正確的)的概率正比于算法執(zhí)行的時間v 缺陷：普通不能有效地確定算法的答案能否正確1.2 概率算法的分類概率算法的分類16v Las Vegas算法 (LV算法)vLV算法絕不前往錯誤的答案。v 特點(diǎn)：獲得的答案必定正確，但有時它仍根本就找不到答案。v 和MC算法一樣，勝利的概率亦隨算法執(zhí)行時間添加而添加。無論輸入何種實(shí)例，只需算法在該實(shí)例上運(yùn)轉(zhuǎn)足夠的次數(shù)，那么算法失敗的概率就恣意小。v Sherwood算法vSher

10、wood算法總是給出正確的答案。v當(dāng)某些確定算法處理一個特殊問題平均的時間比最壞時間快得多時，我們可以運(yùn)用Sherwood算法來減少，甚至是消除好的和壞的實(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è)可知落入圓中的飛鏢和正方形內(nèi)的飛鏢平均比為：由此知： 1.3 數(shù)字概率算法數(shù)字概率算法2244krn

11、r4 /4nk n k18n求近似值的算法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)(x,y)nif (x2 + y2 1) then k+; /圓內(nèi)nnreturn 4k/n;nn實(shí)驗(yàn)結(jié)果： =3.141592654nn = 1000萬: 3.140740, 3.142568 (2位準(zhǔn)確)nn = 1億: 3.141691, 3.143 (3位準(zhǔn)確)nn = 10億: 3.141527, 3.141507 (4位準(zhǔn)確)1.3.1 值計算值計算

12、19n 求近似值的算法nEx.1 假設(shè)將y uniform(0, 1) 改為 y x, 那么上述的算法估計的值是什么？n1.3.1 值計算值計算20Monte 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ù)字積分?jǐn)?shù)字積分 (計算定積分的值計算定積分的值)10( )Sf x dx/1kSSk nn/Sk n 21n概率算法1nHitorMiss (f, n) nk 0;nfor

13、i 1 to n do nx uniform(0, 1);ny uniform(0, 1);nif y f(x) then k+;nnreturn k/n;nnNote: 是S/4的面積， =S, n1.3.2 數(shù)字積分?jǐn)?shù)字積分 (計算定積分的值計算定積分的值)1201x dx12041x dx22n 概率算法1nEx2. 在機(jī)器上用 估計值，給出不同的n值及精度。nEx3. 設(shè)a, b, c和d是實(shí)數(shù)，且a b, c d, f:a, b c, d是一個延續(xù)函數(shù)，寫一概率算法計算積分：nn留意，函數(shù)的參數(shù)是a, b, c, d, n和f, 其中f用函數(shù)指針實(shí)現(xiàn)，請選一延續(xù)函數(shù)做實(shí)驗(yàn)，并給出實(shí)驗(yàn)

14、結(jié)果。1.3.2 數(shù)字積分?jǐn)?shù)字積分 (計算定積分的值計算定積分的值)12041x dx( )baf x dx23n概率算法1n*Ex4. 設(shè),是(0,1)之間的常數(shù)，證明：n假設(shè)I是 的正確值，h是由HitorHiss算法前往的值，那么當(dāng)n I(1-I)/2時有：nProb|h-I| Tj;1.4.2 隨機(jī)的預(yù)處置隨機(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，最多計算0 x p-1 或 1xp，實(shí)踐上離散對數(shù)

15、是循環(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 x1.4.2 隨機(jī)的預(yù)處置隨機(jī)的預(yù)處置2,7xlog3x32 mod7例無解，不存在使45問題：最壞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秒/年)假設(shè)p是數(shù)百位十進(jìn)制？隨機(jī)選擇都能夠無法在可行的時間內(nèi)求解。假設(shè)有一個平均時間性能很好，但最壞情

16、況差確實(shí)定算法求logp,ga，怎樣用Sherwood算法求解該問題？設(shè)p=19, g=2當(dāng)a=14, 6時，log2,1914 = 7, log2,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,pa1.4.2 隨機(jī)的預(yù)處置隨機(jī)的預(yù)處置46定理(見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); /

17、求冪模b=gr mod p c ba mod p; / y logg,pc; / 運(yùn)用確定性算法求logp,gc, y=r+x return (y-r) mod (p-1); / 求xEx. 分析dlogRH的任務(wù)原理，指出該算法相應(yīng)的u和v1.4.2 隨機(jī)的預(yù)處置隨機(jī)的預(yù)處置,log(mod)(loglog)mod(1)log(mod)for 02g pg pg prg pstpstpgprrp(mod)(mod)modmo?drxr xgp gppgpc47隨機(jī)預(yù)處置提供了一種加密計算的能夠性假定他想計算某個實(shí)例x，經(jīng)過f(x)計算，但他缺乏計算才干或是缺乏有效算法，而他人有相應(yīng)的計算才干

18、，情愿為他計算(能夠會收費(fèi))，假設(shè)他情愿他人幫他計算，但他不情愿泄露他的輸入實(shí)例x，他將如何做？可將隨機(jī)預(yù)處置運(yùn)用到f的計算上： 運(yùn)用函數(shù)u將x加密為某一隨機(jī)實(shí)例y 將y提交給f計算出f(y)的值 運(yùn)用函數(shù)v轉(zhuǎn)換為f(x)上述過程，他人除了知道他的實(shí)例大小外，不知道x的任何信息，由于u(x,r)的概率分布(只需r是隨機(jī)均勻選擇的)是獨(dú)立于x的。1.4.2 隨機(jī)的預(yù)處置隨機(jī)的預(yù)處置48設(shè)兩個數(shù)組val1.n和ptr1.n及head構(gòu)成一個有序的靜態(tài)鏈表：valhead valptrhead valptrptrhead valptrn-1head例：1.4.3 搜索有序表搜索有序表if val i

19、:ptri0 if val i給出下一個關(guān)鍵字的下標(biāo) 不是最大關(guān)鍵字即 是最大關(guān)鍵字49假設(shè)val1.n本身有序，可用折半查找找某個給定的key，時間為O(lgn)。但因此處置鏈?zhǔn)綐?gòu)造，故最壞時間是(n)。雖然如此，我們可以找到一個確定性算法，平均時間為 。相應(yīng)的Sherwood算法的期望時間是 ，它雖然并不比確定性算法快，但他消除了最壞實(shí)例。假定表中元素互不一樣，且所求的關(guān)鍵字表中存在，那么給定x，我們是求下標(biāo)i，使vali=x,這里1i n。任何實(shí)例可以有兩個參數(shù)描寫： 前n個整數(shù)的陳列 x的rank1.4.3 搜索有序表搜索有序表()On()On50設(shè)Sn是一切n!個陳列的集合，設(shè)A是一

20、個確定性算法 tA(n, k, )表示算法A的執(zhí)行時間，此時間與被查找元素的秩k，以及val的排序相關(guān)。假設(shè)A是一個概率算法，那么tA(n, k, )表示算法的期望值。無論算法是確定的還是概率的，wA(n)和mA(n)表示最壞時間和平均時間，因此有： 1.4.3 搜索有序表搜索有序表1( )max ( , , )|1 1( )( , , )!11,2,.,1/!nAnnAASknwnt n kkn andSmntn kn nknnSn的概率是，在 中每個排列的概率是51n時間為O(n)確實(shí)定算法n設(shè)xvali且x在表中，那么從位置i開場查找x的算法為：nSearch(x, i) /仍可改良nw

21、hile x vali don i ptri;nreturn i;nn在表val1.n中查找x的算法為：nA(x) nreturn Search(x, head);n1.4.3 搜索有序表搜索有序表52n時間為O(n)確實(shí)定算法n分析：n設(shè)rank(x)=k, 那么：n 算法A在n個元素的表中查找x所需的訪問數(shù)組元素的次數(shù)，顯然與無關(guān)n 算法A最壞時的訪問次數(shù)n 算法A平均的訪問次數(shù)n nnn1.4.3 搜索有序表搜索有序表( , )Atn kw ( )Anm ( )An1,1, ,( , ),( ),1,2,.,11( )( , )2( )( )AAnAAnnNkn tn kknNknwnn

22、nNknnmntn knT nO n 若是為最壞情況，此時設(shè)的概率相等，則綜上所述，53n時間為O(n)的概率算法nD(x) ni uniform(1.n);ny vali;ncase n x y: return Search(x, ptri); / case2n otherwise: return i; / x = ynnn1.4.3 搜索有序表搜索有序表54n時間為O(n)的概率算法n性能分析：n 設(shè)rank(x)=k, rank(vali)=j (D訪問數(shù)組次數(shù))n假設(shè) k j, 那么 ，屬于case2，從第j小元素搜索n假設(shè) k = j, 那么 ，屬于case3n nnnn1.4.3

23、搜索有序表搜索有序表( , )Dtn kk( , )-Dtn kkj( , )0Dtn k DDnN,w (n)?j1,knSearchn-1w (n)n1 當(dāng)時，執(zhí)行次數(shù)為， 121111121,( )?11,2,.,1,2,.,11( )( , )()1(1)(1)()11()22333DjnnnnDDjkjkkjnjnN mnjnknnmntn kkkjn nnj jnjnjnnnn 及的概率均為顯然平均時間性能優(yōu)于確定算法55n平均時間為 確實(shí)定算法nB(x) /設(shè)x在val1.n中ni head;nmax vali; / max初值是表val中最小值nfor j i to do /

24、在前 個數(shù)中找不大于x n / 的最大整數(shù)y相應(yīng)下標(biāo)in y valj;n if max y x then ni j;n max y;n n / endfornreturn Search(x, i); / 從y向后搜索nnfor循環(huán)的目的：找不超越x的最大整數(shù)y，使搜索從y開場，假設(shè)將val1.n中的n個整數(shù)看作是均勻隨機(jī)分布的，那么在val1.l中求y值就相當(dāng)于在n個整數(shù)中，隨機(jī)地取l個整數(shù)，求這l個整數(shù)中不大于x的最大整數(shù)y。1.4.3 搜索有序表搜索有序表()Onnn56n平均時間為 確實(shí)定算法n算法分析：n可用一個與l和n相關(guān)的隨機(jī)變量來分析，更簡單的分析如下：n設(shè)n個整數(shù)的陳列滿足：

25、na1 a2 0，更好的情況是Obstinate(x) repeatLV(x, y, success);until success;return y; 設(shè)t(x)是算法obstinate找到一個正確解的期望時間，那么假設(shè)要最小化t(x)， 那么需在p(x), s(x)和e(x)之間進(jìn)展某種折衷，例如，假設(shè)要較少失敗的時間，那么可降低勝利的概率p(x)。1.5 Las Vegas 算法算法0, ( )p x常數(shù)( )( ) ( )(1( )( ( )( )LV1( )( )( )( )( )t xp x s xp xe xt xLVp xt xs xe xp x成功的概率失敗的概率60n傳統(tǒng)的回

26、溯法n置當(dāng)前行為第1行，當(dāng)前列為第1列，即ij1;nwhile i 8 do / 當(dāng)前行號 8n檢查當(dāng)前行：從當(dāng)前列j起向后逐列試探，尋覓平安列號；nif 找到平安列號 then n 放置皇后，將列號記入棧中，并將下一行置為當(dāng)前行，即i+;n j1; /當(dāng)前列置為1n else n 退棧回溯到上一行，即i-；n 移去該行已已放置的皇后，以該皇后所在列的下一列作為當(dāng)前 列；nn1.5.1 8后問題后問題12341234iji+j 135度對角線度對角線：同一條對同一條對角線上的元素的行列號之和角線上的元素的行列號之和相等相等 i-j或或j-i 45度對角線度對角線：同一條同一條對角線上的元素的行

27、列號之對角線上的元素的行列號之差相等差相等 61611.5.1 8后問題后問題2.Las Vegas方法向量try1.8中存放結(jié)果tryi表示第i個皇后放在i，tryi)位置上try1.k稱為k-promising是指：假設(shè)k個皇后的位置(0k 8): (1,try1),(2,try2),(k,tryk)相互不攻擊，那么稱try1.k是k-promising的.方式化：對 ，假設(shè) 有 (式1)那么：行沖突：無須思索，由于第i個皇后放在第i行，故同一行不會有兩皇后,1, i jkijtryi-tryji-j,0,j-i62621.5.1 8后問題后問題 列沖突：假設(shè)對恣意不同的兩行i、j，由于其

28、列數(shù)之差不為0，故恣意兩皇后不能夠在同一列上。 對角線沖突： 和 沖突時有：即 。故任兩皇后不會在對角線上沖突。 45對角線沖突： 和 沖突時有：即tryi-tryj=i-j故任兩皇后不會在45對角線上沖突。 綜上所述，式1成立時try1.k是k-promising。 顯然，假設(shè)k 1，那么向量try1.k是k-promising的，對 8后問題，解是8-promising的。, i try ia itry ijtry j, j try ja try itry jji, i try ia, j try ja itry ijtry j63631.5.1 8后問題后問題算法：QueensLv (s

29、uccess)/貪婪的LV算法，一切皇后都是隨機(jī)放置/假設(shè)Success=true，那么try1.8包含8后問題的一個解。col,diag45,diag；/列及兩對角線集合初值為空k 0；/行號repeat /try1.k是k-promising，思索放第k+1個皇后nb 0；/計數(shù)器，nb值為k+1)th皇后的open位置總數(shù)for i i to 8 do /i是列號 if (i col) and (i-k diag45) and (i+k diag) then /列i對k+1th皇后可用，但不一定馬上將其放在第i列 nb nb+1； if uniform(1.nb)=1 then /或許放

30、在第i列 j i；/留意第一次uniform一定前往1，即j一定有值1 /endif /endfor64641.5.1 8后問題后問題if(nb 0) then /nb=0時，第k+1個皇后尚未放好，一切位置不平安。/在一切nb個open位置上，k+1)th皇后選擇位置j的概率為1/nb tryk+1 j；/放置k+1)th個皇后 col col j ； diag45 diag45 j-k ； diag diag j+k ； kk+1；/try1.k+1是k+1)-promisinguntil nb = 0 or k=8；/當(dāng)前皇后找不到適宜的位置或try是 / 8-promising是終了。

31、success nb0；65651.5.1 8后問題后問題v 分析v 設(shè)p是勝利的概率一次勝利 vs：勝利時搜索的結(jié)點(diǎn)的平均數(shù)。一個皇后放好算是搜索樹上的一個結(jié)點(diǎn)ve：失敗時搜索的結(jié)點(diǎn)的平均數(shù)。v 顯然s=q空向量try算在內(nèi)vp和e實(shí)際上難于計算，但實(shí)驗(yàn)用計算機(jī)可以計算出：vp=0.1293ve=6.971v在反復(fù)上述算法，直至勝利時(相當(dāng)于obstinate的時間，所搜索的平均結(jié)點(diǎn)數(shù)：v大大優(yōu)于回溯法，回溯法約為114個結(jié)點(diǎn)才干求出一個解。v Ex.證明：當(dāng)放置k+1)th皇后時，假設(shè)有多個位置是開放的,那么算法QueensLV選中其中任一位置的概率相等。(1) /55.927.tsp e

32、 p66661.5.1 8后問題后問題v 改良v 上述LV算法過于消極：一旦失敗，從頭再來v 而回溯法又過于樂觀：一旦放置某個皇后，就進(jìn)展系統(tǒng)回退一步的戰(zhàn)略，而這一步往往不一定有效。 v 折中的方法會更好嗎？普通情況下為此。v先用LV方法隨機(jī)地放置前假設(shè)干個結(jié)點(diǎn)，例如k個。v然后運(yùn)用回溯法放置后假設(shè)干個結(jié)點(diǎn)，但不思索重放前k個結(jié)點(diǎn)。v假設(shè)前面的隨機(jī)選擇位置不好，能夠使得后面的位置不勝利，如假設(shè)前兩個皇后的位置是1、3。v隨機(jī)放置的皇后越多，那么后續(xù)回溯階段的平均時間就越少，失敗的概率也就越大。67671.5.1 8后問題后問題折中算法只需將QueensLV的最后兩行改為：until nb =

33、0 or k = stopVegas；if nb0)then backtrace (k, col, diag45, diag,success);else success false；stopVegas控制隨機(jī)放置皇后的個數(shù)。68681.5.1 8后問題后問題改良后算法的實(shí)驗(yàn)室結(jié)果：純回溯時間：40msstepVegas=2 or 3：10ms平均純貪婪LV：23ms平均結(jié)論：一半略少的皇后隨機(jī)放置較好。StepVegaspset011141141139.6339.6320.87522.5339.6728.230.493113.4815.129.0140.261810.318.7935.150.

34、16249.337.2946.9260.13579.056.9853.570.129396.9755.9380.129396.9753.93搜索的平均節(jié)點(diǎn)數(shù)完全回溯完全隨機(jī)69691.5.1 8后問題后問題-問題1：為什么僅隨機(jī)放一個皇后，其效果就會大大優(yōu)于純回溯方法？-問題2：預(yù)先隨機(jī)選幾個皇后放置為好？由于解缺乏規(guī)律性至少在皇后數(shù)不等于4k+2，k為某整數(shù)時，故求出stepVegas的最優(yōu)值較難，但是找到一個較好不一定是最優(yōu)的stepVegas還是可以的。12皇后：StepVegaspset時間01262262125ms50.503933.8847.2380.3937ms120.04651

35、310.2222.11基本與純回溯相同70701.5.1 8后問題后問題在Apple II機(jī)器上，20個皇后：確定性的回溯算法：找到第一個解的時間大于2個小時。概率算法，隨機(jī)地放置前10個皇后：5分半鐘找到36個不同的解。后者找一個接比前者大約快1000倍！Ex. 寫一算法，求n=1220時最優(yōu)的StepVegas值。-Obstinate算法在何時無限循環(huán)？當(dāng)問題不存在解時。對于n皇后，要求n=4，即問題至少有一個解存在時，Obstinate算法才有能夠終了。71711.5.2 模模p平方根平方根n定義1：設(shè)p是一個奇素數(shù)，假設(shè)整數(shù)x1,p-1且存在一個整數(shù)y，使n那么x稱為模p的二次剩余qu

36、adratic residue，假設(shè)y 1,p-1，那么y稱為x模p的平方根。n例：63是55模103的平方根，55是模103的二次剩余。nnn定義2：假設(shè)整數(shù) ，且z不是模p的二次剩余，那么z是模p的非二次剩余。nn2modxyp55mod10355263 mod1033969mod1035525563 (mod103)1,1zp72721.5.2 模模p平方根平方根n定理1：任何一個模p的二次剩余至少有兩個不同的平方根。npf：設(shè)x是模p的二次剩余，y是x模p的平方根。n由于n故n只需證 且 就可證明p-y是不同于y的x模p的另一個平方根。np是奇數(shù)， ，否那么p是偶數(shù)。n另一方面，n22

37、22()2(mod)pyppyyyp2() (mod)xpyppyy11yppyy11pyp1. /y1pyp(1)1. /yp-1pypp73731.5.2 模模p平方根平方根n定理2：任一模p的二次剩余至多有兩個不同的平方根npf：設(shè) a和b是x模p的平方根。nnn即 成立。n假設(shè)k=0，那么a=bn假設(shè)k0，那么abn無妨設(shè)ab. n又 n由Th31.7知n即 n即 ，n 也就是說恣意兩個不同的平方根，均只需b和(p-b)兩種不同方式。220(mod)abp22|()pab| ()pab22abk p222212(mod ) ,abpak pr bk pr1abp|()()pab ab|

38、()pab()abkp()2abp1k abpapb74741.5.2 模模p平方根平方根n定理3：1到p-1之間的整數(shù)恰有一半是模p的二次剩余余數(shù)。npf：由定理1和定理2知，任一模p的二次剩余恰有兩個不同的平方根，即任取二次剩余 ，只需y和p-y這兩個不同的平方根 ，nn在1,p-1中恰有(p-1)/2對不同的平方根，每對平方根對應(yīng)的模p的余數(shù)必定在1,p-1中，即此區(qū)間上恰有(p-1)/2個模p的二次剩余n定理4：對 ，p是任一奇素數(shù)，有n且x是模p的二次剩余當(dāng)且僅當(dāng)npf：略可用費(fèi)馬定理1,1xp1,1xp (1)/21(mod)pxp 1y1pyp22() (mod)ypyp(1)/

39、21(mod)pxp 75751.5.2 模模p平方根平方根n斷定x能否為模p的二次剩余？n只需利用定理4和計算方冪模 即可。n知p是奇素數(shù)，x是模p的二次剩余，如何計算x模p的兩個平方根？n當(dāng) 時，兩平方根易求，分別是n當(dāng) 時，沒有有效確實(shí)定性算法，只能借助與Las Vegas算法。nLas Vegas算法。n用 表示x的兩個平方根中較小的一個。nDef：模p乘法類似于復(fù)數(shù)乘法，a，b，c，d0,p-1(1)/4px(1)/2modpxp3(mod4)p 1(mod4)p x()()mod()mod()mod()mod)mod /See p.863,(31.18)ab x cdxpacbdx

40、adbcxpacbdxpadbcpxp式76761.5.2 1.5.2 模模pp平方根平方根v例：設(shè)vv由定理4可知，7是模53的二次剩余，求7模53的平方根。v當(dāng)省略模53符號是， 計算過程如下：531(mod 4),7.7px求 的平方根2671(mod53) /26=(53-1)/226(17)mod5323(17)(17)(17)82 7(17)(17)(82 7)22 10 717(22 10 7)(22 10 7)18 16 717(18 16 7)(18 16 7)4946 717(17)(4946 7)042 717(042 7)(042 7)520 76121326（）（）（

41、）（）77771.5.2 模模p平方根平方根注：上例中， ， 由定理4知， 是模53的二次非剩余。 同樣可知 亦是摸53的二次非剩余。26(17)mod53(042 7)(042 7)mod5326(17)1(mod53) 1726(1)/2p17(42 42 7mod530 7)mod53(12348mod530 7)mod53(520 7)mod5378781.5.2 模模p平方根平方根n假設(shè)計算知當(dāng) 時，知 和 中有一個是模p的二次剩余，而另一個不是二次剩余，會怎樣呢？n例如，假定nn兩等式相加得：n n 兩式相減的：n 26(17)7(mod53cd）20(mod53)c 71(mod

42、53) /(7)mod534cda即+是二次剩余，定理052c(7)mod53a(7)mod53a71(mod53) /7)mod53cdcd 即(不是二次剩余0c 272(mod53)d71(mod53)d79791.5.2 模模p平方根平方根n例：經(jīng)過計算可知n為了獲得7的一個平方根，需求找獨(dú)一的一個證書y使得 ， 。這可運(yùn)用一個Euclid算法處理nnn算法：n設(shè)x是模p的二次剩余，p是素數(shù)且nn26(27)041 7(mod53）152y411mod53y 41 221(mod53), 故y=22.它是7模53一個平方根21(mod4),(mod )pyxp找2722 (mod53),

43、 另一平方根為53-22=3180801.5.2 模模p平方根平方根rootLV(x, p, y, success)/計算ya uniform(1.p-1);/我們并不知道a應(yīng)取多少if then /能夠性很小 success true； y a；else 計算e，d使得 if d=0 then success false；/無法求出 else/c=0 success true； 計算y使得 /算法勝利的概率0.5,接近0.5。故平均調(diào)用兩次即可求得x的平方根。2(mod)axp(1)/20,1,()(mod );pc dpaxcd xp x1(mod ),11/Euclidd ypypy修改

44、算法可求81811.5.3 整數(shù)的因數(shù)分解整數(shù)的因數(shù)分解設(shè)n是一個大于1的整數(shù)，因數(shù)分解問題是找到n的一個獨(dú)一分解：這里 是正整數(shù)，且 均為素數(shù)。假設(shè)n是合數(shù)，那么至少有一個非平凡的因數(shù)(不是1和n本身).n的因數(shù)分解問題，即為找n的非平凡因數(shù)(設(shè)n是一個合數(shù)),它由兩部分構(gòu)成：prime(n)斷定n能否為素數(shù)，可由Monte Carlo算法確定。split(n)當(dāng)n為分?jǐn)?shù)時，找n的一個非平凡的因數(shù)。1212kmmmknpppim12kppp82821.5.3 整數(shù)的因數(shù)分解整數(shù)的因數(shù)分解n樸素的split算法nsplit(n)n/假設(shè)n是素數(shù),前往1，否那么前往找到的n的最小非平凡因數(shù)nfo

45、r i2 to do n if (n mod i)=0 thenn return i; /i2n return 1; /前往平凡因數(shù)nn83831.5.3 整數(shù)的因數(shù)分解整數(shù)的因數(shù)分解n性能分析：n 最壞情況。n當(dāng)n是一個中等規(guī)模的整數(shù)如大約50位十進(jìn)制整數(shù)時，最壞情況的計算時間亦不可接受。nn的位數(shù)n ，當(dāng)m=50時，上述算法的時間約為n無論是確定性的還是概率的，沒有算法可以在多項式時間O(p(m)內(nèi)分解n。Dixom的概率算法分解n的時間為nNote：無論k和b是何正常數(shù)，均有：( )()T nn 10log(2)mmO(1)10lognm/210mn 251010(log)/()(2)(

46、10)mOmkm bO mOO84841.5.3 整數(shù)的因數(shù)分解整數(shù)的因數(shù)分解n合數(shù)的二次剩余模素數(shù)到模合數(shù)的推行n設(shè)n是任一正整數(shù)，整數(shù) 。假設(shè)x和n互素，且存在一整數(shù) 使 ，那么x稱為是模n的二次剩余，y稱為是模n的平方根。n一個模p的二次剩余，當(dāng)p為素數(shù)時，恰有兩個不同的平方根，但p為合數(shù)，且至少有兩個奇素數(shù)因子時，不再為真。例： ,留意29應(yīng)與35互素，才有能夠是模35的二次剩余。n定理：假設(shè)n=pq，p、q是兩個互不一樣的素數(shù)，那么每一個模n的二次剩余恰有4個平方根。1,1xn1,1yn2(mod )xyn2222813222729(mod35)85851.5.3 整數(shù)的因數(shù)分解整數(shù)

47、的因數(shù)分解 上節(jié)的測試x能否是模p的二次剩余及找x的平方根的方法是一個有效的算法指rootLV，當(dāng)n是一個合數(shù)，且n的因子分解給定時，同樣存在有效的算法。但n的因數(shù)分解未給定時，目前還沒有有效算法測試x能否為二次剩余及找x的平方根。Dixon因數(shù)分解算法。 根本思想，找兩個與n互素的整數(shù)a和b，使 但 蘊(yùn)含著 即 假定 ，那么n的某一非平凡因子x滿足： . n和a+b的最大公因子是n的一個非平凡因子。 例如： 22(mod )abn(mod )abn 22()()0(mod )abab abn|()()nab a b| (),| ()nab nab|(),( / )|()xabn xab8,1

48、3,35.abn2135gcd7,abnxx和的是是35的一個非平凡因子86861.5.3 整數(shù)的因數(shù)分解整數(shù)的因數(shù)分解Dixon (n, x, success)/找合數(shù)n的某一非平凡因子xif n是偶數(shù) then x2；success true；else for i 2 to do if 是整數(shù) thenx ; success true;return; /n是合數(shù)且為奇數(shù)，如今知道它至少有兩個不同的奇素數(shù)因子a，b 兩個使得 的整數(shù)if then success false；elsex gcd (a+b,n); success true;3logn1/in1/in22(mod )abn(mo

49、d )abn87871.5.3 整數(shù)的因數(shù)分解整數(shù)的因數(shù)分解n如何確定a和b使 ，來對n因數(shù)分解。nDef. k-平滑：n 假設(shè)一個整數(shù)x的一切素因子均在前k個素數(shù)之中，那么x稱為k-平滑的。n例如： 是3-平滑的n 35=57不是3-平滑的， 7是第四個素數(shù)n它是4-平滑的，也是5-平滑的n當(dāng)k較小時，k-平滑的整數(shù)可用樸素的split算法進(jìn)展有效的因數(shù)分解。Dixom算法可以分為3步確定a和b。22(mod )abn312023 5 88881.5.3 整數(shù)的因數(shù)分解整數(shù)的因數(shù)分解Step1：在1n-1之間隨機(jī)選擇xi)假設(shè)x碰23不與n互素，那么已找到n的一個非平凡因子(即為x)ii)否

50、那么設(shè) ，假設(shè)y是k-平滑，那么將x和y的因數(shù)分解保管在表里。此過程反復(fù)直至選擇了k+1個互不一樣的整數(shù)，并且這些整數(shù)的平方模n的因數(shù)已分解(當(dāng)k較小時，用split(n)分解例1：設(shè)n=2537，k=7.前7個整數(shù)為：2，3，5，7，11，13，17假設(shè)隨機(jī)選取x=1769，1240不是7-平滑的21769 mod25371240y 2modyxn3124025 31 89891.5.3 整數(shù)的因數(shù)分解整數(shù)的因數(shù)分解下述8個x的平方模n是7-平滑的：211223333442556623774882455,16502 3 511970,22102 5 13 171105,72827 13145

51、8,229535 17216,9902 35 1180,13262 3 13 171844,756237433,2288211 13xyxyxyxyxyxyxyxy 90901.5.3 整數(shù)的因數(shù)分解整數(shù)的因數(shù)分解Step2：在k+1個等式之中找一個非空子集，使相應(yīng)的因數(shù)分解的積中前k個素數(shù)的指數(shù)均為偶數(shù)(包含0)例2：在上例的8個等式中，有7個積符合要求：可以證明，在k+1個等式中，至少存在這樣一個解，如何找到一個解？構(gòu)造一個0-1矩陣A：(k+1) k矩陣的行對應(yīng)k+1個yi，列對應(yīng)前k個素數(shù)。644022212488104222213456723571113172357111317y y

52、 y yy y y y y y（解一）（解二）0 1 iijiyjayj若 的第 個素數(shù)的指數(shù)為偶數(shù)若 的第 個素數(shù)的指數(shù)為奇數(shù)91911.5.3 整數(shù)的因數(shù)分解整數(shù)的因數(shù)分解矩陣的行數(shù)大于列數(shù)。在模2意義下，矩陣的行之間不能夠均是相互獨(dú)立的。例如在例2中，第一個解就是線性相關(guān)的：運(yùn)用Gauss-Jordan消去法可找到線性相關(guān)的行。Step3：在step2中找到線性相關(guān)的行后：1令a為相應(yīng)xi的乘積2令b是yi的乘積開平方假設(shè) ，那么只需求a+b和n的最大公因子即可獲得n的非平凡因子。112010012357111317 (1,1,0,0,1,0,0)(1,0,1,0,0,1,1)(0,1,

53、1,0,0,0,1)(0,0,0,0,1,1,0)(0,0,0,0,0,0,0)(mod2)y (mod )abn92921.5.3 整數(shù)的因數(shù)分解整數(shù)的因數(shù)分解例3：對于例2中的第1個解有： a+b=3和n=2537的最大公因子是43，它是n的一個非平凡因子，對于例2中的第2個解有： 此解不能求因子。實(shí)踐上 的概率至少為1/21 24 83220mod2455 970 1458 433mod25371127235711 13 17mod25372012(mod )ax x x xnban1 3 4 567452mod5642357 11 13 17mod1973(mod )ax x x x

54、x xnbnan (mod )abn93931.5.3 整數(shù)的因數(shù)分解整數(shù)的因數(shù)分解5.時間分析如何選擇k.1)k越大， 是k-平滑的能夠性越大(x是隨機(jī)選取的)2)k越小，測試k-平滑及因數(shù)分解yi的時間越小，確定yi能否線性相關(guān)的時間也越少，但 不是k-平滑的概率也就越小。設(shè)通常的，當(dāng) 時較好，此時Dixom算法分裂n的期望時間為 ，勝利的概率至少為1/2.ln lnln,nnLeb2modxn2modxnkL22 ln lnln()()nnO LO e94941.6 Monte Carlo算法算法存在某些問題，無論是確定的還是概率的，均找不到有效的算法獲得正確的答案。Monte Carl

55、o算法偶爾會犯錯，但它無論對何實(shí)例均能以高概率找到正確解。當(dāng)算法出錯時，沒有警告信息。根本概念Def1：設(shè)p是一個實(shí)數(shù)，且1/2p1.假設(shè)一個MC算法以不小于p的概率前往一個正確的解，那么該MC算法稱為p-正確，算法的優(yōu)勢advantage是p-1/2.Def2：假設(shè)一個MC算法對同一實(shí)例決不給出兩個不同的正確解，那么該算法稱是相容的consistent或一致的。95951.6 Monte Carlo算法算法某些MC算法的參數(shù)不僅包括被解的實(shí)例，還包括錯誤概率的上界。因此，這樣算法的時間被表示為實(shí)例大小及相關(guān)可接受的錯誤概率的函數(shù)。根本思想：為了添加一個一致的，p-正確算法勝利的概率，只需多次

56、調(diào)用同一算法，然后選擇出現(xiàn)次數(shù)最多的解。例：設(shè)MC(x)是一個一致、75%-correct的MC算法，思索下述算法：MC3(x) tMC(x); uMC(x); vMC(x); if t=u or t=v then return t; else return v;96961.6 Monte Carlo算法算法該算法是一致的和27/32-correct的(約84%)pf:相容性一致性易證。t、u、v正確的概率為75%=3/4=p(MC是一致的， t、u、v均正確時t=u=v)卻為概率為q=1/4.1)假設(shè)t、u、v均正確，那么MC3前往的t正確，此時t=u=v.此概率為：(3/4)32)假設(shè)t、

57、u、v恰有兩個正確那么MC3前往的 此概率為：3)假設(shè)t、u、v恰有一個正確，假設(shè)v正確，那么MC3前往正確答案，此概率為： if t=u or t=v if u=v tv正確正確221233 (3/4) (1/4)C p q 22(3/4)(1/4)pq 97971.6 Monte Carlo算法算法嚴(yán)厲的說，當(dāng)v正確，且錯誤的t和v不相等時，才有能夠勝利，因此MC3勝利的概率為： 多運(yùn)轉(zhuǎn)2次共3次Theorem：設(shè)+0是多小，均可經(jīng)過反復(fù)調(diào)用來擴(kuò)展其優(yōu)勢，使得最終的算法具有可接受的錯誤概率，使之恣意小選定的。pf：設(shè) 是調(diào)用MC(x)的次數(shù)。當(dāng)反復(fù)調(diào)用MC(x)算法n次時，假設(shè)正確解至少出

58、現(xiàn)m次，那么可以為新算法找到了正確解，因此其出錯概率至多為：/21, 1/2 /MC 11/2 /MCmnpqp 成功的概率失敗的概率lg1/nC99991.6 Monte Carlo算法算法10101/2/201/20/2/2/22(/2)lg(1/ )22Pri()/ /, /20241 41 4 /0 1 41,lg1/n.2mimin iimninimninnnnCnnp qinpqq pinpqqp niipqpqCq 次調(diào)用中出現(xiàn) 次正確解用取代lg(1/ )21/lglg /21/lg(1 4),0,2.2xCxx對任意/m/實(shí)際上，當(dāng)正確解出現(xiàn)次數(shù)1/2的要求可以放寬到p0即可

59、。1021021.6 Monte Carlo算法算法Def：(偏y0算法)更普通的(不在限定是斷定問題)，一個MC是偏y0的(y0是某個特定解)，假設(shè)存在問題實(shí)例的子集X使得：假設(shè)被解實(shí)例 ，那么算法MC(x)前往的解總是正確的(無論前往y0還是非y0)假設(shè) ，正確解是y0 ，但MC并非對一切這樣的實(shí)例x都前往正確解。顯然， y0是必需知道的，但無需測試x能否是X的成員，洗面解釋假設(shè)算法前往y0時，它總是正確的。即算法前往y0時總是正確的，前往非y0時以p為概率正確。xXxX 1031031.6 Monte Carlo算法算法設(shè)MC是一個一致的、p-correct和偏y0的蒙特卡洛算法，x是一

60、個實(shí)例，y是MC(x)前往的解，可分為如下2種情形討論：case1：假設(shè) ，那么算法MC總是前往正確解，因此y0確實(shí)是正確的。假設(shè) ，算法前往的正確解必定是y0這兩種情況均可得到結(jié)論： y0是一個正確解。case2：假設(shè) ，那么y是正確解。假設(shè) ，由于正確解是y0 ，故y是錯誤解，此出錯概率不超越1-p。xXxXxXxX0yy0yy1041041.6 Monte Carlo算法算法假設(shè)調(diào)用MC(x)k次所前往解依次是 ，那么： (1) 假設(shè)存在i使 ，那么前面的討論知，它是一個正確解(yi是正確解).(2) 假設(shè)存在 使 ，由于MC是一致的，故必有 。因此正確解仍是y0 。(3) 假設(shè)對一切的