第12章 概率算法

1、算法设计与分析算法设计与分析清华大学出版社清华大学出版社第第12章章 概率算法概率算法 12.1 概概 述述 12.2 舍伍德舍伍德(Sherwood)型概率算法型概率算法12.3 拉斯维加斯拉斯维加斯(Las Vegas)型概率算法型概率算法12.4 蒙特卡罗蒙特卡罗(Monte Carlo)型概率算法型概率算法12.5 实验项目实验项目随机数发生器随机数发生器算法设计与分析算法设计与分析清华大学出版社清华大学出版社12.1 概概 述述 前面讨论的算法都是针对确定性算法，即算前面讨论的算法都是针对确定性算法，即算法的每一步都明确指定下一步该如何进行，对于任法的每一步都明确指定下一步该如何进行

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

3、想解读藏宝图要解读藏宝图要4天，不允许出发后解读；天，不允许出发后解读；另外一个人每天会拿走一部分宝藏；另外一个人每天会拿走一部分宝藏；有一个小精灵可告诉你如何解读，但需支付相有一个小精灵可告诉你如何解读，但需支付相当于那个人当于那个人3天拿走的宝藏。天拿走的宝藏。问题：如何做才能得到更多的宝藏？问题：如何做才能得到更多的宝藏？5天5天5天算法设计与分析算法设计与分析清华大学出版社清华大学出版社12.1.1 概率算法的设计思想概率算法的设计思想假设得到藏宝图时剩余宝藏价值是假设得到藏宝图时剩余宝藏价值是x，知道藏宝地点的，知道藏宝地点的那个人每天拿走宝藏价值是那个人每天拿走宝藏价值是y，并且，

4、并且x9y，可行方案有：，可行方案有：用用4天时间解读藏宝图，用天时间解读藏宝图，用5天时间到达藏宝地点，可获天时间到达藏宝地点，可获得宝藏价值得宝藏价值x-9y;接受小精灵的条件，用接受小精灵的条件，用5天时间到达藏宝地点，并支付天时间到达藏宝地点，并支付给小精灵宝藏价值给小精灵宝藏价值3y，则可获宝藏价值，则可获宝藏价值x-5y-3y=x-8y;投掷硬币决定首先前往哪个地点，如果发现地点是错的，投掷硬币决定首先前往哪个地点，如果发现地点是错的，就前往另一个地点。这样有一半的机会获得宝藏价值就前往另一个地点。这样有一半的机会获得宝藏价值x-5y，另一半机会获得宝藏价值，另一半机会获得宝藏价值

5、x-10y，这样最终可获宝，这样最终可获宝藏价值是藏价值是x-7.5y。当面临选择时，当面临选择时，如计算正确选择的时间大于随机确定一个选择的时间，如计算正确选择的时间大于随机确定一个选择的时间，那么应该随机选择一个那么应该随机选择一个。当算法执行过程中面临一个选择，有时候。当算法执行过程中面临一个选择，有时候随机选择算法的执行动作可能比花费时间计算哪个是最优选择更好。随机选择算法的执行动作可能比花费时间计算哪个是最优选择更好。算法设计与分析算法设计与分析清华大学出版社清华大学出版社12.1.1 概率算法的设计思想概率算法的设计思想 概率算法把概率算法把“对于所有合理的输入都必须给出对于所有合

6、理的输入都必须给出正确的输出正确的输出”这一求解问题的条件放宽，把这一求解问题的条件放宽，把随机性的随机性的选择选择注入到算法中，在算法执行某些步骤时，可以随注入到算法中，在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许机地选择下一步该如何进行，同时允许结果以较小的结果以较小的概率出现错误概率出现错误，并以此为代价，获得算法运行时间的，并以此为代价，获得算法运行时间的大幅度减少。大幅度减少。如果一个问题没有有效的确定性算法可以在一如果一个问题没有有效的确定性算法可以在一个合理的时间内求解，但是该问题个合理的时间内求解，但是该问题能接受小概率的错能接受小概率的错误误，那么采用概率算

7、法就可以快速找到问题的解。，那么采用概率算法就可以快速找到问题的解。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 例如，判断表达式例如，判断表达式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)

8、比较特殊，如果这样重复几次，继续得到比较特殊，如果这样重复几次，继续得到f(r1, r2, , rn)0的结果，那么就可以得出的结果，那么就可以得出f(x1, x2, , xn)恒等于恒等于0的结论，并且测试的随机向量越多，这个结果出错的结论，并且测试的随机向量越多，这个结果出错的可能性就越小。的可能性就越小。算法设计与分析算法设计与分析清华大学出版社清华大学出版社一般情况下，概率算法具有以下基本特征：一般情况下，概率算法具有以下基本特征：（1）概率算法的输入包括）概率算法的输入包括两部分两部分，一部分是，一部分是原问题原问题的输入的输入，另一部分是一个供算法进行随机选择的，另一部分是一个供算

