第10章概率算法

1、算法设计与分析算法设计与分析清华大学出版社清华大学出版社第第10章章 概率算法概率算法 10.1 概概 述述 10.2 舍伍德舍伍德(Sherwood)型概率算法型概率算法10.3 拉斯维加斯拉斯维加斯(Las Vegas)型概率算法型概率算法10.4 蒙特卡罗蒙特卡罗(Monte Carlo)型概率算法型概率算法10.5 实验项目实验项目随机数发生器随机数发生器算法设计与分析算法设计与分析清华大学出版社清华大学出版社10.1 概概 述述 10.1.1 概率算法的设计思想概率算法的设计思想 10.1.2 随机数发生器随机数发生器 算法设计与分析算法设计与分析清华大学出版社清华大学出版社10.1

2、.1 概率算法的设计思想概率算法的设计思想 概率算法把概率算法把“对于所有合理的输入都必须对于所有合理的输入都必须给出正确的输出给出正确的输出”这一求解问题的条件放宽，把这一求解问题的条件放宽，把随机性随机性的选择注入到算法中，在算法执行某些步的选择注入到算法中，在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时骤时，可以随机地选择下一步该如何进行，同时允许结果以允许结果以较小的概率较小的概率出现错误，并以此为代价，出现错误，并以此为代价，获得算法运行时间的大幅度减少。获得算法运行时间的大幅度减少。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 例如，判断表达式例如，判断表

3、达式f(x1, x2, , xn)是否恒等于是否恒等于0。概率算法首先生成一个随机概率算法首先生成一个随机n元向量元向量(r1, r2, , rn)，并计算并计算f(r1, r2, , rn)的值，如果的值，如果f(r1, r2, , rn)0，则则f(x1, x2, , xn)0；如果；如果f(r1, r2, , rn)0，则或者，则或者f(x1, x2, , xn)恒等于恒等于0，或者是，或者是(r1, r2, , rn)比较特比较特殊，如果这样重复几次，继续得到殊，如果这样重复几次，继续得到f(r1, r2, , rn)0的结果，那么就可以得出的结果，那么就可以得出f(x1, x2, ,

4、 xn)恒等于恒等于0的结的结论，并且测试的随机向量越多，这个结果出错的可论，并且测试的随机向量越多，这个结果出错的可能性就越小。能性就越小。算法设计与分析算法设计与分析清华大学出版社清华大学出版社一般情况下，概率算法具有以下基本特征：一般情况下，概率算法具有以下基本特征：（1）概率算法的输入包括两部分，一部分是原）概率算法的输入包括两部分，一部分是原问题的输入，另一部分是一个供算法进行随机选问题的输入，另一部分是一个供算法进行随机选择的择的随机数序列随机数序列；（2）概率算法在运行过程中，包括一处或若干）概率算法在运行过程中，包括一处或若干处处随机选择随机选择，根据随机值来决定算法的运行；，

5、根据随机值来决定算法的运行；（3）概率算法的结果不能保证一定是正确的，）概率算法的结果不能保证一定是正确的，但可以限定其出错概率；但可以限定其出错概率；（4）概率算法在不同的运行中，对于相同的输）概率算法在不同的运行中，对于相同的输入实例可以有不同的结果，因此，对于相同的输入实例可以有不同的结果，因此，对于相同的输入实例，概率算法的入实例，概率算法的执行时间可能不同执行时间可能不同。算法设计与分析算法设计与分析清华大学出版社清华大学出版社 对于确定性算法，通常分析在平均情况下以对于确定性算法，通常分析在平均情况下以及最坏情况下的时间复杂性。对于概率算法，通及最坏情况下的时间复杂性。对于概率算法

