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

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

3、雜性，是對確定實例的期望運行時間，即反復地運行實例，所取的平均運行時間。在隨機算法里，所討論的是最壞情況下的期望時間，和平均情況下的期望時間。9.1.2 隨機數發生器一、產生隨機數的公式：（9.1.1）產生065535的隨機數序列，、為正整數，稱為所產生的隨機序列的種子。常數、，對所產生的隨機序列的隨機性能有很大的關系，通常取一素數。二、隨機數發生器函數random_seed提供給用戶選擇隨機數的種子，函數random計算新的種子，并產生一個范圍為的新的隨機數。#definemultiplier0x015a4e35l;#defineincrement1;static unsigned long

4、seed;void random_seed(unsigned long 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）算法一、確定性算法的平均運行時間：確定性算法對輸入實例的運行時間。：規模為的所有輸入實例全體。算法的平均運行時間：存在實例， 。例：快

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

6、cksort_random(type a,int low,int high) 3. 4. random_seed(0);/* 選擇系統當前時間作為隨機數種子 */ 5. r_quicksort(a,low,high);/* 遞歸調用隨機快速排序算法 */ 6. 1. void r_quicksort(type a,int low,int high)2. 3. int k; 4. if (low<high) 5. k = random(low,high);/* 產生low到high之間的隨機數k */ 6. swap(alow,ak);/* 把元素ak交換到數組的第一個位置*/ 7. k

7、= split(a,low,high);/* 按元素alow把數組劃分為兩個 */ 8. r_quicksort(a,low,k-1);/* 排序第一個子數組 */ 9. r_quicksort(a,k+1,high);/* 排序第二個子數組 */10. 11. 算法的期望運行時間是。9.2.3 隨機選擇算法從個元素中選擇第小元素。算法9.2 隨機選擇算法輸入：從數組a的第一個元素下標為low,最后一個元素下標為high中,選擇第k小元素輸出：所選擇的元素1. template <class type> 2. type select_random(type a,int low,in

8、t high,int k) 3. 4. random_seed(0);/* 選擇系統當前時間作為隨機數種子 */ 5. k = k 1;/* 使k從數組的第low元素開始計算 */ 5. return r_select(a,low,high,k);/* 遞歸調用隨機選擇算法 */ 6. 1. type r_select(type a,int low,int high,int k)2. 3. int i;4. if (high-low<=k)/* 第k小元素已位于子數組的最高端 */5. return ahigh;/* 直接返回最高端元素 */6. else 7. i = random(l

9、ow,high);/* 產生low到high之間的隨機數i */8. swap(alow,ai);/* 把元素ai交換到數組的第一個位置*/9. i = split(a,low,high);/* 按元素alow把數組劃分為兩個 */10. if (i-low)=k)/* 元素ai就是第k小元素 */11. return ai;/* 直接返回ai */12. else if (i-low)>k)/* 第k小元素位于第一個子數組 */13. return r_select(a,low,i-1,k);/* 從第一個子數組尋找 */14. else/* 否則 */15. return r_sel

10、ect(a,i+1,high,k-i-1);/* 從第二個子數組尋找 */16. 17. 算法的運行時間1、最壞的情況：第輪遞歸調用，所選擇的樞點元素，恰是數組的第大、或第小元素。所執行的元素比較次數為發生這種情況的概率為，微乎其微。2、元素比較的期望次數小于。：對個元素的數組所執行的元素比較的期望次數。用數學歸納法證明。當及時，容易驗證：，。假定，對所有的，成立。證明也成立。樞點元素的位置是中的任何一位置，并具有相同概率。因為序號從0開始，第小元素相當于數組的第位置。1）：樞點元素就是第小元素，調用一次 split函數，執行次元素比較操作2）：丟棄序號為等個元素，在其余個元素之中繼續尋找第小

11、元素，除調用 split函數所執行的次元素比較操作外，還需執行次元素比較操作。3）如果，丟棄序號為等個元素，在前面個元素之中尋找第小元素，除調用 split函數所執行的次元素比較操作外，還需執行次元素比較操作。圖9.1 樞點元素在第k小元素之前和之后的情況算法所執行的元素比較的期望次數為：因為是的非降函數，所以，當時，方程的值達最大。因此根據歸納定義，對所有的，成立。所以，有9.3 拉斯維加斯（las vegas）算法一、一般概念拉斯維加斯算法有時運行成功，有時失敗，需要反復運行同一實例，直到成功為止。bool las_vegas()：解問題的某個實例的代碼段。運行成功返回，否則返回。拉斯維加

