第九章隨機算法

1、第九章 隨機算法算法的特征：確定性。算法對所有可能的輸入，都必須能夠得到正確的答案。很多確定性的算法，其性能很壞。用隨機選擇的方法來改善算法的性能。某些方面可能不正確，對特定的輸入，算法的每一次運行不一定得到相同結(jié)果。出現(xiàn)這種不正確的可能性很小，以致可以安全地不予理睬。9.1 隨機算法引言解問題的隨機算法定義為：設(shè)是問題的一個實例，用算法解的某些時刻，隨機選取，由來決定算法的下一步動作。優(yōu)點：1、執(zhí)行時間和空間，小于同一問題的已知最好的確定性算法；2、實現(xiàn)比較簡單，容易理解。一、類型：數(shù)值概率算法、拉斯維加斯（Las Vegas）算法、蒙特卡羅（Monte Carlo）算法、及舍伍德（Sher

2、wood）算法。1、數(shù)值概率算法：用于數(shù)值問題的求解。所得到的解幾乎都是近似解，近似解的精度隨著計算時間的增加而不斷地提高。2、拉斯維加斯算法：要么給出問題的正確答案，要么得不到答案。反復求解多次，可使失效的概率任意小。3、蒙特卡羅算法：總能得到問題的答案，偶然產(chǎn)生不正確的答案。重復運行，每一次都進行隨機選擇，可使不正確答案的概率變得任意小。4、舍伍德算法：很多具有很好的平均運行時間的確定性算法，在最壞的情況下性能很壞。引入隨機性加以改造，可以消除或減少一般情況和最壞情況的差別。二、時間復雜性的衡量衡量確定性算法的時間復雜性，是取它的平均運行時間。衡量隨機算法的時間復雜性，是對確定實例的期望運

3、行時間，即反復地運行實例，所取的平均運行時間。在隨機算法里，所討論的是最壞情況下的期望時間，和平均情況下的期望時間。一、產(chǎn)生隨機數(shù)的公式：產(chǎn)生065535的隨機數(shù)序列，、為正整數(shù)，稱為所產(chǎn)生的隨機序列的種子。常數(shù)、，對所產(chǎn)生的隨機序列的隨機性能有很大的關(guān)系，通常取一素數(shù)。二、隨機數(shù)發(fā)生器函數(shù)random_seed提供給用戶選擇隨機數(shù)的種子，函數(shù)random計算新的種子，并產(chǎn)生一個范圍為的新的隨機數(shù)。#defineMULTIPLIER0x015A4E35L;#defineINCREMENT1;static unsigned longseed;void random_seed(unsigned l

4、ong d)if (d=0) seed = time(0);else seed = d;unsigned int random(unsigned long low,unsigned long high)seed = MULTIPLIER * seed + INCREMENT;return (seed >> 16) % (high low) + low);9.2 舍伍德（Sherwood）算法一、確定性算法的平均運行時間：確定性算法對輸入實例的運行時間。：規(guī)模為的所有輸入實例全體。算法的平均運行時間：存在實例， 。例：快速排序算法當輸入數(shù)據(jù)均勻分布時，運行時間是。當輸入數(shù)據(jù)按遞增或遞

5、減順序排列時，算法的運行時間變壞二、舍伍德算法的基本思想消除不同輸入實例對算法性能的影響，使隨機算法對規(guī)模為的每一個實例，都有：三、期望運行時間：。當與相比很小可以忽略時，舍伍德算法有很好的性能。對所有輸入實例而言，運行時間相對均勻。時間復雜性與確定性算法的時間復雜性相當隨機選擇樞點的快速排序算法。算法9.1 隨機選擇樞點的快速排序算法輸入：數(shù)組A,數(shù)組元素的的起始位置low,終止位置high輸出：按非降順序排序的數(shù)組A 1. template <class Type>2. void quicksort_random(Type A,int low,int high) 3. 4. r