6、，通常分析在平均情况下以及最坏情况下的常分析在平均情况下以及最坏情况下的期望期望时间时间复杂性，即由概率算法反复运行同一输入实例所复杂性，即由概率算法反复运行同一输入实例所得的平均运行时间。得的平均运行时间。 概率算法的时间性能概率算法的时间性能v需要强调的是，需要强调的是，“随机随机”并不意味着并不意味着“随意随意”。算法设计与分析算法设计与分析清华大学出版社清华大学出版社10.1.2 随机数发生器随机数发生器 目前，在计算机上产生随机数还是一个难题，因为在目前，在计算机上产生随机数还是一个难题，因为在原理上，这个问题只能近似解决。原理上，这个问题只能近似解决。 计算机中产生随机数的方法通常

7、采用线性同余法，产计算机中产生随机数的方法通常采用线性同余法，产生的随机数序列为生的随机数序列为a0, a1, , an，满足：，满足： （式（式10.1） 其中，其中，b0，c0，m0，dm。d称为随机数发生器的称为随机数发生器的随机种子（随机种子（Random Seed），当），当b、c和和m的值确定后，给定的值确定后，给定一个随机种子，由式一个随机种子，由式10.1产生的随机数序列也就确定了。产生的随机数序列也就确定了。, 2 , 1mod)(10nmcbaadann算法设计与分析算法设计与分析清华大学出版社清华大学出版社 计算机语言提供的随机数发生器，一般会输出一个分布计算机语言提供的

8、随机数发生器，一般会输出一个分布在开区间（在开区间（0, 1）上的随机小数，并且需要一个随机种子，）上的随机小数，并且需要一个随机种子，这个随机种子可以是系统当前的日期或时间。下面给出利用这个随机种子可以是系统当前的日期或时间。下面给出利用C+语言中的随机函数语言中的随机函数rand产生的分布在任意区间产生的分布在任意区间a, b上的上的随机数算法。随机数算法。算法10.1随机数发生器 int Random(int a, int b) return rand( )%(b-a)+a; /rand( )产生(0, 32767)之间的随机整数 算法设计与分析算法设计与分析清华大学出版社清华大学出版社

9、10.2 舍伍德舍伍德(Sherwood)型概率算法型概率算法 10.2.1 快速排序快速排序 10.2.2 选择问题选择问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社舍伍德舍伍德(Sherwood)型概率算法型概率算法 分析确定性算法在平均情况下的时间复杂性分析确定性算法在平均情况下的时间复杂性时，通常假定算法的输入实例满足某一特定的概时，通常假定算法的输入实例满足某一特定的概率分布。率分布。 事实上，很多算法对于不同的输入实例，其事实上，很多算法对于不同的输入实例，其运行时间差别很大。此时，可以采用舍伍德型概运行时间差别很大。此时，可以采用舍伍德型概率算法来消除算法的时间复杂

10、性与输入实例间的率算法来消除算法的时间复杂性与输入实例间的这种联系。这种联系。算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法10.2随机洗牌 void RandomShuffle(int n, int r ) for (i=0; in; i+) j=Random(0, n-i-1); rirj; /交换ri和rj 如果一个确定性算法无法直接改造成舍伍德型概率算法，如果一个确定性算法无法直接改造成舍伍德型概率算法，可借助于随机预处理技术，即不改变原有的确定性算法，可借助于随机预处理技术，即不改变原有的确定性算法，仅对其输入实例随机排列（称为洗牌）。假设输入实例为仅对其输入实例随机排

11、列（称为洗牌）。假设输入实例为整型，下面的随机洗牌算法可在线性时间实现对输入实例整型，下面的随机洗牌算法可在线性时间实现对输入实例的随机排列。的随机排列。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 舍伍德型概率算法总能求得问题的一个解，并且所求得的解总是正确的。但与其相对应的确定性算法相比，舍伍德型概率算法的平均时间复杂性没有改进。换言之，舍伍德型概率算法不是避免算法的最坏情况行为，而是设法消除了算法的不同输入实例对算法时间性能的影响，对所有输入实例而言，舍伍德型概率算法的运行时间相对比较均匀，其时间复杂性与原有的确定性算法在平均情况下的时间复杂性相当。 算法设计与分析算法设计

12、与分析清华大学出版社清华大学出版社10.2.1 快速排序快速排序 快速排序算法的关键在于一次划分中选择合适快速排序算法的关键在于一次划分中选择合适的轴值作为划分的基准，如果轴值是序列中最小的轴值作为划分的基准，如果轴值是序列中最小（或最大）记录，则一次划分后，由轴值分割得到（或最大）记录，则一次划分后，由轴值分割得到的两个子序列不均衡，使得快速排序的时间性能降的两个子序列不均衡，使得快速排序的时间性能降低。舍伍德型概率算法在一次划分之前，根据随机低。舍伍德型概率算法在一次划分之前，根据随机数在待划分序列中随机确定一个记录作为轴值，并数在待划分序列中随机确定一个记录作为轴值，并把它与第一个记录交

13、换，则一次划分后得到期望均把它与第一个记录交换，则一次划分后得到期望均衡的两个子序列，从而使算法的行为不受待排序序衡的两个子序列，从而使算法的行为不受待排序序列的不同输入实例的影响，使快速排序在最坏情况列的不同输入实例的影响，使快速排序在最坏情况下的时间性能趋近于平均情况的时间性能。下的时间性能趋近于平均情况的时间性能。算法设计与分析算法设计与分析清华大学出版社清华大学出版社一次划分结果一次划分结果 6 13 192331 35 28初始键值序列初始键值序列 6 13 19 23 31 35 58图图10.1 一次划分引入随机选择的示例一次划分引入随机选择的示例一次划分结果一次划分结果 613

14、 19 23 31 35 58初始键值序列初始键值序列 6 13 19 23 31 35 58随机选择一个随机选择一个 23 13 19 6 31 35 58记录与记录与6交换交换(a) 以最小值以最小值6为轴值，划分不均衡为轴值，划分不均衡(b) 随机选择轴值，划分均衡随机选择轴值，划分均衡算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法10.3随机快速排序随机快速排序 void QuickSort (int r , int low, int high) if (lowhigh) i=Random(low, high); rlowri; k=Partition(r, low,

15、 high); QuickSort(r, low, k- -1); QuickSort(r, k+1, high); 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 一次划分算法一次划分算法Partition与与4.3.2节中相同。算法节中相同。算法10.3在最坏情况下的时间复杂性仍是在最坏情况下的时间复杂性仍是O(n2)，这是由，这是由于随机数发生器在第于随机数发生器在第i次随机产生的轴值记录恰好都次随机产生的轴值记录恰好都是序列中第是序列中第i小（或第小（或第i大）记录。但是，作为随机大）记录。但是，作为随机数发生器，这种情况的出现概率是微乎其微的。事数发生器，这种情况的出现概率

16、是微乎其微的。事实上，输入记录的任何排列，都不可能出现使算法实上，输入记录的任何排列，都不可能出现使算法行为处于最坏的情况。因此，该算法的期望时间复行为处于最坏的情况。因此，该算法的期望时间复杂性是杂性是O(nlog2n)。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社10.2.2 选择问题选择问题 设无序序列设无序序列T=(r1, r2, , rn)，T的第的第k（1kn）小元素定义为小元素定义为T按升序排列后在第按升序排列后在第k个位置上的元素。个位置上的元素。给定一个序列给定一个序列T和一个整数和一个整数k，寻找，寻找T的第的第k小元素的小元素的问题称为选择问题。特别地，将寻

17、找第问题称为选择问题。特别地，将寻找第n/2小元素的小元素的问题称为中值问题。问题称为中值问题。算法设计与分析算法设计与分析清华大学出版社清华大学出版社 考虑快速排序中的划分过程，选定一个轴值将考虑快速排序中的划分过程，选定一个轴值将序列序列rirj进行划分，使得比轴值小的元素都位于轴进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是定轴值的最终位置是s，则：，则：（1）若）若k=s，则，则rs就是第就是第k小元素；小元素；（2）若）若ks，则第，则第k小元素一定在序列小元素一定在序列rs+1rj中；中

18、； ri rk rs-1 rs rs+1 rj 均均rs 轴值轴值 均均rs 查找这里查找这里 ri rs-1 rs rs+1 rk rj 均均rs 轴值轴值 均均rs 查找这里查找这里 (a) 若若ks，则，则rk在轴值的后面在轴值的后面算法设计与分析算法设计与分析清华大学出版社清华大学出版社 舍伍德型概率算法在一次划分之前，根据随机数在待划舍伍德型概率算法在一次划分之前，根据随机数在待划分序列中随机确定一个记录作为轴值，并把它与第一个记录分序列中随机确定一个记录作为轴值，并把它与第一个记录交换，则一次划分后得到期望均衡的两个子序列，使得选择交换，则一次划分后得到期望均衡的两个子序列，使得选

19、择问题在最坏情况下的时间性能趋近于平均情况的时间性能。问题在最坏情况下的时间性能趋近于平均情况的时间性能。算法算法10.4选择问题选择问题 int Select(int r , int low, int high, int k) if (high-lows) return Select(r, low, s-1, k); /在前半部分继续查找在前半部分继续查找 else return Select(r, s+1, high, k); /在后半部分继续查找在后半部分继续查找 算法设计与分析算法设计与分析清华大学出版社清华大学出版社10.3 10.3 拉斯维加斯拉斯维加斯(Las Vegas)(La

20、s Vegas)型概率算法型概率算法 10.3.1 10.3.1 八皇后问题八皇后问题10.3.2 10.3.2 整数因子分解问题整数因子分解问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社拉斯维加斯拉斯维加斯(Las Vegas)(Las Vegas)型概率算法型概率算法 拉斯维加斯型概率算法不时地做出可能导致拉斯维加斯型概率算法不时地做出可能导致算法陷入僵局的选择，并且算法能够检测是否陷算法陷入僵局的选择，并且算法能够检测是否陷入僵局，如果是，算法就承认失败。这种行为对入僵局，如果是，算法就承认失败。这种行为对于一个确定性算法是不能接受的，因为这意味着于一个确定性算法是不能接受

21、的，因为这意味着它不能解决相应的问题实例。但是，拉斯维加斯它不能解决相应的问题实例。但是，拉斯维加斯型概率算法的随机特性可以接受失败，只要这种型概率算法的随机特性可以接受失败，只要这种行为出现的概率不占多数。当出现失败时，只要行为出现的概率不占多数。当出现失败时，只要在相同的输入实例上再次运行概率算法，就又有在相同的输入实例上再次运行概率算法，就又有成功的可能。成功的可能。算法设计与分析算法设计与分析清华大学出版社清华大学出版社 拉斯维加斯型概率算法的一个显著特征是，它拉斯维加斯型概率算法的一个显著特征是，它所做的随机性选择有可能导致算法找不到问题的解，所做的随机性选择有可能导致算法找不到问题

22、的解，即算法运行一次，或者得到一个正确的解，或者无即算法运行一次，或者得到一个正确的解，或者无解。因此，需要对同解。因此，需要对同一输入实例反复多次运行算法，一输入实例反复多次运行算法，直到成功地获得问题的解。直到成功地获得问题的解。 由于拉斯维加斯型概率算法有时运行成功，有由于拉斯维加斯型概率算法有时运行成功，有时运行失败，因此，通常拉斯维加斯型概率算法的时运行失败，因此，通常拉斯维加斯型概率算法的返回类型为返回类型为boolbool，并且有两个参数：一个是算法的，并且有两个参数：一个是算法的输入，另一个是当算法运行成功时保存问题的解。输入，另一个是当算法运行成功时保存问题的解。当算法运行失

23、败时，可对同一输入实例再次运行，当算法运行失败时，可对同一输入实例再次运行，直到成功地获得问题的解。直到成功地获得问题的解。算法设计与分析算法设计与分析清华大学出版社清华大学出版社拉斯维加斯型概率算法的一般形式拉斯维加斯型概率算法的一般形式void Obstinate(input x, solution y) success=false; while (!success) success=LV(x, y);算法设计与分析算法设计与分析清华大学出版社清华大学出版社 设设p(x)是对输入实例是对输入实例x调用拉斯维加斯型概率调用拉斯维加斯型概率算法获得问题的一个解的概率，则一个正确的拉斯算法获得问

24、题的一个解的概率，则一个正确的拉斯维加斯型概率算法应该对于所有的输入实例维加斯型概率算法应该对于所有的输入实例x均有均有p(x)0。在更强的意义下，要求存在一个正的常数。在更强的意义下，要求存在一个正的常数，使得对于所有的输入实例，使得对于所有的输入实例x均有均有p(x)。由于。由于p(x)，所以，只要有足够的时间，对任何输入实，所以，只要有足够的时间，对任何输入实例例x，拉斯维加斯型概率算法总能找到问题的一个，拉斯维加斯型概率算法总能找到问题的一个解。换言之，拉斯维加斯型概率算法找到正确解的解。换言之，拉斯维加斯型概率算法找到正确解的概率随着计算时间的增加而提高。概率随着计算时间的增加而提高

25、。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社10.3.1 八皇后问题八皇后问题 八皇后问题是在八皇后问题是在88的棋盘上摆放八个皇后，的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。一行、同一列或同一斜线上。 对于八皇后问题的任何一个解而言，每一个皇对于八皇后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而后在棋盘上的位置无任何规律，不具有系统性，而更像是随机放置的。由此想到拉斯维加斯型概率算更像是随机放置的。由此想到拉斯维加斯型概率算法：在棋盘上相继的各行中随机地

26、放置皇后，并使法：在棋盘上相继的各行中随机地放置皇后，并使新放置的皇后与已放置的皇后互不攻击，直至八个新放置的皇后与已放置的皇后互不攻击，直至八个皇后均已相容地放置好，或下一个皇后没有可放置皇后均已相容地放置好，或下一个皇后没有可放置的位置。的位置。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 由于棋盘的每一行上可以而且必须放置一个皇后，所由于棋盘的每一行上可以而且必须放置一个皇后，所以八皇后问题的可能解用一个向量以八皇后问题的可能解用一个向量X=(x1, x2, , x8)表示，表示，其中，其中，1xi8并且并且1i8，即第，即第i个皇后放置在第个皇后放置在第i行第行第xi列上

27、。列上。由于两个皇后不能位于同一列上，所以，解向量由于两个皇后不能位于同一列上，所以，解向量X必须满必须满足约束条件：足约束条件： xixj （式（式10.2） 若两个皇后摆放的位置分别是若两个皇后摆放的位置分别是(i, xi)和和(j, xj)，在棋盘上，在棋盘上斜率为斜率为-1的斜线上，满足条件的斜线上，满足条件i-j= xi-xj，在棋盘上斜率为，在棋盘上斜率为1的斜线上，满足条件的斜线上，满足条件ij= xixj，综合两种情况，由于两，综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量个皇后不能位于同一斜线上，所以，解向量X必须满足约必须满足约束条件：束条件： |i-xi|j-

28、xj| （式（式10.3） 满足式满足式10.2和式和式10.3的向量的向量X=(x1, x2, , xi)表示已放置表示已放置的的i个皇后（个皇后（1i8）互不攻击，也就是不发生冲突。）互不攻击，也就是不发生冲突。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法10.5八皇后问题八皇后问题 1. 将数组将数组x8初始化为初始化为0；试探次数；试探次数count初始化为初始化为0； 2for (i=1; i=8; i+) 2.1 产生一个产生一个1, 8 的随机数的随机数j； 2.2 count=count+1，进行第，进行第count次试探；次试探； 2.3 若皇后若皇后i

29、放置在位置放置在位置j不发生冲突，不发生冲突， 则则xi=j；count=0；转步骤；转步骤2放置下一个皇后；放置下一个皇后； 2.4 若若(count= =8)，则无法放置皇后，则无法放置皇后i，算法运行失败；，算法运行失败； 否则，转步骤否则，转步骤2.1重新放置皇后重新放置皇后i； 3. 将元素将元素x1x8作为八皇后问题的一个解输出；作为八皇后问题的一个解输出； 拉斯维加斯型概率算法通过反复调用算法拉斯维加斯型概率算法通过反复调用算法10.5，直至得到八皇后问题的一个解。直至得到八皇后问题的一个解。算法设计与分析算法设计与分析清华大学出版社清华大学出版社 如果将上述随机放置策略与回溯法

30、相结合，则会获如果将上述随机放置策略与回溯法相结合，则会获得更好的效果。可以先在棋盘的若干行中随机地放置相得更好的效果。可以先在棋盘的若干行中随机地放置相容的皇后，然后在其他行中用回溯法继续放置，直至找容的皇后，然后在其他行中用回溯法继续放置，直至找到一个解或宣告失败。到一个解或宣告失败。 在棋盘中随机放置的皇后越多，回溯法搜索所需的在棋盘中随机放置的皇后越多，回溯法搜索所需的时间就越少，但失败的概率也就越大。时间就越少，但失败的概率也就越大。 例如八皇后问题，随机地放置两个皇后再采用回溯例如八皇后问题，随机地放置两个皇后再采用回溯法比完全采用回溯法快大约两倍；随机地放置三个皇后法比完全采用回

31、溯法快大约两倍；随机地放置三个皇后再采用回溯法比完全采用回溯法快大约一倍；而所有的再采用回溯法比完全采用回溯法快大约一倍；而所有的皇后都随机放置比完全采用回溯法慢大约一倍。皇后都随机放置比完全采用回溯法慢大约一倍。 很容易解释这个现象：不能忽略产生随机数所需的很容易解释这个现象：不能忽略产生随机数所需的时间，当随机放置所有的皇后时，八皇后问题的求解大时间，当随机放置所有的皇后时，八皇后问题的求解大约有约有70%的时间都用在了产生随机数上。的时间都用在了产生随机数上。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社10.3.2 整数因子分解问题整数因子分解问题 设设n是正整数且是正整数

32、且n1，整数，整数n的因子分解问题是的因子分解问题是找出找出n的如下形式的惟一分解式：的如下形式的惟一分解式： 其中，其中，p1p2pk是素数，是素数，m1, m2, , mk是正整是正整数。如果数。如果n是一个合数，则是一个合数，则n必有一个非平凡因子必有一个非平凡因子m（1mn），使得），使得m可以整除可以整除n。给定一个合数。给定一个合数n，求求n的一个非平凡因子的问题称为整数因子划分问的一个非平凡因子的问题称为整数因子划分问题。题。 kmkmmpppn2121算法设计与分析算法设计与分析清华大学出版社清华大学出版社 整数因子分解问题可以归结为整数因子整数因子分解问题可以归结为整数因子划

33、分和素数测试：假设对整数划分和素数测试：假设对整数n进行因子分进行因子分解，首先进行素数测试，如果解，首先进行素数测试，如果n是素数，则是素数，则分解完成；否则，再进行因子划分，找到分解完成；否则，再进行因子划分，找到n的一个非平凡因子的一个非平凡因子m，并递归地对，并递归地对m和和n/m进进行因子分解。行因子分解。 下面讨论整数因子划分问题。下面讨论整数因子划分问题。算法设计与分析算法设计与分析清华大学出版社清华大学出版社 对一个正整数对一个正整数n进行因子划分的最自然的想法进行因子划分的最自然的想法是试除，它可以找到是试除，它可以找到n的最小素数因子。的最小素数因子。算法算法10. .5整

34、数因子划分整数因子划分 int Factor(int n) i =sqrt(n); for (m=2; m1) return d; /若若y- -x与与n存在最大公约数存在最大公约数d，则，则d即为即为n的非平凡因子的非平凡因子 if (i= =k) y=x; k*=2; 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 算法算法Pollard中的中的while循环执行约循环执行约 次后，次后，会得到会得到n的一个素数因子的一个素数因子p。由于。由于n的最小素数的最小素数因子因子 ，故算法，故算法Pollard可在可在O(n1/4)的时间的时间内找到内找到n的一个素数因子。的一个素数因

35、子。 pnp 算法设计与分析算法设计与分析清华大学出版社清华大学出版社10.4 蒙特卡罗蒙特卡罗(Monte Carlo)型概率算法型概率算法10.4.1 主元素问题主元素问题10.4.2 素数测试问题素数测试问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社10.4.1 主元素问题主元素问题 设设Tn是一个含有是一个含有n个元素的数组，个元素的数组，x是数组是数组T的的一个元素，如果数组中有一半以上的元素与一个元素，如果数组中有一半以上的元素与x相同，相同，则称元素则称元素x是数组是数组T的主元素（的主元素（Major Element）。）。例如，在数组例如，在数组T7=3, 2,

36、 3, 2, 3, 3, 5中，元素中，元素3就是就是主元素。主元素。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 蒙特卡罗型概率算法求解主元素问题可以随机蒙特卡罗型概率算法求解主元素问题可以随机地选择数组中的一个元素地选择数组中的一个元素Ti进行统计，如果该元进行统计，如果该元素出现的次数大于素出现的次数大于n/2，则该元素就是数组的主元，则该元素就是数组的主元素，算法返回素，算法返回true；否则随机选择的这个元素；否则随机选择的这个元素Ti不是主元素，算法返回不是主元素，算法返回false。此时，数组中可能有。此时，数组中可能有主元素也可能没有主元素。如果数组中存在主元素，

37、主元素也可能没有主元素。如果数组中存在主元素，则非主元素的个数小于则非主元素的个数小于n/2。因此，算法将以大于。因此，算法将以大于1/2的概率返回的概率返回true，以小于，以小于1/2的概率返回的概率返回false，这说明算法出现错误的概率小于这说明算法出现错误的概率小于1/2。如果连续运。如果连续运行算法行算法k次，算法返回次，算法返回false的概率将减少为的概率将减少为2-k，则，则算法发生错误的概率为算法发生错误的概率为2-k。算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法10.8主元素问题主元素问题 bool Majority(int T , int n) i=

38、Random(0, n- -1); x=Ti; /随机选择一个数组元素随机选择一个数组元素 k=0; for (j=0; jn/2) / kn/2时含有主元素为时含有主元素为Ti return true; else return false; bool MajorityMC(int T , int n, double e) k=log(1/e)/log(2); for (i=1; i0，算法，算法MajorityMC重复重复调用调用 log2(1/ ) 次算法次算法Majority，其错误概率小于其错误概率小于 ，时间复杂性显然是，时间复杂性显然是O(nlog2(1/ )。算法设计与分析算法设

39、计与分析清华大学出版社清华大学出版社10.4.2 素数测试问题素数测试问题 测试一个整数测试一个整数n是否是素数，最简单的方法是把是否是素数，最简单的方法是把这个数除以这个数除以2 的数，如果余数为的数，如果余数为0，则，则n是是一个合数，否则，一个合数，否则，n就是一个素数。就是一个素数。 算法算法10. .9素数测试素数测试 bool Factor(int n) i =sqrt(n); for (m=2; m=i; m+) if (n % m= =0) return false; return true; /如果找不到一个因子，则如果找不到一个因子，则n是素数是素数 n算法设计与分析算法设

40、计与分析清华大学出版社清华大学出版社 算法算法10.9的时间复杂性是的时间复杂性是O( )。对于一个正。对于一个正整数整数n，其位数为，其位数为 ，则算法，则算法Factor的时间复杂性是的时间复杂性是O(10m/2)，因此，这个算法的时间因此，这个算法的时间复杂性是指数阶的。复杂性是指数阶的。费尔马定理费尔马定理 如果如果n是一个素数，是一个素数，a为正整数且为正整数且0an，则，则an-1 mod n1。 费尔马定理表明，如果存在一个小于费尔马定理表明，如果存在一个小于n的正的正整数整数a，使得，使得an-1 mod n1，则，则n肯定不是素数。肯定不是素数。n) 1(log10nm算法设

41、计与分析算法设计与分析清华大学出版社清华大学出版社 费尔马定理只是素数判定的一个必要条件，有些费尔马定理只是素数判定的一个必要条件，有些合数也满足费尔马定理，这些合数被称作合数也满足费尔马定理，这些合数被称作Carmichael数。数。Carmichael数是非常少的，在数是非常少的，在1100,000,000范范围内的整数中，只有围内的整数中，只有255个个Carmichael数。为了提高数。为了提高素数测试的准确性，可以多次随机选取小于素数测试的准确性，可以多次随机选取小于n的正整的正整数数a，重复计算，重复计算dan-1 mod n来判定来判定n是否是素数。是否是素数。例如，对于例如，对

42、于341，取，取a=3，则，则3340 mod 34156，从而，从而判定判定341不是素数。不是素数。算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法10.10Fermat测试测试int ExpMod(int n) /计算计算an-1 mod n a=Random(2, n- -1); /产生产生2, n- -1之间的一个随机整数之间的一个随机整数 b=1; for (i=1; i=n- -1; i+) b=(b*a) % n; return b;bool Prime1(int n) if (ExpMod(n)= =1) return true; /可能是素数或可能是素数或C

43、armichael数数 else return false; /一定不是素数一定不是素数算法设计与分析算法设计与分析清华大学出版社清华大学出版社 算法算法Prime1返回返回false时，整数时，整数n一定是一个合一定是一个合数，数，如果算法如果算法Prime1返回返回true，说明正整数，说明正整数n可能可能是素数，还可能是是素数，还可能是Carmichael数。但是，这个简数。但是，这个简单的测试却很少给出错误的结果。当一个合数单的测试却很少给出错误的结果。当一个合数n对对于整数于整数a满足费尔马定理时，称整数满足费尔马定理时，称整数a为合数为合数n的伪的伪证据（证据（Pseudowitn

44、ess）。所以，只有在选取到一）。所以，只有在选取到一个伪证据时，个伪证据时，Fermat测试的结论才是错误的。测试的结论才是错误的。 幸运的是伪证据相当少。在小于幸运的是伪证据相当少。在小于1000的的332个个合数中只有合数中只有5个没有伪证据，超过一半的合数只有个没有伪证据，超过一半的合数只有两个伪证据，超过两个伪证据，超过15个伪证据的合数不超过个伪证据的合数不超过160个。个。如果考虑更大的数，这个概率会更小。如果考虑更大的数，这个概率会更小。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社但是，有些合数的伪证据比例相当高，在小于但是，有些合数的伪证据比例相当高，在小于1000的合数中，的合数中，情况最坏的是情况最坏的是561，它有，它有318个伪证据。最坏的一个例子是一个伪证据。最坏的一个例子是一个个15位的合数位的合数651,693,055,693,681，它以大于，它以大于99.965的概的概率返回率返回true，尽管这个数确实是合数！此时，通过之前采用，尽管这个数确实是合数！此时，通过之前采用的技巧，将算法的技巧，将算法Prime1重复任意次数，都不能将误差概率重复任意次数，都不能将误差概率减少到