12、斯算法反復地運行下面的代碼段：while(!las_vegas(p(x) ;直到運行成功返回為止。：對輸入實例成功地運行las_vegas的概率存在常數，使得對的所有實例，都有，則失敗的概率小于。連續運行次，失敗的概率降低為。充分大，趨于0。二、期望運行時間：成功地運行實例所花費的平均時間，：失敗地運行實例所花費的平均時間，：成功運行的概率。則總的平均時間花費是：算法的期望運行時間為：9.3.1 字符串匹配長度分別為和的字符串和， 中是否包含有與相匹配的子串，稱為字符串匹配。稱為正文，稱為模式。一、算法1在中設置長度為窗口，檢查窗口中的子串是否與模式匹配。開始時，窗口位于的最左邊的起始位置，逐

13、個字符地向右移動窗口，直到窗口位于的最右邊為止。檢查窗口中的子串是否與模式匹配，需要次比較操作；窗口的移動次數最多為次。比較的總次數為。二、rk（rabin-karp）算法1、其思想方法窗口中的子串和模式都賦予一個hash函數，只有這兩個hash函數值相等時，才檢查窗口中的子串是否與模式相匹配；否則，移動到下一個窗口。和中出現的字符集為， 。自然數集，函數為：，窗口中的子串，。把字符串中的字符都用函數映射為0的正整數，模式及窗口中的子串，可表示為以其基底的、具有位數字的進制數。例：模式的進制數可以表示為：其中，。窗口中的子串的進制數可表示為：其中，。引入hash函數：其中，是某個充分大的素數。

14、的hash函數，有如下的遞推關系：三、算法的實現算法9.3 字符串匹配輸入：存放正文字符串的數組s,正文字符串的長度n,模式字符串數組p,模式字符串長度m, 素數q輸出：與p相匹配的子串在正文中的起始位置loc 1. void match(char s,long n,char p,long m,long &loc,long q) 2. 3. long b = base;/* 字母集s的字符個數 */ 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 *

15、 b) % q; 9. for (i=0;i<m;i+)10. w = (w * b + ch(si) % q;/* 第一個窗口子串的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.

16、 if (k>=m) /* 模式串全部檢查完畢,則窗口子串匹配 */19. loc = i;/* 否則，不匹配 */20. 21. w = (w x) * b + si+m) % q; /*計算下一個窗口子串的hash值*/22. i+;23. 24. 四、時間復雜性1、第78行計算值，需時間；第910行計算正文第一個窗口子串進制數的hash值，需時間。第1112行計算模式串進制數的hash值，同樣需時間。第14行開始的while循環體最多執行次，如果所有窗口子串的hash值都與模式串的hash值不同，while循環所花費的時間為時間，整個算法的執行時間為時間。如果存在著一個與模式串ha

17、sh值相同的窗口子串， for循環的循環體只需時間，整個算法的執行時間仍為時間。2、，的假匹配情況算法執行時間仍然可能需要時間。3、 素數整除引起假匹配。對所有的，都出現假匹配，只有素數整除下面的式子時才有可能：和都是具有位數字的進制數，。：小于的不同素數個數，已知漸近于。已知：若，整除的不同素數個數小于令，則整除上面式子的素數個數不會超過。令，小于的不同素數個數有個。考慮：在小于的素數集合中，隨機地選擇素數，出現假匹配的概率將小于。這樣，可用下面的算法來實現字符串匹配：算法9.4 字符串匹配的隨機算法輸入：正文字符串的數組s,正文字符串的長度n,模式字符串數組p,模式字符串長度m, 小于r的

18、素數集合r輸出：與p相匹配的子串在正文中的起始位置loc 1. void match_random(char s,long n,char p,long m,long &loc,long r) 2. 3. long q;4. random_seed(0);5. q = random(1,a);/* a為集合r中的元素個數 */ 6. q = rq; 7. match(s,n,p,m,loc,q); 8. 這個算法從小于的素數集合中隨機地選擇一個素數，使得在調用match時，出現假匹配的概率小于，從而在執行match的while循環時，最多增加時間。因此，這個算法的時間復雜性仍然為，而這是

19、在提供小于的素數集合的數據下得到的。此外，這個算法總能給出正確的答案。9.3.2 整數因子假設是一個大于1的整數，如果是一個合數，必存在的一個非平凡因子，使得整除。因此，給定一個合數，求的非平凡因子的問題，稱為整數的因子分割問題。通常，可以用下面的算法來實現整數的因子分割問題。算法9.5 整數的因子分割問題輸入：整數n輸出：整數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. 顯然，這個算法的

20、時間復雜性是，當的位數是時，其時間復雜性為，是一個指數時間算法，效率很低。求整數因子的另一個算法是pollard算法，它是一個拉斯維加斯算法。這個算法選取之間的一個隨機數，然后按下式：循環迭代，產生序列。對，及的和，求取與的最大公因子。如果是的非平凡因子，算法結束。這個算法利用1.1.1節所敘述的求取兩個整數的最大公因子的歐幾里德算法，來求與的最大公因子。算法敘述如下。算法9.6 求取整數因子的pollard算法輸入：整數n輸出：整數n的因子 1. int pollard(int n) 2. 3. int i,k,x,y,d = 0; 4. random_seed(0); 5. i = 1;

21、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)&&(d<n)14. break;15. else if (i=k) 16. y = x;17. k *= 2;18. 19. 20. return d;21. 對算法pollard進行深入的分析得到，執行算法的while循環的循環體次后，就可以得到的一個因子。因為的最小因子，所以，這個算法的時間復雜性為。9.4 蒙特卡羅（mo