6、andom_seed(0);/* 選擇系統(tǒng)當前時間作為隨機數(shù)種子 */ 5. r_quicksort(A,low,high);/* 遞歸調(diào)用隨機快速排序算法 */ 6. 1. void r_quicksort(Type A,int low,int high)2. 3. int k; 4. if (low<high) 5. k = random(low,high);/* 產(chǎn)生low到high之間的隨機數(shù)k */ 6. swap(Alow,Ak);/* 把元素Ak交換到數(shù)組的第一個位置*/ 7. k = split(A,low,high);/* 按元素Alow把數(shù)組劃分為兩個 */ 8. r

7、_quicksort(A,low,k-1);/* 排序第一個子數(shù)組 */ 9. r_quicksort(A,k+1,high);/* 排序第二個子數(shù)組 */10. 11. 算法的期望運行時間是。從個元素中選擇第小元素。算法9.2 隨機選擇算法輸入：從數(shù)組A的第一個元素下標為low,最后一個元素下標為high中,選擇第k小元素輸出：所選擇的元素1. template <class Type> 2. Type select_random(Type A,int low,int high,int k) 3. 4. random_seed(0);/* 選擇系統(tǒng)當前時間作為隨機數(shù)種子 */ 5

8、. k = k 1;/* 使k從數(shù)組的第low元素開始計算 */ 5. return r_select(A,low,high,k);/* 遞歸調(diào)用隨機選擇算法 */ 6. 1. Type r_select(Type A,int low,int high,int k)2. 3. int i;4. if (high-low<=k)/* 第k小元素已位于子數(shù)組的最高端 */5. return Ahigh;/* 直接返回最高端元素 */6. else 7. i = random(low,high);/* 產(chǎn)生low到high之間的隨機數(shù)i */8. swap(Alow,Ai);/* 把元素Ai交

9、換到數(shù)組的第一個位置*/9. i = split(A,low,high);/* 按元素Alow把數(shù)組劃分為兩個 */10. if (i-low)=k)/* 元素Ai就是第k小元素 */11. return Ai;/* 直接返回Ai */12. else if (i-low)>k)/* 第k小元素位于第一個子數(shù)組 */13. return r_select(A,low,i-1,k);/* 從第一個子數(shù)組尋找 */14. else/* 否則 */15. return r_select(A,i+1,high,k-i-1);/* 從第二個子數(shù)組尋找 */16. 17. 算法的運行時間1、最壞的情

10、況：第輪遞歸調(diào)用，所選擇的樞點元素，恰是數(shù)組的第大、或第小元素。所執(zhí)行的元素比較次數(shù)為發(fā)生這種情況的概率為，微乎其微。2、元素比較的期望次數(shù)小于。：對個元素的數(shù)組所執(zhí)行的元素比較的期望次數(shù)。用數(shù)學歸納法證明。當及時，容易驗證：，。假定，對所有的，成立。證明也成立。樞點元素的位置是中的任何一位置，并具有相同概率。因為序號從0開始，第小元素相當于數(shù)組的第位置。1）：樞點元素就是第小元素，調(diào)用一次 split函數(shù)，執(zhí)行次元素比較操作2）：丟棄序號為等個元素，在其余個元素之中繼續(xù)尋找第小元素，除調(diào)用 split函數(shù)所執(zhí)行的次元素比較操作外，還需執(zhí)行次元素比較操作。3）如果，丟棄序號為等個元素，在前面?zhèn)€

