第10章 概率算法(完).ppt

1、第10章 概率算法,2020/8/2,第10章 概率算法,Page 2,10.1 概 述,10.2 舍伍德(Sherwood)型概率算法,10.3 拉斯维加斯(Las Vegas)型概率算法,10.4 蒙特卡罗(Monte Carlo)型概率算法,10.5 实验项目随机数发生器,第10章 概率算法,2020/8/2,第10章 概率算法,Page 3,10.1.1 概率算法的设计思想,10.1.2 随机数发生器,10.1 概 述,2020/8/2,第10章 概率算法,Page 4,概率算法把“对于所有合理的输入都必须给出正确的输出”这一求解问题的条件放宽，把随机性的选择注入到算法中，在算法执行某

2、些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少。,10.1.1 概率算法的设计思想,2020/8/2,第10章 概率算法,Page 5,例如，判断表达式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)比较特殊，如果这样重复几次，继续得

3、到f(r1, r2, , rn)0的结果，那么就可以得出f(x1, x2, , xn)恒等于0的结论，并且测试的随机向量越多，这个结果出错的可能性就越小。,2020/8/2,第10章 概率算法,Page 6,一般情况下，概率算法具有以下基本特征： （1）概率算法的输入包括两部分，一部分是原问题的输入，另一部分是一个供算法进行随机选择的随机数序列； （2）概率算法在运行过程中，包括一处或若干处随机选择，根据随机值来决定算法的运行； （3）概率算法的结果不能保证一定是正确的，但可以限定其出错概率； （4）概率算法在不同的运行中，对于相同的输入实例可以有不同的结果，因此，对于相同的输入实例，概率算法

4、的执行时间可能不同。,2020/8/2,第10章 概率算法,Page 7,对于确定性算法，通常分析在平均情况下以及最坏情况下的时间复杂性。对于概率算法，通常分析在平均情况下以及最坏情况下的期望时间复杂性，即由概率算法反复运行同一输入实例所得的平均运行时间。,概率算法的时间性能,需要强调的是，“随机”并不意味着“随意”。,2020/8/2,第10章 概率算法,Page 8,目前，在计算机上产生随机数还是一个难题，因为在原理上，这个问题只能近似解决。 计算机中产生随机数的方法通常采用线性同余法，产生的随机数序列为a0, a1, , an，满足： （式10.1） 其中，b0，c0，m0，dm。d称为

5、随机数发生器的随机种子（Random Seed），当b、c和m的值确定后，给定一个随机种子，由式10.1产生的随机数序列也就确定了。,10.1.2 随机数发生器,2020/8/2,第10章 概率算法,Page 9,计算机语言提供的随机数发生器，一般会需要一个随机种子，这个随机种子可以是系统当前的日期或时间。下面给出利用C+语言中的随机函数rand产生的分布在任意区间a, b)上的随机数算法。,2020/8/2,第10章 概率算法,Page 10,10.2.1 快速排序,10.2.2 选择问题,10.2 舍伍德(Sherwood)型概率算法,2020/8/2,第10章 概率算法,Page 11,

6、舍伍德(Sherwood)型概率算法,分析确定性算法在平均情况下的时间复杂性时，通常假定算法的输入实例满足某一特定的概率分布。 事实上，很多算法对于不同的输入实例，其运行时间差别很大。 例如快速排序算法，若输入实例是等概率均匀分布，其时间复杂性是O(nlog2n)，若输入实例基本有序，其时间复杂度是O(n2)。 因此，可以采用舍伍德型概率算法来消除算法的时间复杂性与输入实例间的这种联系。,2020/8/2,第10章 概率算法,Page 12,如果一个确定性算法无法直接改造成舍伍德型概率算法，可借助于随机预处理技术，即不改变原有的确定性算法，仅对其输入实例随机排列（称为洗牌）。假设输入实例为整型

7、，下面的随机洗牌算法可在线性时间实现对输入实例的随机排列。,2020/8/2,第10章 概率算法,Page 13,舍伍德型概率算法总能求得问题的一个解，并且所求得的解总是正确的。但与其相对应的确定性算法相比，舍伍德型概率算法的平均时间复杂性没有改进。换言之，舍伍德型概率算法不是避免算法的最坏情况行为，而是设法消除了算法的不同输入实例对算法时间性能的影响，对所有输入实例而言，舍伍德型概率算法的运行时间相对比较均匀，其时间复杂性与原有的确定性算法在平均情况下的时间复杂性相当。,2020/8/2,第10章 概率算法,Page 14,快速排序算法的关键在于一次划分中选择合适的轴值作为划分的基准，如果轴

8、值是序列中最小（或最大）记录，则一次划分后，由轴值分割得到的两个子序列不均衡，使得快速排序的时间性能降低。,10.2.1 快速排序,2020/8/2,第10章 概率算法,Page 15,舍伍德型概率算法在一次划分之前，根据随机数在待划分序列中随机确定一个记录作为轴值，并把它与第一个记录交换，则一次划分后得到期望均衡的两个子序列，从而使算法的行为不受待排序序列的不同输入实例的影响，使快速排序在最坏情况下的时间性能趋近于平均情况的时间性能。,10.2.1 快速排序,2020/8/2,第10章 概率算法,Page 16,一次划分结果 6 13 192331 35 28,初始键值序列 6 13 19

