第九章随机算法

1、第九章 随机算法算法的特征：确定性。算法对所有可能的输入，都必须能够得到正确的答案。很多确定性的算法，其性能很坏。用随机选择的方法来改善算法的性能。某些方面可能不正确，对特定的输入，算法的每一次运行不一定得到相同结果。出现这种不正确的可能性很小，以致可以安全地不予理睬。9.1 随机算法引言解问题的随机算法定义为：设是问题的一个实例，用算法解的某些时刻，随机选取，由来决定算法的下一步动作。优点：1、执行时间和空间，小于同一问题的已知最好的确定性算法；2、实现比较简单，容易理解。一、类型：数值概率算法、拉斯维加斯（Las Vegas）算法、蒙特卡罗（Monte Carlo）算法、及舍伍德（Sher

2、wood）算法。1、数值概率算法：用于数值问题的求解。所得到的解几乎都是近似解，近似解的精度随着计算时间的增加而不断地提高。2、拉斯维加斯算法：要么给出问题的正确答案，要么得不到答案。反复求解多次，可使失效的概率任意小。3、蒙特卡罗算法：总能得到问题的答案，偶然产生不正确的答案。重复运行，每一次都进行随机选择，可使不正确答案的概率变得任意小。4、舍伍德算法：很多具有很好的平均运行时间的确定性算法，在最坏的情况下性能很坏。引入随机性加以改造，可以消除或减少一般情况和最坏情况的差别。二、时间复杂性的衡量衡量确定性算法的时间复杂性，是取它的平均运行时间。衡量随机算法的时间复杂性，是对确定实例的期望运

3、行时间，即反复地运行实例，所取的平均运行时间。在随机算法里，所讨论的是最坏情况下的期望时间，和平均情况下的期望时间。一、产生随机数的公式：产生065535的随机数序列，、为正整数，称为所产生的随机序列的种子。常数、，对所产生的随机序列的随机性能有很大的关系，通常取一素数。二、随机数发生器函数random_seed提供给用户选择随机数的种子，函数random计算新的种子，并产生一个范围为的新的随机数。#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）算法一、确定性算法的平均运行时间：确定性算法对输入实例的运行时间。：规模为的所有输入实例全体。算法的平均运行时间：存在实例， 。例：快速排序算法当输入数据均匀分布时，运行时间是。当输入数据按递增或递

5、减顺序排列时，算法的运行时间变坏二、舍伍德算法的基本思想消除不同输入实例对算法性能的影响，使随机算法对规模为的每一个实例，都有：三、期望运行时间：。当与相比很小可以忽略时，舍伍德算法有很好的性能。对所有输入实例而言，运行时间相对均匀。时间复杂性与确定性算法的时间复杂性相当随机选择枢点的快速排序算法。算法9.1 随机选择枢点的快速排序算法输入：数组A,数组元素的的起始位置low,终止位置high输出：按非降顺序排序的数组A 1. template <class Type>2. void quicksort_random(Type A,int low,int high) 3. 4. r

6、andom_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 = split(A,low,high);/* 按元素Alow把数组划分为两个 */ 8. r

7、_quicksort(A,low,k-1);/* 排序第一个子数组 */ 9. r_quicksort(A,k+1,high);/* 排序第二个子数组 */10. 11. 算法的期望运行时间是。从个元素中选择第小元素。算法9.2 随机选择算法输入：从数组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);/* 选择系统当前时间作为随机数种子 */ 5

8、. 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(low,high);/* 产生low到high之间的随机数i */8. swap(Alow,Ai);/* 把元素Ai交

9、换到数组的第一个位置*/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_select(A,i+1,high,k-i-1);/* 从第二个子数组寻找 */16. 17. 算法的运行时间1、最坏的情

10、况：第轮递归调用，所选择的枢点元素，恰是数组的第大、或第小元素。所执行的元素比较次数为发生这种情况的概率为，微乎其微。2、元素比较的期望次数小于。：对个元素的数组所执行的元素比较的期望次数。用数学归纳法证明。当及时，容易验证：，。假定，对所有的，成立。证明也成立。枢点元素的位置是中的任何一位置，并具有相同概率。因为序号从0开始，第小元素相当于数组的第位置。1）：枢点元素就是第小元素，调用一次 split函数，执行次元素比较操作2）：丢弃序号为等个元素，在其余个元素之中继续寻找第小元素，除调用 split函数所执行的次元素比较操作外，还需执行次元素比较操作。3）如果，丢弃序号为等个元素，在前面个