11、元素之中尋找第小元素，除調(diào)用 split函數(shù)所執(zhí)行的次元素比較操作外，還需執(zhí)行次元素比較操作。圖9.1 樞點元素在第k小元素之前和之后的情況算法所執(zhí)行的元素比較的期望次數(shù)為：因為是的非降函數(shù)，所以，當時，方程的值達最大。因此根據(jù)歸納定義，對所有的，成立。所以，有9.3 拉斯維加斯（Las Vegas）算法一、一般概念拉斯維加斯算法有時運行成功，有時失敗，需要反復運行同一實例，直到成功為止。BOOL las_vegas()：解問題的某個實例的代碼段。運行成功返回，否則返回。拉斯維加斯算法反復地運行下面的代碼段：while(!las_vegas(P(x) ;直到運行成功返回為止。：對輸入實例成功地

12、運行l(wèi)as_vegas的概率存在常數(shù)，使得對的所有實例，都有，則失敗的概率小于。連續(xù)運行次，失敗的概率降低為。充分大，趨于0。二、期望運行時間：成功地運行實例所花費的平均時間，：失敗地運行實例所花費的平均時間，：成功運行的概率。則總的平均時間花費是：算法的期望運行時間為：字符串匹配長度分別為和的字符串和， 中是否包含有與相匹配的子串，稱為字符串匹配。稱為正文，稱為模式。一、算法1在中設(shè)置長度為窗口，檢查窗口中的子串是否與模式匹配。開始時，窗口位于的最左邊的起始位置，逐個字符地向右移動窗口，直到窗口位于的最右邊為止。檢查窗口中的子串是否與模式匹配，需要次比較操作；窗口的移動次數(shù)最多為次。比較的總

13、次數(shù)為。二、RK（Rabin-Karp）算法1、其思想方法窗口中的子串和模式都賦予一個Hash函數(shù)，只有這兩個Hash函數(shù)值相等時，才檢查窗口中的子串是否與模式相匹配；否則，移動到下一個窗口。和中出現(xiàn)的字符集為， 。自然數(shù)集，函數(shù)為：，窗口中的子串，。把字符串中的字符都用函數(shù)映射為0的正整數(shù)，模式及窗口中的子串，可表示為以其基底的、具有位數(shù)字的進制數(shù)。例：模式的進制數(shù)可以表示為：其中，。窗口中的子串的進制數(shù)可表示為：其中，。引入Hash函數(shù)：其中，是某個充分大的素數(shù)。的Hash函數(shù)，有如下的遞推關(guān)系：三、算法的實現(xiàn)算法9.3 字符串匹配輸入：存放正文字符串的數(shù)組S,正文字符串的長度n,模式字符

14、串數(shù)組P,模式字符串長度m, 素數(shù)q輸出：與P相匹配的子串在正文中的起始位置loc 1. void match(char S,long n,char P,long m,long &loc,long q) 2. 3. long b = BASE;/* 字母集S的字符個數(shù) */ 4. long i,j,k; 6. long w=0,p=0;5. long x=1; 7. for (i=0;i<m-1;i+)/* 計算 mod q */ 8. x = (x * b) % q; 9. for (i=0;i<m;i+)10. w = (w * b + ch(Si) % q;/* 第一

15、個窗口子串的Hash值*/ 11. for (i=0;i<m;i+)12. p = (p * b + ch(Pi) % q;/* 模式串的Hash值*/ 13. i = 0; loc = -1;14. while (i<n-m) && (loc=-1) 15. if (w=p) /* 判斷Hash值相等? */16. for (k=0;k<m;k+)/* 若相等,檢查是否匹配 */17. if (Si+k!=Pk) break;18. if (k>=m) /* 模式串全部檢查完畢,則窗口子串匹配 */19. loc = i;/* 否則，不匹配 */20.

16、 21. w = (w x) * b + Si+m) % q; /*計算下一個窗口子串的Hash值*/22. i+;23. 24. 四、時間復雜性1、第78行計算值，需時間；第910行計算正文第一個窗口子串進制數(shù)的Hash值，需時間。第1112行計算模式串進制數(shù)的Hash值，同樣需時間。第14行開始的while循環(huán)體最多執(zhí)行次，如果所有窗口子串的Hash值都與模式串的Hash值不同，while循環(huán)所花費的時間為時間，整個算法的執(zhí)行時間為時間。如果存在著一個與模式串Hash值相同的窗口子串， for循環(huán)的循環(huán)體只需時間，整個算法的執(zhí)行時間仍為時間。2、，的假匹配情況算法執(zhí)行時間仍然可能需要時間。

17、3、 素數(shù)整除引起假匹配。對所有的，都出現(xiàn)假匹配，只有素數(shù)整除下面的式子時才有可能：和都是具有位數(shù)字的進制數(shù)，。：小于的不同素數(shù)個數(shù)，已知漸近于。已知：若，整除的不同素數(shù)個數(shù)小于令，則整除上面式子的素數(shù)個數(shù)不會超過。令，小于的不同素數(shù)個數(shù)有個?？紤]：在小于的素數(shù)集合中，隨機地選擇素數(shù)，出現(xiàn)假匹配的概率將小于。這樣，可用下面的算法來實現(xiàn)字符串匹配：算法9.4 字符串匹配的隨機算法輸入：正文字符串的數(shù)組S,正文字符串的長度n,模式字符串數(shù)組P,模式字符串長度m, 小于R的素數(shù)集合R輸出：與P相匹配的子串在正文中的起始位置loc 1. void match_random(char S,long n,

18、char P,long m,long &loc,long R) 2. 3. long q;4. random_seed(0);5. q = random(1,a);/* a為集合R中的元素個數(shù) */ 6. q = Rq; 7. match(S,n,P,m,loc,q); 8. 這個算法從小于的素數(shù)集合中隨機地選擇一個素數(shù)，使得在調(diào)用match時，出現(xiàn)假匹配的概率小于，從而在執(zhí)行match的while循環(huán)時，最多增加時間。因此，這個算法的時間復雜性仍然為，而這是在提供小于的素數(shù)集合的數(shù)據(jù)下得到的。此外，這個算法總能給出正確的答案。假設(shè)是一個大于1的整數(shù)，如果是一個合數(shù)，必存在的一個非平凡

19、因子，使得整除。因此，給定一個合數(shù)，求的非平凡因子的問題，稱為整數(shù)的因子分割問題。通常，可以用下面的算法來實現(xiàn)整數(shù)的因子分割問題。算法9.5 整數(shù)的因子分割問題輸入：整數(shù)n輸出：整數(shù)n的因子 1. int factor(int n) 2. 3. int i,m; 4. m = sqrt(double)n); 5. for (i=2;i<m;i+) 6. if (n%i=0) return i; 7. return 1; 8. 顯然，這個算法的時間復雜性是，當?shù)奈粩?shù)是時，其時間復雜性為，是一個指數(shù)時間算法，效率很低。求整數(shù)因子的另一個算法是Pollard算法，它是一個拉斯維加斯算法。這個算

