第10章 概率算法.ppt

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

2、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, , xn)恒等于0的结论，并且测试的随机向量越多，这个结果出错的可能性就越小。,一般情况下，概率算法具有以下基本特征： （1）概率算法的输入包括两部分，

3、一部分是原问题的输入，另一部分是一个供算法进行随机选择的随机数序列； （2）概率算法在运行过程中，包括一处或若干处随机选择，根据随机值来决定算法的运行； （3）概率算法的结果不能保证一定是正确的，但可以限定其出错概率； （4）概率算法在不同的运行中，对于相同的输入实例可以有不同的结果，因此，对于相同的输入实例，概率算法的执行时间可能不同。,对于确定性算法，通常分析在平均情况下以及最坏情况下的时间复杂性。对于概率算法，通常分析在平均情况下以及最坏情况下的期望时间复杂性，即由概率算法反复运行同一输入实例所得的平均运行时间。,概率算法的时间性能,需要强调的是，“随机”并不意味着“随意”。,10.1.

4、2 随机数发生器,目前，在计算机上产生随机数还是一个难题，因为在原理上，这个问题只能近似解决。 计算机中产生随机数的方法通常采用线性同余法，产生的随机数序列为a0, a1, , an，满足： （式10.1） 其中，b0，c0，m0，dm。d称为随机数发生器的随机种子（Random Seed），当b、c和m的值确定后，给定一个随机种子，由式10.1产生的随机数序列也就确定了。,计算机语言提供的随机数发生器，一般会输出一个分布在开区间（0, 1）上的随机小数，并且需要一个随机种子，这个随机种子可以是系统当前的日期或时间。下面给出利用C+语言中的随机函数rand产生的分布在任意区间a, b上的随机数

5、算法。,10.2 舍伍德(Sherwood)型概率算法,10.2.1 快速排序,10.2.2 选择问题,舍伍德(Sherwood)型概率算法,分析确定性算法在平均情况下的时间复杂性时，通常假定算法的输入实例满足某一特定的概率分布。 事实上，很多算法对于不同的输入实例，其运行时间差别很大。此时，可以采用舍伍德型概率算法来消除算法的时间复杂性与输入实例间的这种联系。,如果一个确定性算法无法直接改造成舍伍德型概率算法，可借助于随机预处理技术，即不改变原有的确定性算法，仅对其输入实例随机排列（称为洗牌）。假设输入实例为整型，下面的随机洗牌算法可在线性时间实现对输入实例的随机排列。,舍伍德型概率算法总能

6、求得问题的一个解，并且所求得的解总是正确的。但与其相对应的确定性算法相比，舍伍德型概率算法的平均时间复杂性没有改进。换言之，舍伍德型概率算法不是避免算法的最坏情况行为，而是设法消除了算法的不同输入实例对算法时间性能的影响，对所有输入实例而言，舍伍德型概率算法的运行时间相对比较均匀，其时间复杂性与原有的确定性算法在平均情况下的时间复杂性相当。,10.2.1 快速排序,快速排序算法的关键在于一次划分中选择合适的轴值作为划分的基准，如果轴值是序列中最小（或最大）记录，则一次划分后，由轴值分割得到的两个子序列不均衡，使得快速排序的时间性能降低。舍伍德型概率算法在一次划分之前，根据随机数在待划分序列中随

7、机确定一个记录作为轴值，并把它与第一个记录交换，则一次划分后得到期望均衡的两个子序列，从而使算法的行为不受待排序序列的不同输入实例的影响，使快速排序在最坏情况下的时间性能趋近于平均情况的时间性能。,一次划分算法Partition与4.3.2节中相同。算法10.3在最坏情况下的时间复杂性仍是O(n2)，这是由于随机数发生器在第i次随机产生的轴值记录恰好都是序列中第i小（或第i大）记录。但是，作为随机数发生器，这种情况的出现概率是微乎其微的。事实上，输入记录的任何排列，都不可能出现使算法行为处于最坏的情况。因此，该算法的期望时间复杂性是O(nlog2n)。,10.2.2 选择问题,设无序序列T=(

8、r1, r2, , rn)，T的第k（1kn）小元素定义为T按升序排列后在第k个位置上的元素。给定一个序列T和一个整数k，寻找T的第k小元素的问题称为选择问题。特别地，将寻找第n/2小元素的问题称为中值问题。,考虑快速排序中的划分过程，选定一个轴值将序列rirj进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是s，则： （1）若k=s，则rs就是第k小元素； （2）若ks，则第k小元素一定在序列rs+1rj中；,舍伍德型概率算法在一次划分之前，根据随机数在待划分序列中随机确定一个记录作为轴值，并把它与第一个记录交换，则一次划分后得到期望均衡的两个

