算法设计与分析王红梅第二版第12章概率算法.

算法设计与分析清华大学出版社第12章概率算法12.1概述12.2舍伍德(Sherwood)型概率算法12.3拉斯维加斯(LasVegas)型概率算法12.4蒙特卡罗(MonteCarlo)型概率算法12.5实验项目——随机数发生器算法设计与分析清华大学出版社12.1概述前面讨论的算法都是针对确定性算法，即算法的每一步都明确指定下一步该如何进行，对于任何合理的输入，确定性算法都必须给出正确的输出。概率算法把“对于所有合理的输入都必须给出正确的输出”这一求解问题的条件放宽，允许算法在执行过程中随机选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少。算法设计与分析清华大学出版社12.1.1概率算法的设计思想•解读藏宝图要4天，不允许出发后解读；•另外一个人每天会拿走一部分宝藏；•有一个小精灵可告诉你如何解读，但需支付相当于那个人3天拿走的宝藏。问题：如何做才能得到更多的宝藏？5天5天5天算法设计与分析清华大学出版社12.1.1概率算法的设计思想假设得到藏宝图时剩余宝藏价值是x，知道藏宝地点的那个人每天拿走宝藏价值是y，并且x9y，可行方案有：1.用4天时间解读藏宝图，用5天时间到达藏宝地点，可获得宝藏价值x-9y;2.接受小精灵的条件，用5天时间到达藏宝地点，并支付给小精灵宝藏价值3y，则可获宝藏价值x-5y-3y=x-8y;3.投掷硬币决定首先前往哪个地点，如果发现地点是错的，就前往另一个地点。这样有一半的机会获得宝藏价值x-5y，另一半机会获得宝藏价值x-10y，这样最终可获宝藏价值是x-7.5y。当面临选择时，如计算正确选择的时间大于随机确定一个选择的时间，那么应该随机选择一个。当算法执行过程中面临一个选择，有时候随机选择算法的执行动作可能比花费时间计算哪个是最优选择更好。算法设计与分析清华大学出版社12.1.1概率算法的设计思想概率算法把“对于所有合理的输入都必须给出正确的输出”这一求解问题的条件放宽，把随机性的选择注入到算法中，在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少。如果一个问题没有有效的确定性算法可以在一个合理的时间内求解，但是该问题能接受小概率的错误，那么采用概率算法就可以快速找到问题的解。算法设计与分析清华大学出版社例如，判断表达式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,…,xn)恒等于0的结论，并且测试的随机向量越多，这个结果出错的可能性就越小。算法设计与分析清华大学出版社一般情况下，概率算法具有以下基本特征：（1）概率算法的输入包括两部分，一部分是原问题的输入，另一部分是一个供算法进行随机选择的随机数序列；（2）概率算法在运行过程中，包括一处或若干处随机选择，根据随机值来决定算法的运行；（3）概率算法的结果不能保证一定是正确的，但可以限定其出错概率；（4）概率算法在不同的运行中，对于相同的输入实例可以有不同的结果，因此，对于相同的输入实例，概率算法的执行时间可能不同。同一输入实例运行同一概率算法求解两次可能得到完全不同的效果（结果和所需时间），所以一旦概率算法失败了，只需重启算法又有成功的希望。另外运行几次概率算法，有可能得到几个不同的答案。算法设计与分析清华大学出版社对于确定性算法，通常分析在平均情况下以及最坏情况下的时间复杂性。对于概率算法，通常分析在平均情况下以及最坏情况下的期望时间复杂性，即由概率算法反复运行同一输入实例所得的平均运行时间。概率算法的时间性能需要强调的是，“随机”并不意味着“随意”。如手工运行算法，可通过掷骰子来得到一个随机结果，在计算机中则通过随机数发生器来实现。算法设计与分析清华大学出版社11.1.2随机数发生器目前，在计算机上产生随机数还是一个难题，因为在原理上，这个问题只能近似解决。计算机中产生随机数的方法通常采用线性同余法，产生的随机数序列为a0,a1,…,an，满足：（式12.1）其中，b≥0，c≥0，m＞0，d≤m。d称为随机数发生器的随机种子（RandomSeed），当b、c和m的值确定后，给定一个随机种子，由式12.1产生的随机数序列也就确定了。,2,1mod)(10nmcbaadann算法设计与分析清华大学出版社计算机语言提供的随机数发生器，一般会输出一个分布在开区间（0,1）上的随机小数，并且需要一个随机种子，这个随机种子可以是系统当前的日期或时间。下面给出利用C++语言中的随机函数rand产生的分布在任意区间[a,b]上的随机数算法。算法12.1——随机数发生器intRandom(inta,intb){returnrand()%(b-a)+a;//rand()产生(0,32767)之间的随机整数}算法设计与分析清华大学出版社12.2舍伍德(Sherwood)型概率算法分析确定性算法在平均情况下的时间复杂性时，通常假定算法的输入实例满足某一特定的概率分布。事实上，很多算法对于不同的输入实例，其运行时间差别很大。此时，可以采用舍伍德型概率算法来消除算法的时间复杂性与输入实例间的这种联系。算法设计与分析清华大学出版社算法12.2——随机洗牌voidRandomShuffle(intn,intr[]){for(i=0;in;i++){j=Random(0,n-i-1);r[i]←→r[j];//交换r[i]和r[j]}}如果一个确定性算法无法直接改造成舍伍德型概率算法，可借助于随机预处理技术，即不改变原有的确定性算法，仅对其输入实例随机排列（称为洗牌）。假设输入实例为整型，下面的随机洗牌算法可在线性时间实现对输入实例的随机排列。算法设计与分析清华大学出版社舍伍德型概率算法总能求得问题的一个解，并且所求得的解总是正确的。但与其相对应的确定性算法相比，舍伍德型概率算法的平均时间复杂性没有改进。换言之，舍伍德型概率算法不是避免算法的最坏情况行为，而是设法消除了算法的不同输入实例对算法时间性能的影响，对所有输入实例而言，舍伍德型概率算法的运行时间相对比较均匀，其时间复杂性与原有的确定性算法在平均情况下的时间复杂性相当。算法设计与分析清华大学出版社12.2.1快速排序快速排序算法的关键在于一次划分中选择合适的轴值作为划分的基准，如果轴值是序列中最小（或最大）记录，则一次划分后，由轴值分割得到的两个子序列不均衡，使得快速排序的时间性能降低。舍伍德型概率算法在一次划分之前，根据随机数在待划分序列中随机确定一个记录作为轴值，并把它与第一个记录交换，则一次划分后得到期望均衡的两个子序列，从而使算法的行为不受待排序序列的不同输入实例的影响，使快速排序在最坏情况下的时间性能趋近于平均情况的时间性能。算法设计与分析清华大学出版社一次划分结果［61319］23［313528］初始键值序列6131923313558图10.1一次划分引入随机选择的示例一次划分结果6［131923313558］初始键值序列6131923313558随机选择一个2313196313558记录与6交换(a)以最小值6为轴值，划分不均衡(b)随机选择轴值，划分均衡算法设计与分析清华大学出版社算法12.3——随机快速排序voidQuickSort(intr[],intlow,inthigh){if(lowhigh){i=Random(low,high);r[low]←→r[i];k=Partition(r,low,high);QuickSort(r,low,k-1);QuickSort(r,k+1,high);}}算法设计与分析清华大学出版社一次划分算法Partition与4.3.2节中相同。算法12.3在最坏情况下的时间复杂性仍是O(n2)，这是由于随机数发生器在第i次随机产生的轴值记录恰好都是序列中第i小（或第i大）记录。但是，作为随机数发生器，这种情况的出现概率是微乎其微的。事实上，输入记录的任何排列，都不可能出现使算法行为处于最坏的情况。因此，该算法的期望时间复杂性是O(nlog2n)。算法设计与分析清华大学出版社12.3拉斯维加斯(LasVegas)型概率算法拉斯维加斯型概率算法不时地做出可能导致算法陷入僵局的选择，并且算法能够检测是否陷入僵局，如果是，算法就承认失败。这种行为对于一个确定性算法是不能接受的，因为这意味着它不能解决相应的问题实例。但是，拉斯维加斯型概率算法的随机特性可以接受失败，只要这种行为出现的概率不占多数。当出现失败时，只要在相同的输入实例上再次运行概率算法，就又有成功的可能。算法设计与分析清华大学出版社拉斯维加斯型概率算法的一个显著特征是，它所做的随机性选择有可能导致算法找不到问题的解，即算法运行一次，或者得到一个正确的解，或者无解。因此，需要对同一输入实例反复多次运行算法，直到成功地获得问题的解。由于拉斯维加斯型概率算法有时运行成功，有时运行失败，因此，通常拉斯维加斯型概率算法的返回类型为bool，并且有两个参数：一个是算法的输入，另一个是当算法运行成功时保存问题的解。当算法运行失败时，可对同一输入实例再次运行，直到成功地获得问题的解。算法设计与分析清华大学出版社拉斯维加斯型概率算法的一般形式voidObstinate(inputx,solutiony){success=false;while(!success)success=LV(x,y);}算法设计与分析清华大学出版社设p(x)是对输入实例x调用拉斯维加斯型概率算法获得问题的一个解的概率，则一个正确的拉斯维加斯型概率算法应该对于所有的输入实例x均有p(x)0。在更强的意义下，要求存在一个正的常数δ，使得对于所有的输入实例x均有p(x)δ。由于p(x)δ，所以，只要有足够的时间，对任何输入实例x，拉斯维加斯型概率算法总能找到问题的一个解。换言之，拉斯维加斯型概率算法找到正确解的概率随着计算时间的增加而提高。算法设计与分析清华大学出版社12.3.1八皇后问题八皇后问题是在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。对于八皇后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更像是随机放置的。由此想到拉斯维加斯型概率算法：在棋盘上相继的各行中随机地放置皇后，并使新放置的皇后与已放置的皇后互不攻击，直至八个皇后均已相容地放置好，或下一个皇后没有可放置的位置。算法设计与分析清华大学出版社由于棋盘的每一行上可以而且必须放置一个皇后，所以八皇后问题的可能解用一个向量X=(x1,x2,…,x8)表示，其中，1≤xi≤8并且1≤i≤8，即第i个皇后放置在第i行第xi列上。由于两个皇后不能位于同一列上，所以，解向量X必须满足约束条件：xi≠xj（式12.2）若两个皇后摆放的位置分别是(i,xi)和(j,xj)，在棋盘上斜率为-1的斜线上，满足条件i-j=xi-xj，在棋盘上斜率为1的斜线上，满足条件i＋j=xi＋xj，综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足约束条件：|i-xi|≠|j-xj|（式12.3）满足式12.2和式12.3的向量X=(x1,x2,…,xi)表示已放置的i个皇后（1≤i≤8）互不攻击，也就是不发生冲突。算法设计与分析清华大学出版社算法12.5——八皇后问题1.将数组x[8]初始化为0；试探次数count初始化为0；2．for(i=1;i=8;i++)2.1产生一个[1,8]的随机数j；2.2count=count+1，进行第count次试探；2.3若皇后i放置在位置j