20、法選取之間的一個隨機數(shù)，然后按下式：循環(huán)迭代，產(chǎn)生序列。對，及的和，求取與的最大公因子。如果是與的最大公因子。算法敘述如下。算法9.6 求取整數(shù)因子的Pollard算法輸入：整數(shù)n輸出：整數(shù)n的因子 1. int pollard(int n) 2. 3. int i,k,x,y,d = 0; 4. random_seed(0); 5. i = 1; 6. k = 2; 7. x = random(1,n); 8. y = x; 9. while (i<n) 10. i+;11. x = (x * x 1) % n;12. d = euclid(n,y-x);13. if (d>1)

21、&&(d<n)14. break;15. else if (i=k) 16. y = x;17. k *= 2;18. 19. 20. return d;21. 對算法Pollard進行深入的分析得到，執(zhí)行算法的while循環(huán)的循環(huán)體次后，就可以得到的一個因子。因為的最小因子，所以，這個算法的時間復雜性為。9.4 蒙特卡羅（Monte Carlo）算法蒙特卡羅算法總能得到問題的答案。偶然產(chǎn)生不正確的答案。：正確解的概率，稱算法是正確的，優(yōu)勢為。運行同一實例兩次，不會給出兩個不同的正確答案，稱算法是一致的。重復運行一致的正確的算法，每一次運行都獨立地進行隨機選擇，可使產(chǎn)生不