9、法进行随机选择的随随机数序列机数序列；（2）概率算法在运行过程中，包括一处或若干处）概率算法在运行过程中，包括一处或若干处随随机选择机选择，根据随机值来决定算法的运行；，根据随机值来决定算法的运行；（3）概率算法的结果）概率算法的结果不能保证一定是正确不能保证一定是正确的，但可的，但可以限定其以限定其出错概率出错概率；（4）概率算法在不同的运行中，对于相同的输入实）概率算法在不同的运行中，对于相同的输入实例可以有例可以有不同的结果不同的结果，因此，对于相同的输入实例，因此，对于相同的输入实例，概率算法的概率算法的执行执行时间可能不同时间可能不同。同一输入实例运行同一概率算法求解两次可能得到完同

10、一输入实例运行同一概率算法求解两次可能得到完全不同的效果（结果和所需时间），所以一旦概率算法失败全不同的效果（结果和所需时间），所以一旦概率算法失败了，只需了，只需重启算法重启算法又有成功的希望。另外运行几次概率算法，又有成功的希望。另外运行几次概率算法，有可能得到几个不同的答案。有可能得到几个不同的答案。算法设计与分析算法设计与分析清华大学出版社清华大学出版社 对于确定性算法，通常分析在平均情况下以对于确定性算法，通常分析在平均情况下以及最坏情况下的时间复杂性。对于概率算法，通及最坏情况下的时间复杂性。对于概率算法，通常分析在平均情况下以及最坏情况下的常分析在平均情况下以及最坏情况下的期望期

11、望时间时间复杂性，即由概率算法反复运行同一输入实例所复杂性，即由概率算法反复运行同一输入实例所得的平均运行时间。得的平均运行时间。 概率算法的时间性能概率算法的时间性能v需要强调的是，需要强调的是，“随机随机”并不意味着并不意味着“随意随意”。如手工运行。如手工运行算法，可通过掷骰子来得到一个随机结果，在计算机中则通算法，可通过掷骰子来得到一个随机结果，在计算机中则通过随机数发生器来实现。过随机数发生器来实现。算法设计与分析算法设计与分析清华大学出版社清华大学出版社11.1.2 随机数发生器随机数发生器 目前，在计算机上产生随机数还是一个难题，因为在目前，在计算机上产生随机数还是一个难题，因为

12、在原理上，这个问题只能近似解决。原理上，这个问题只能近似解决。 计算机中产生随机数的方法通常采用线性同余法，产计算机中产生随机数的方法通常采用线性同余法，产生的随机数序列为生的随机数序列为a0, a1, , an，满足：，满足： （式（式12.1） 其中，其中，b0，c0，m0，dm。d称为随机数发生器的称为随机数发生器的随机种子（随机种子（Random Seed），当），当b、c和和m的值确定后，给定的值确定后，给定一个随机种子，由式一个随机种子，由式12.1产生的随机数序列也就确定了。产生的随机数序列也就确定了。, 2 , 1mod)(10nmcbaadann算法设计与分析算法设计与分析清

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

14、(0, 32767)之间的随机整数 C+描述算法设计与分析算法设计与分析清华大学出版社清华大学出版社12.2 舍伍德舍伍德(Sherwood)型概率算法型概率算法 分析确定性算法在平均情况下的时间复杂性分析确定性算法在平均情况下的时间复杂性时，通常假定算法的输入实例满足某一特定的概时，通常假定算法的输入实例满足某一特定的概率分布。率分布。 事实上，很多算法对于不同的输入实例，其事实上，很多算法对于不同的输入实例，其运行时间差别很大。此时，可以采用舍伍德型概运行时间差别很大。此时，可以采用舍伍德型概率算法来率算法来消除消除算法的时间复杂性与输入实例间的算法的时间复杂性与输入实例间的这种联系。这种

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

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

17、能的影响实例对算法时间性能的影响，对所有输入实例而言，对所有输入实例而言，舍伍德型概率算法的运行时间相对比较均匀，其时舍伍德型概率算法的运行时间相对比较均匀，其时间复杂性与原有的确定性算法在平均情况下的时间间复杂性与原有的确定性算法在平均情况下的时间复杂性相当。复杂性相当。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社12.2.1 快速排序快速排序 快速排序算法的关键在于一次划分中选择合适快速排序算法的关键在于一次划分中选择合适的轴值作为划分的基准，如果轴值是序列中最小的轴值作为划分的基准，如果轴值是序列中最小（或最大）记录，则一次划分后，由轴值分割得到（或最大）记录，则一次划分后

18、，由轴值分割得到的两个子序列不均衡，使得快速排序的时间性能降的两个子序列不均衡，使得快速排序的时间性能降低。低。舍伍德型概率算法在一次划分之前，根据舍伍德型概率算法在一次划分之前，根据随随机数机数在待划分序列中随机确定一个记录作为轴值，在待划分序列中随机确定一个记录作为轴值，并把它与第一个记录交换，则一次划分后得到期望并把它与第一个记录交换，则一次划分后得到期望均衡的两个子序列，从而使算法的行为不受待排序均衡的两个子序列，从而使算法的行为不受待排序序列的不同输入实例的影响，序列的不同输入实例的影响，使快速排序在最坏情使快速排序在最坏情况下的时间性能趋近于平均情况的时间性能况下的时间性能趋近于平

19、均情况的时间性能。算法设计与分析算法设计与分析清华大学出版社清华大学出版社一次划分结果一次划分结果 6 13 192331 35 28初始键值序列初始键值序列 6 13 19 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) 随机选择轴值，划分均衡随机选择轴值，划分均衡算法设计与