9、子序列，使得选择问题在最坏情况下的时间性能趋近于平均情况的时间性能。,10.3 拉斯维加斯(Las Vegas)型概率算法,10.3.1 八皇后问题,10.3.2 整数因子分解问题,拉斯维加斯(Las Vegas)型概率算法,拉斯维加斯型概率算法不时地做出可能导致算法陷入僵局的选择，并且算法能够检测是否陷入僵局，如果是，算法就承认失败。这种行为对于一个确定性算法是不能接受的，因为这意味着它不能解决相应的问题实例。但是，拉斯维加斯型概率算法的随机特性可以接受失败，只要这种行为出现的概率不占多数。当出现失败时，只要在相同的输入实例上再次运行概率算法，就又有成功的可能。,拉斯维加斯型概率算法的一个显

10、著特征是，它所做的随机性选择有可能导致算法找不到问题的解，即算法运行一次，或者得到一个正确的解，或者无解。因此，需要对同一输入实例反复多次运行算法，直到成功地获得问题的解。 由于拉斯维加斯型概率算法有时运行成功，有时运行失败，因此，通常拉斯维加斯型概率算法的返回类型为bool，并且有两个参数：一个是算法的输入，另一个是当算法运行成功时保存问题的解。当算法运行失败时，可对同一输入实例再次运行，直到成功地获得问题的解。,拉斯维加斯型概率算法的一般形式 void Obstinate(input x, solution y) success=false; while (!success) succes

11、s=LV(x, y); ,设p(x)是对输入实例x调用拉斯维加斯型概率算法获得问题的一个解的概率，则一个正确的拉斯维加斯型概率算法应该对于所有的输入实例x均有p(x)0。在更强的意义下，要求存在一个正的常数，使得对于所有的输入实例x均有p(x)。由于p(x)，所以，只要有足够的时间，对任何输入实例x，拉斯维加斯型概率算法总能找到问题的一个解。换言之，拉斯维加斯型概率算法找到正确解的概率随着计算时间的增加而提高。,10.3.1 八皇后问题,八皇后问题是在88的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。 对于八皇后问题的任何一个解而言，每一个皇后在棋

12、盘上的位置无任何规律，不具有系统性，而更像是随机放置的。由此想到拉斯维加斯型概率算法：在棋盘上相继的各行中随机地放置皇后，并使新放置的皇后与已放置的皇后互不攻击，直至八个皇后均已相容地放置好，或下一个皇后没有可放置的位置。,由于棋盘的每一行上可以而且必须放置一个皇后，所以八皇后问题的可能解用一个向量X=(x1, x2, , x8)表示，其中，1xi8并且1i8，即第i个皇后放置在第i行第xi列上。由于两个皇后不能位于同一列上，所以，解向量X必须满足约束条件： xixj （式10.2） 若两个皇后摆放的位置分别是(i, xi)和(j, xj)，在棋盘上斜率为-1的斜线上，满足条件i-j= xi-

13、xj，在棋盘上斜率为1的斜线上，满足条件ij= xixj，综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足约束条件： |i-xi|j-xj| （式10.3） 满足式10.2和式10.3的向量X=(x1, x2, , xi)表示已放置的i个皇后（1i8）互不攻击，也就是不发生冲突。,拉斯维加斯型概率算法通过反复调用算法10.5，直至得到八皇后问题的一个解。,如果将上述随机放置策略与回溯法相结合，则会获得更好的效果。可以先在棋盘的若干行中随机地放置相容的皇后，然后在其他行中用回溯法继续放置，直至找到一个解或宣告失败。 在棋盘中随机放置的皇后越多，回溯法搜索所需的时间就越少，但失

14、败的概率也就越大。 例如八皇后问题，随机地放置两个皇后再采用回溯法比完全采用回溯法快大约两倍；随机地放置三个皇后再采用回溯法比完全采用回溯法快大约一倍；而所有的皇后都随机放置比完全采用回溯法慢大约一倍。 很容易解释这个现象：不能忽略产生随机数所需的时间，当随机放置所有的皇后时，八皇后问题的求解大约有70%的时间都用在了产生随机数上。,10.3.2 整数因子分解问题,设n是正整数且n1，整数n的因子分解问题是找出n的如下形式的惟一分解式： 其中，p1p2pk是素数，m1, m2, , mk是正整数。如果n是一个合数，则n必有一个非平凡因子m（1mn），使得m可以整除n。给定一个合数n，求n的一个