22、正確答案的概率變得任意小。一、問題個元素的數(shù)組，中元素，若中一半以上元素與相同，稱是的主元素。例：序列1,3,2,3,3,4,3中，元素3是主元素。二、一般方法每個元素和其它元素比較，并計數(shù)。如果計數(shù)值大于，該元素就是的主元素。元素比較次數(shù)為。三、蒙特卡羅算法1、隨機選擇元素進行測試，若返回，就是主元素；否則不是主元素。算法9.7 求數(shù)組A的主元素輸入：n個元素的數(shù)組A輸出：數(shù)組A的主元素 1. template <class Type> 2. BOOL majority(Type A,Type &x,int n) 3. 4. int i,j,k; 5. random_se

23、ed(0); 6. i = random(0,n-1) ;7. k = 0; 8. for (j=0;j<n;j+) 9. if (Ai=Aj)10. k+;11. if (k>n/2) 12. x = Ai; return TRUE;13. 14. else return FALSE;15. 2、如果存在主元素，以大于的概率返回，小于的概率返回。連續(xù)運行次，返回的概率減少為，算法錯誤的概率為。希望錯誤概率小于，則令：算法修改為：算法9.8 求數(shù)組A的主元素輸入：n個元素的數(shù)組A輸出：數(shù)組A的主元素 1. template <class Type> 2. BOOL ma

24、jority_monte(Type A,Type &x,int n,double e) 3. 4. int t,s,i,j,k; 5. BOOL flag = FALSE; 6. random_seed(0); 7. s = log(1/e); 8. for (t=1;t<=s;t+) 9. i = random(0,n-1) ;10. k = 0;11. for (j=0;j<n;j+) 12. if (Ai=Aj)13. k+;14. if (k>n/2) 15. x = Ai; flag = TRUE; break;16. 17. 18. return flag

25、;19. 一次也檢測不到主元素，返回；只要其中有一次檢測到主元素，返回。算法的錯誤概率小于所給參數(shù)。算法的運行時間為。一、一般方法被測試的數(shù)除以2到 ëû 的數(shù)，余數(shù)為0，是合數(shù)，否則是素數(shù)。二、蒙特卡羅算法 1、定理9.1 如果是素數(shù)，則對所有小于的整數(shù)，都有。必要條件，而非充分條件，其逆非真定理表明：若存在，使得，則肯定不是素數(shù)。2、計算的算法exp_mod算法9.9 指數(shù)運算后求模輸入：正整數(shù)a,m,n,m<n輸出： 1. int exp_mod(int n, int a,int m) 2. 3. int i,c,k = 0; 4. int *b = new i

26、ntn; 5. while (m!=0) /* 把m轉(zhuǎn)換為二進制數(shù)字于bk */ 6. bk+ = m % 2;/* 若m=11,數(shù)組b內(nèi)容順序為1,1,0,1*/ 7. m /= 2; 8. 9. c = 1;10. for (i=k-1;i>=0;i-) /* 計算 */11. c = (c * c) % n;12. if (bk=1)13. c = (a * c) % n 14. 15. delete b;16. return c;17. 運行時間為時間。因為，因此，運行時間也是時間。3、測試整數(shù)是否是素數(shù)算法： 算法9.10 素數(shù)測試的一種版本輸入：正整數(shù)n輸出：若n是素數(shù),返回TRUE,否則返回FALSE 1. BOOL prime_test1(int n) 2. 3. if (exp_mod(n,2,n-1)=1) 4. return TRUE;/* 素數(shù)或偽素數(shù) */ 5. else 6. return FALSE;/* 合數(shù) */ 7. 4、Carmichael數(shù)：存在整數(shù)，使得成立的合數(shù)，以為基數(shù)的偽素數(shù)。例：4到2000之間的所有合數(shù)中，有341，561，645，1105，1387，1729，1905等都滿足條件。5、算法9