20、分析算法设计与分析清华大学出版社清华大学出版社算法算法12.3随机随机快速排序快速排序 void QuickSort (int r , int low, int high) if (low0。在更强的意义下，要求存在一个正的常数。在更强的意义下，要求存在一个正的常数，使得对于所有的输入实例，使得对于所有的输入实例x均有均有p(x)。由于。由于p(x)，所以，只要有足够的时间，对任何输入实，所以，只要有足够的时间，对任何输入实例例x，拉斯维加斯型概率算法总能找到问题的一个，拉斯维加斯型概率算法总能找到问题的一个解。换言之，拉斯维加斯型概率算法找到正确解的解。换言之，拉斯维加斯型概率算法找到正确解

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

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

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

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

25、，进行第count次试探；次试探； 2.3 若皇后若皇后i放置在位置放置在位置j不发生冲突，不发生冲突， 则则xi=j；count=0；转步骤；转步骤2放置下一个皇后；放置下一个皇后； 2.4 若若(count= =8)，则无法放置皇后，则无法放置皇后i，算法运行失败；，算法运行失败； 否则，转步骤否则，转步骤2.1重新放置皇后重新放置皇后i； 3. 将元素将元素x1x8作为八皇后问题的一个解输出；作为八皇后问题的一个解输出； 拉斯维加斯型概率算法通过反复调用算法拉斯维加斯型概率算法通过反复调用算法12.5，直至得到八皇后问题的一个解。直至得到八皇后问题的一个解。算法设计与分析算法设计与分析清

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

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

28、罗蒙特卡罗(Monte Carlo)型概率算法型概率算法 对于许多问题来说，近似解毫无意义。如布对于许多问题来说，近似解毫无意义。如布尔型的解，或象整数因子划分问题的解必须是准尔型的解，或象整数因子划分问题的解必须是准确的。蒙特卡罗型概率算法用于求问题的准确解。确的。蒙特卡罗型概率算法用于求问题的准确解。 因为属于概率算法，该算法偶尔也会出错，因为属于概率算法，该算法偶尔也会出错，但无论任何输入实例，总能以很高的概率找到一但无论任何输入实例，总能以很高的概率找到一个正确解。求得正确解的概率依赖于算法所用的个正确解。求得正确解的概率依赖于算法所用的时间，所用的时间越多，得到正确解的概率就越时间，

29、所用的时间越多，得到正确解的概率就越高。高。算法设计与分析算法设计与分析清华大学出版社清华大学出版社12.4 蒙特卡罗蒙特卡罗(Monte Carlo)型概率算法型概率算法蒙特卡罗型概率算法是蒙特卡罗型概率算法是P正确：如果该算法对于问正确：如果该算法对于问题的任一输入实例得到正确解的概率不小于题的任一输入实例得到正确解的概率不小于P（P是属于是属于(1/2, 1)间的实数）。间的实数）。蒙特卡罗型概率算法是一致：如果对于同一输入蒙特卡罗型概率算法是一致：如果对于同一输入实例，该算法不会给出两个不同的正确解。实例，该算法不会给出两个不同的正确解。蒙特卡罗型概率算法的参数除了问题输入实例蒙特卡罗

30、型概率算法的参数除了问题输入实例I外，外，还有描述错误解可接受概率的参数，其时间复杂还有描述错误解可接受概率的参数，其时间复杂性由函数性由函数T(n, )描述。描述。算法设计与分析算法设计与分析清华大学出版社清华大学出版社12.4.1 主元素问题主元素问题 设设Tn是一个含有是一个含有n个元素的数组，个元素的数组，x是数组是数组T的的一个元素，如果数组中有一个元素，如果数组中有一半以上一半以上的元素与的元素与x相同，相同，则称元素则称元素x是数组是数组T的主元素（的主元素（Major Element）。）。例如，在数组例如，在数组T7=3, 2, 3, 2, 3, 3, 5中，元素中，元素3就是主就是主元素。元素。求解主元素的简单方法是统计每个元素在数组中出现求解主元素的简