15、非平凡因子的问题称为整数因子划分问题。,整数因子分解问题可以归结为整数因子划分和素数测试：假设对整数n进行因子分解，首先进行素数测试，如果n是素数，则分解完成；否则，再进行因子划分，找到n的一个非平凡因子m，并递归地对m和n/m进行因子分解。 下面讨论整数因子划分问题。,对一个正整数n进行因子划分的最自然的想法是试除，它可以找到n的最小素数因子。,算法Factor是对范围在1 的所有整数进行了试除而得到了n的最小素数因子，其时间复杂性是O( )。对于一个正整数n，其位数为 ，则算法Factor的时间复杂性是O(10m/2)。假定每次循环只需要1纳秒，它也需要花费1 000年的时间来分解一个40

16、位左右的坚固的（Hard）合数。 “坚固的”合数是指这个数是两个规模相当的素数的乘积。 到目前为止，还没有找到求解整数因子划分问题的多项式时间算法。,求解整数因子划分问题的拉斯维加斯型概率算法在开始时选取0n-1范围内的随机数x1，然后递归地由下式产生无穷序列x1, x2, , xk, 。 对于i=2k（k=0, 1, 2, ），以及2kj2k+1，计算xj-xi与n的最大公因子d，如果d大于1，则d即是n的非平凡因子，算法实现对n的一次划分。 计算xj-xi与n的最大公因子可以采用欧几里德算法，具体算法如下：,算法Pollard中的while循环执行约 次后，会得到n的一个素数因子p。由于n

17、的最小素数因子 ，故算法Pollard可在O(n1/4)的时间内找到n的一个素数因子。,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, 3, 2, 3, 3, 5中，元素3就是主元素。,蒙特卡罗型概率算法求解主元素问题可以随机地选择数组中的一个元素Ti进行统计，如果该元素出现的次数大于n/2，则该元素就是数组的主元素，算法返回tr

18、ue；否则随机选择的这个元素Ti不是主元素，算法返回false。此时，数组中可能有主元素也可能没有主元素。如果数组中存在主元素，则非主元素的个数小于n/2。因此，算法将以大于1/2的概率返回true，以小于1/2的概率返回false，这说明算法出现错误的概率小于1/2。如果连续运行算法k次，算法返回false的概率将减少为2-k，则算法发生错误的概率为2-k。,对于任何给定的0，算法MajorityMC重复调用log2(1/) 次算法Majority，其错误概率小于，时间复杂性显然是O(nlog2(1/ )。,10.4.2 素数测试问题,测试一个整数n是否是素数，最简单的方法是把这个数除以2

19、的数，如果余数为0，则n是一个合数，否则，n就是一个素数。,算法10.9的时间复杂性是O( )。对于一个正整数n，其位数为 ，则算法Factor的时间复杂性是O(10m/2)，因此，这个算法的时间复杂性是指数阶的。 费尔马定理 如果n是一个素数，a为正整数且0an，则an-1 mod n1。 费尔马定理表明，如果存在一个小于n的正整数a，使得an-1 mod n1，则n肯定不是素数。,费尔马定理只是素数判定的一个必要条件，有些合数也满足费尔马定理，这些合数被称作Carmichael数。Carmichael数是非常少的，在1100,000,000范围内的整数中，只有255个Carmichael数

20、。为了提高素数测试的准确性，可以多次随机选取小于n的正整数a，重复计算dan-1 mod n来判定n是否是素数。 例如，对于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; /可能是素数或Carmicha

21、el数 else return false; /一定不是素数 ,算法Prime1返回false时，整数n一定是一个合数，如果算法Prime1返回true，说明正整数n可能是素数，还可能是Carmichael数。但是，这个简单的测试却很少给出错误的结果。当一个合数n对于整数a满足费尔马定理时，称整数a为合数n的伪证据（Pseudowitness）。所以，只有在选取到一个伪证据时，Fermat测试的结论才是错误的。 幸运的是伪证据相当少。在小于1000的332个合数中只有5个没有伪证据，超过一半的合数只有两个伪证据，超过15个伪证据的合数不超过160个。如果考虑更大的数，这个概率会更小。,但是，有些合数的伪证据比例相当高，在小于1000的合数中，情况最坏的是561，它有318个伪证据。最坏的一个例子是一个15位的合数651,693,055,693,681，它以大于99.965的概率返回true，尽管这个数确实是合数！此时，通过之前采用的技巧，将算法Prime1重复任意次数，都不能将误差概率减少到任意小的内。 可以利用下面的二次探测定理对上面的Fermat测试