11、元素之中寻找第小元素，除调用 split函数所执行的次元素比较操作外，还需执行次元素比较操作。图9.1 枢点元素在第k小元素之前和之后的情况算法所执行的元素比较的期望次数为：因为是的非降函数，所以，当时，方程的值达最大。因此根据归纳定义，对所有的，成立。所以，有9.3 拉斯维加斯（Las Vegas）算法一、一般概念拉斯维加斯算法有时运行成功，有时失败，需要反复运行同一实例，直到成功为止。BOOL las_vegas()：解问题的某个实例的代码段。运行成功返回，否则返回。拉斯维加斯算法反复地运行下面的代码段：while(!las_vegas(P(x) ;直到运行成功返回为止。：对输入实例成功地

12、运行las_vegas的概率存在常数，使得对的所有实例，都有，则失败的概率小于。连续运行次，失败的概率降低为。充分大，趋于0。二、期望运行时间：成功地运行实例所花费的平均时间，：失败地运行实例所花费的平均时间，：成功运行的概率。则总的平均时间花费是：算法的期望运行时间为：字符串匹配长度分别为和的字符串和， 中是否包含有与相匹配的子串，称为字符串匹配。称为正文，称为模式。一、算法1在中设置长度为窗口，检查窗口中的子串是否与模式匹配。开始时，窗口位于的最左边的起始位置，逐个字符地向右移动窗口，直到窗口位于的最右边为止。检查窗口中的子串是否与模式匹配，需要次比较操作；窗口的移动次数最多为次。比较的总

13、次数为。二、RK（Rabin-Karp）算法1、其思想方法窗口中的子串和模式都赋予一个Hash函数，只有这两个Hash函数值相等时，才检查窗口中的子串是否与模式相匹配；否则，移动到下一个窗口。和中出现的字符集为， 。自然数集，函数为：，窗口中的子串，。把字符串中的字符都用函数映射为0的正整数，模式及窗口中的子串，可表示为以其基底的、具有位数字的进制数。例：模式的进制数可以表示为：其中，。窗口中的子串的进制数可表示为：其中，。引入Hash函数：其中，是某个充分大的素数。的Hash函数，有如下的递推关系：三、算法的实现算法9.3 字符串匹配输入：存放正文字符串的数组S,正文字符串的长度n,模式字符

14、串数组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 * 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行计算正文第一个窗口子串进制数的Hash值，需时间。第1112行计算模式串进制数的Hash值，同样需时间。第14行开始的while循环体最多执行次，如果所有窗口子串的Hash值都与模式串的Hash值不同，while循环所花费的时间为时间，整个算法的执行时间为时间。如果存在着一个与模式串Hash值相同的窗口子串， for循环的循环体只需时间，整个算法的执行时间仍为时间。2、，的假匹配情况算法执行时间仍然可能需要时间。

17、3、 素数整除引起假匹配。对所有的，都出现假匹配，只有素数整除下面的式子时才有可能：和都是具有位数字的进制数，。：小于的不同素数个数，已知渐近于。已知：若，整除的不同素数个数小于令，则整除上面式子的素数个数不会超过。令，小于的不同素数个数有个。考虑：在小于的素数集合中，随机地选择素数，出现假匹配的概率将小于。这样，可用下面的算法来实现字符串匹配：算法9.4 字符串匹配的随机算法输入：正文字符串的数组S,正文字符串的长度n,模式字符串数组P,模式字符串长度m, 小于R的素数集合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中的元素个数 */ 6. q = Rq; 7. match(S,n,P,m,loc,q); 8. 这个算法从小于的素数集合中随机地选择一个素数，使得在调用match时，出现假匹配的概率小于，从而在执行match的while循环时，最多增加时间。因此，这个算法的时间复杂性仍然为，而这是在提供小于的素数集合的数据下得到的。此外，这个算法总能给出正确的答案。假设是一个大于1的整数，如果是一个合数，必存在的一个非平凡

19、因子，使得整除。因此，给定一个合数，求的非平凡因子的问题，称为整数的因子分割问题。通常，可以用下面的算法来实现整数的因子分割问题。算法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. 显然，这个算法的时间复杂性是，当的位数是时，其时间复杂性为，是一个指数时间算法，效率很低。求整数因子的另一个算法是Pollard算法，它是一个拉斯维加斯算法。这个算

20、法选取之间的一个随机数，然后按下式：循环迭代，产生序列。对，及的和，求取与的最大公因子。如果是与的最大公因子。算法叙述如下。算法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; 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进行深入的分析得到，执行算法的while循环的循环体次后，就可以得到的一个因子。因为的最小因子，所以，这个算法的时间复杂性为。9.4 蒙特卡罗（Monte Carlo）算法蒙特卡罗算法总能得到问题的答案。偶然产生不正确的答案。：正确解的概率，称算法是正确的，优势为。运行同一实例两次，不会给出两个不同的正确答案，称算法是一致的。重复运行一致的正确的算法，每一次运行都独立地进行随机选择，可使产生不

22、正确答案的概率变得任意小。一、问题个元素的数组，中元素，若中一半以上元素与相同，称是的主元素。例：序列1,3,2,3,3,4,3中，元素3是主元素。二、一般方法每个元素和其它元素比较，并计数。如果计数值大于，该元素就是的主元素。元素比较次数为。三、蒙特卡罗算法1、随机选择元素进行测试，若返回，就是主元素；否则不是主元素。算法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_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、如果存在主元素，以大于的概率返回，小于的概率返回。连续运行次，返回的概率减少为，算法错误的概率为。希望错误概率小于，则令：算法修改为：算法9.8 求数组A的主元素输入：n个元素的数组A输出：数组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. 一次也检测不到主元素，返回；只要其中有一次检测到主元素，返回。算法的错误概率小于所给参数。算法的运行时间为。一、一般方法被测试的数除以2到 ëû 的数，余数为0，是合数，否则是素数。二、蒙特卡罗算法 1、定理9.1 如果是素数，则对所有小于的整数，都有。必要条件，而非充分条件，其逆非真定理表明：若存在，使得，则肯定不是素数。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 i

26、ntn; 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 * 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，1905等都满足条件。5、算法9