9、23 31 35 58,图10.1 一次划分引入随机选择的示例,一次划分结果 613 19 23 31 35 58,初始键值序列 6 13 19 23 31 35 58,随机选择一个 23 13 19 6 31 35 58 记录与6交换,(a) 以最小值6为轴值，划分不均衡,(b) 随机选择轴值，划分均衡,2020/8/2,第10章 概率算法,Page 17,2020/8/2,第10章 概率算法,Page 18,一次划分算法Partition与4.3.2节中相同。算法10.3在最坏情况下的时间复杂性仍是O(n2)，这是由于最坏情况下，随机数发生器在第i次随机产生的轴值记录恰好都是序列中第i小（

10、或第i大）记录。但是，作为随机数发生器，这种情况的出现概率是微乎其微的。事实上，输入记录的任何排列，都不可能出现使算法行为处于最坏的情况。因此，该算法的期望时间复杂性是O(nlog2n)。,2020/8/2,第10章 概率算法,Page 19,设无序序列T=(r1, r2, , rn)，T的第k（1kn）小元素定义为T按升序排列后在第k个位置上的元素。给定一个序列T和一个整数k，寻找T的第k小元素的问题称为选择问题。特别地，将寻找第n/2小元素的问题称为中值问题。,10.2.2 选择问题,2020/8/2,第10章 概率算法,Page 20,考虑快速排序中的划分过程，选定一个轴值将序列rirj

11、进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是s，则： （1）若k=s，则rs就是第k小元素； （2）若ks，则第k小元素一定在序列rs+1rj中；,2020/8/2,第10章 概率算法,Page 21,舍伍德型概率算法在一次划分之前，根据随机数在待划分序列中随机确定一个记录作为轴值，并把它与第一个记录交换，则一次划分后得到期望均衡的两个子序列，使得选择问题在最坏情况下的时间性能趋近于平均情况的时间性能。,2020/8/2,第10章 概率算法,Page 22,10.3.1 八皇后问题,10.3 拉斯维加斯(Las Vegas)型概率算法,20

12、20/8/2,第10章 概率算法,Page 23,拉斯维加斯(Las Vegas)型概率算法,拉斯维加斯型概率算法不时地做出可能导致算法陷入僵局的选择，并且算法能够检测是否陷入僵局，如果是，算法就承认失败。这种行为对于一个确定性算法是不能接受的，因为这意味着它不能解决相应的问题实例。但是，拉斯维加斯型概率算法的随机特性可以接受失败，只要这种行为出现的概率不占多数。当出现失败时，只要在相同的输入实例上再次运行概率算法，就又有成功的可能。,2020/8/2,第10章 概率算法,Page 24,拉斯维加斯型概率算法的一个显著特征是，它所做的随机性选择有可能导致算法找不到问题的解，即算法运行一次，或者

13、得到一个正确的解，或者无解。因此，需要对同一输入实例反复多次运行算法，直到成功地获得问题的解。 由于拉斯维加斯型概率算法有时运行成功，有时运行失败，因此，通常拉斯维加斯型概率算法的返回类型为bool，并且有两个参数：一个是算法的输入，另一个是当算法运行成功时保存问题的解。当算法运行失败时，可对同一输入实例再次运行，直到成功地获得问题的解。,2020/8/2,第10章 概率算法,Page 25,拉斯维加斯型概率算法的一般形式 void Obstinate(input x, solution y) success=false; while (!success) success=LV(x, y);

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

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

16、 xixj （式10.2） 若两个皇后摆放的位置分别是(i, xi)和(j, xj)，在棋盘上斜率为-1的斜线上，满足条件i-j= xi-xj，在棋盘上斜率为1的斜线上，满足条件ij= xixj，综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足约束条件： |i-xi|j-xj| （式10.3） 满足式10.2和式10.3的向量X=(x1, x2, , xi)表示已放置的i个皇后（1i8）互不攻击，也就是不发生冲突。,2020/8/2,第10章 概率算法,Page 29,拉斯维加斯型概率算法通过反复调用算法10.5，直至得到八皇后问题的一个解。,2020/8/2,第10章 概

17、率算法,Page 30,如果将上述随机放置策略与回溯法相结合，则会获得更好的效果。可以先在棋盘的若干行中随机地放置相容的皇后，然后在其他行中用回溯法继续放置，直至找到一个解或宣告失败。 在棋盘中随机放置的皇后越多，回溯法搜索所需的时间就越少，但失败的概率也就越大。 例如八皇后问题，随机地放置两个皇后再采用回溯法比完全采用回溯法快大约两倍；随机地放置三个皇后再采用回溯法比完全采用回溯法快大约一倍；而所有的皇后都随机放置比完全采用回溯法慢大约一倍。 很容易解释这个现象：不能忽略产生随机数所需的时间，当随机放置所有的皇后时，八皇后问题的求解大约有70%的时间都用在了产生随机数上。,2020/8/2,第10章 概率算法,Page 31,10.4.1 主元素问题,10.4 蒙特卡罗(Monte Carlo)型概率算法,2020/8/2,第10章 概率算法,Page 32,设Tn是一个含有n个元素的数组，x是数组T的一个元素，如果数组中有一半以上的元素与x相同，则称元素x是数组T的主元素（Major Element）。 例如，在数组T7=3, 2, 3, 2, 3, 3, 5中，元素3就是主元素。,10.4.1 主元素问题,2020/8/2,第10章 概率算法,Page 33,蒙