22、nte carlo）算法蒙特卡羅算法總能得到問題的答案。偶然產生不正確的答案。：正確解的概率，稱算法是正確的，優勢為。運行同一實例兩次，不會給出兩個不同的正確答案，稱算法是一致的。重復運行一致的正確的算法，每一次運行都獨立地進行隨機選擇，可使產生不正確答案的概率變得任意小。9.4.1 數組的主元素問題一、問題個元素的數組，中元素，若中一半以上元素與相同，稱是的主元素。例：序列1,3,2,3,3,4,3中，元素3是主元素。二、一般方法每個元素和其它元素比較，并計數。如果計數值大于，該元素就是的主元素。元素比較次數為。三、蒙特卡羅算法1、隨機選擇元素進行測試，若返回，就是主元素；否則不是主元素。算

23、法9.7 求數組a的主元素輸入：n個元素的數組a輸出：數組a的主元素 1. template <class type> 2. bool majority(type a,type &x,int n) 3. 4. int i,j,k; 5. random_seed(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、如果存在主元

24、素，以大于的概率返回，小于的概率返回。連續運行次，返回的概率減少為，算法錯誤的概率為。希望錯誤概率小于，則令：算法修改為：算法9.8 求數組a的主元素輸入：n個元素的數組a輸出：數組a的主元素 1. template <class type> 2. bool majority_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 = rand

25、om(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;19. 一次也檢測不到主元素，返回；只要其中有一次檢測到主元素，返回。算法的錯誤概率小于所給參數。算法的運行時間為。9.4.2 素數測試一、一般方法被測試的數除以2到 ëû 的數，余數為0，是合數，否則是素數。二、蒙特卡羅算法 1、定理9.1 如果是素數，則對所有小于的整數，都有。必要條件，而非充分條

26、件，其逆非真定理表明：若存在，使得，則肯定不是素數。2、計算的算法exp_mod算法9.9 指數運算后求模輸入：正整數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 intn; 5. while (m!=0) /* 把m轉換為二進制數字于bk */ 6. bk+ = m % 2;/* 若m=11,數組b內容順序為1,1,0,1*/ 7. m /= 2; 8. 9. c = 1;10. for (i=k-1;i>=0;i-) /* 計算 */11. c = (c

27、* c) % n;12. if (bk=1)13. c = (a * c) % n 14. 15. delete b;16. return c;17. 運行時間為時間。因為，因此，運行時間也是時間。3、測試整數是否是素數算法： 算法9.10 素數測試的一種版本輸入：正整數n輸出：若n是素數,返回true,否則返回false 1. bool prime_test1(int n) 2. 3. if (exp_mod(n,2,n-1)=1) 4. return true;/* 素數或偽素數 */ 5. else 6. return false;/* 合數 */ 7. 4、carmichael數：存在整數，使得成立的合數，以為基數的偽素數。例：4到2000之間的所有合數中，有341，561，645，1105，1387，1729，190