第10章 概率算法(完)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第10章 概率算法,Page,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第10章 概率算法,Page,*,第,10,章 概率算法,2024/10/2,第10章 概率算法,Page,2,10.1,概 述,10.2,舍伍德,(Sherwood),型概率算法,10.3,拉斯维加斯,(Las Vegas),型概率算法,10.4,蒙特卡罗,(Monte Carlo),型概率算法,10.5,实验项目,随机数发生器,第,10,章 概率算法,2024/10/2,第10章 概率算法,Page,3,10.1.1,概率算法的设计思想,10.1.2,随机数发生器,10.1,概 述,2024/10/2,第10章 概率算法,Page,4,概率算法把“对于所有合理的输入都必须给出正确的输出”这一求解问题的条件放宽，把,随机性,的选择注入到算法中，在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以,较小的概率出现错误,，并以此为代价，获得算法运行时间的大幅度减少。,10.1.1,概率算法的设计思想,2024/10/2,第10章 概率算法,Page,5,例如，判断表达式,f,(,x,1,x,2, ,x,n,),是否恒等于,0,。,概率算法首先生成一个随机,n,元向量,(,r,1,r,2, ,r,n,),，并计算,f,(,r,1,r,2, ,r,n,),的值，如果,f,(,r,1,r,2, ,r,n,),0,，则,f,(,x,1,x,2, ,x,n,),0,；如果,f,(,r,1,r,2, ,r,n,),0,，则或者,f,(,x,1,x,2, ,x,n,),恒等于,0,，或者是,(,r,1,r,2, ,r,n,),比较特殊，如果这样重复几次，继续得到,f,(,r,1,r,2, ,r,n,),0,的结果，那么就可以得出,f,(,x,1,x,2, ,x,n,),恒等于,0,的结论，并且测试的随机向量越多，这个结果出错的可能性就越小。,2024/10/2,第10章 概率算法,Page,6,一般情况下，概率算法具有以下基本特征：,（,1,）概率算法的输入包括两部分，一部分是原问题的输入，另一部分是一个供算法进行随机选择的,随机数序列,；,（,2,）概率算法在运行过程中，包括一处或若干处,随机选择,，根据随机值来决定算法的运行；,（,3,）概率算法的结果,不能保证一定是正确,的，但可以限定其出错概率；,（,4,）概率算法在不同的运行中，对于相同的输入实例可以有不同的结果，因此，,对于相同的输入实例,，概率算法的,执行时间可能不同,。,2024/10/2,第10章 概率算法,Page,7,对于确定性算法，通常分析在平均情况下以及最坏情况下的时间复杂性。对于概率算法，通常分析在平均情况下以及最坏情况下的,期望,时间复杂性，即由概率算法反复运行同一输入实例所得的平均运行时间。,概率算法的时间性能,需要强调的是，,“,随机,”,并不意味着,“,随意,”,。,2024/10/2,第10章 概率算法,Page,8,目前，在计算机上产生随机数还是一个难题，因为在原理上，这个问题只能近似解决。,计算机中产生随机数的方法通常采用线性同余法，产生的随机数序列为,a,0,a,1, ,a,n,，满足：,（式,10.1,）,其中，,b,0,，,c,0,，,m,0,，,d,m,。,d,称为随机数发生器的随机种子（,Random Seed,），当,b,、,c,和,m,的值确定后，给定一个随机种子，由式,10.1,产生的随机数序列也就确定了。,10.1.2,随机数发生器,2024/10/2,第10章 概率算法,Page,9,计算机语言提供的随机数发生器，一般会需要一个随机种子，这个随机种子可以是系统当前的日期或时间。下面给出利用,C+,语言中的随机函数,rand,产生的分布在任意区间,a,b,),上的随机数算法。,算法,10.1,随机数发生器,int Random(int a, int b),return rand( )%(b,-,a)+a;,/rand( ),产生,a,b,),之间的随机整数,C+,描述,2024/10/2,第10章 概率算法,Page,10,10.2.1,快速排序,10.2.2,选择问题,10.2,舍伍德,(Sherwood),型概率算法,2024/10/2,第10章 概率算法,Page,11,舍伍德,(Sherwood),型概率算法,分析确定性算法在平均情况下的时间复杂性时，通常假定算法的输入实例满足某一特定的概率分布。,事实上，很多算法对于不同的输入实例，其运行时间差别很大。,例如快速排序算法，若输入实例是等概率均匀分布，其时间复杂性是,O,(,n,log,2,n,),，若输入实例基本有序，其时间复杂度是,O,(,n,2,),。,因此，可以采用舍伍德型概率算法来消除算法的时间复杂性与输入实例间的这种联系。,2024/10/2,第10章 概率算法,Page,12,算法,10.2,随机洗牌,void RandomShuffle(int n, int r ),for (i=0; in; i+),j=Random(0, n,-,i,-,1);,rirj; /,交换,ri,和,rj,C+,描述,如果一个确定性算法无法直接改造成舍伍德型概率算法，可借助于随机预处理技术，即,不改变原有的确定性算法，仅对其输入实例随机排列（称为洗牌）,。假设输入实例为整型，下面的随机洗牌算法可在线性时间实现对输入实例的随机排列。,2024/10/2,第10章 概率算法,Page,13,舍伍德型概率算法总能求得问题的一个解，并且所求得的解总是正确的。但与其相对应的确定性算法相比，舍伍德型概率算法的平均时间复杂性没有改进。换言之，舍伍德型概率算法不是避免算法的最坏情况行为，而是,设法消除了算法的不同输入实例对算法时间性能的影响,，,对所有输入实例而言，舍伍德型概率算法的运行时间相对比较均匀,，其时间复杂性与原有的确定性算法在平均情况下的时间复杂性相当。,2024/10/2,第10章 概率算法,Page,14,快速排序算法的关键在于一次划分中选择合适的轴值作为划分的基准，如果轴值是序列中最小（或最大）记录，则一次划分后，由轴值分割得到的两个子序列不均衡，使得快速排序的时间性能降低。,10.2.1,快速排序,2024/10/2,第10章 概率算法,Page,15,舍伍德型概率算法在一次划分之前，根据,随机数在待划分序列中随机确定一个记录作为轴值,，并把它与第一个记录交换，则一次划分后得到期望均衡的两个子序列，从而使算法的行为不受待排序序列的不同输入实例的影响，使快速排序在最坏情况下的时间性能趋近于平均情况的时间性能。,10.2.1,快速排序,2024/10/2,第10章 概率算法,Page,16,一次划分结果 ,6 13 19,23,31 35 28,初始键值序列,6 13 19 23 31 35 58,图,10.1,一次划分引入随机选择的示例,一次划分结果,6,13 19 23 31 35 58,初始键值序列,6 13 19 23 31 35 58,随机选择一个,23 13 19 6 31 35 58,记录与,6,交换,(a),以最小值,6,为轴值，划分不均衡,(b),随机选择轴值，划分均衡,2024/10/2,第10章 概率算法,Page,17,算法,10.3,随机快速排序,void QuickSort (int r , int low, int high),if (lowhigh) ,i=Random(low, high);,rlowri;,k=Partition(r, low, high);,QuickSort(r, low, k,-,1);,QuickSort(r, k+1, high);,C+,描述,2024/10/2,第10章 概率算法,Page,18,一次划分算法,Partition,与,4.3.2,节中相同。算法,10.3,在最坏情况下的时间复杂性仍是,O,(,n,2,),，这是由于最坏情况下，随机数发生器在第,i,次随机产生的轴值记录恰好都是序列中第,i,小（或第,i,大）记录。但是，作为随机数发生器，这种情况的出现概率是微乎其微的。事实上，输入记录的任何排列，都不可能出现使算法行为处于最坏的情况。因此，,该算法的期望时间复杂性是,O,(,n,log,2,n,),。,2024/10/2,第10章 概率算法,Page,19,设无序序列,T,=(,r,1,r,2, ,r,n,),，,T,的第,k,（,1,k,n,）小元素定义为,T,按升序排列后在第,k,个位置上的元素。给定一个序列,T,和一个整数,k,，寻找,T,的第,k,小元素的问题称为选择问题。特别地，将寻找第,n,/2,小元素的问题称为中值问题。,10.2.2,选择问题,2024/10/2,第10章 概率算法,Page,20,考虑快速排序中的划分过程，选定一个轴值将序列,r,i,r,j,进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是,s,，则：,（,1,）若,k,=,s,，则,r,s,就是第,k,小元素；,（,2,）若,k,s,，则第,k,小元素一定在序列,r,s,+1,r,j,中；,r,i,r,k,r,s,-1,r,s,r,s,+1, ,r,j,均,r,s,轴值 均,r,s,查找这里,r,i, ,r,s,-1,r,s,r,s,+1,r,k,r,j,均,r,s,轴值 均,r,s,查找这里,(a),若,k,s,，则,r,k,在轴值的后面,2024/10/2,第10章 概率算法,Page,21,舍伍德型概率算法在一次划分之前，根据,随机数在待划分序列中随机确定一个记录作为轴值,，并把它与第一个记录交换，则一次划分后得到期望均衡的两个子序列，使得选择问题在最坏情况下的时间性能趋近于平均情况的时间性能。,算法,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); /,在后半部分继续查找,C+,描述,2024/10/2,第10章 概率算法,Page,22,10.3.1,八皇后问题,10.3,拉斯维加斯,(Las Vegas),型概率算法,2024/10/2,第10章 概率算法,Page,23,拉斯维加斯,(Las Vegas),型概率算法,拉斯维加斯型概率算法不时地做出可能导致算法陷入僵局的选择，并且算法能够检测是否陷入僵局，如果是，算法就承认失败。这种行为对于一个确定性算法是不能接受的，因为这意味着它不能解决相应的问题实例。但是，拉斯维加斯型概率算法的随机特性可以接受失败，只要这种行为出现的概率不占多数。当出现失败时，只要在相同的输入实例上再次运行概率算法，就又有成功的可能。,2024/10/2,第10章 概率算法,Page,24,拉斯维加斯型概率算法的一个显著特征是，,它所做的随机性选择有可能导致算法找不到问题的解，即算法运行一次，或者得到一个正确的解，或者无解。,因此，需要对同,一输入实例反复多次运行算法，直到成功地获得问题的解。,由于拉斯维加斯型概率算法有时运行成功，有时运行失败，因此，通常拉斯维加斯型概率算法的返回类型为,bool,，并且有两个参数：一个是算法的输入，另一个是当算法运行成功时保存问题的解。当算法运行失败时，可对同一输入实例再次运行，直到成功地获得问题的解。,2024/10/2,第10章 概率算法,Page,25,拉斯维加斯型概率算法的一般形式,void Obstinate(input x, solution y),success=false;,while (!success) success=LV(x, y);,2024/10/2,第10章 概率算法,Page,26,设,p,(,x,),是对输入实例,x,调用拉斯维加斯型概率算法获得问题的一个解的概率，则一个正确的拉斯维加斯型概率算法应该对于所有的输入实例,x,均有,p,(,x,)0,。在更强的意义下，要求存在一个正的常数,，使得对于所有的输入实例,x,均有,p,(,x,),。由于,p,(,x,),，所以，只要有足够的时间，对任何输入实例,x,，拉斯维加斯型概率算法总能找到问题的一个解。换言之，拉斯维加斯型概率算法找到正确解的概率随着计算时间的增加而提高。,2024/10/2,第10章 概率算法,Page,27,八皇后问题是在,8,8,的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。,对于八皇后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更像是随机放置的。由此想到拉斯维加斯型概率算法：在棋盘上相继的各行中随机地放置皇后，并使新放置的皇后与已放置的皇后互不攻击，直至八个皇后均已相容地放置好，或下一个皇后没有可放置的位置。,10.3.1,八皇后问题,2024/10/2,第10章 概率算法,Page,28,由于棋盘的每一行上可以而且必须放置一个皇后，所以八皇后问题的可能解用一个向量,X,=(,x,1,x,2, ,x,8,),表示，其中，,1,x,i,8,并且,1,i,8,，即第,i,个皇后放置在第,i,行第,x,i,列上。由于两个皇后不能位于同一列上，所以，解向量,X,必须满足约束条件：,x,i,x,j,（式,10.2,）,若两个皇后摆放的位置分别是,(,i,x,i,),和,(,j,x,j,),，在棋盘上斜率为,-1,的斜线上，满足条件,i,-,j,=,x,i,-,x,j,，在棋盘上斜率为,1,的斜线上，满足条件,i,j,=,x,i,x,j,，综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量,X,必须满足约束条件：,|,i,-,x,i,|,j,-,x,j,|,（式,10.3,）,满足式,10.2,和式,10.3,的向量,X,=(,x,1,x,2, ,x,i,),表示已放置的,i,个皇后（,1,i,8,）互不攻击，也就是不发生冲突。,2024/10/2,第10章 概率算法,Page,29,算法,10.5,八皇后问题,1.,将数组,x8,初始化为,0,；试探次数,count,初始化为,0,；,2,for (i=1; i=8; i+),2.1,产生一个,1, 8,的随机数,j,；,2.2 count=count+1,，进行第,count,次试探；,2.3,若皇后,i,放置在位置,j,不发生冲突，,则,xi=j,；,count=0,；转步骤,2,放置下一个皇后；,2.4,若,(count= =8),，则无法放置皇后,i,，算法运行失败；,否则，转步骤,2.1,重新放置皇后,i,；,3.,将元素,x1,x8,作为八皇后问题的一个解输出；,伪代码,拉斯维加斯型概率算法通过反复调用算法,10.5,，直至得到八皇后问题的一个解。,2024/10/2,第10章 概率算法,Page,30,如果将上述随机放置策略与回溯法相结合，则会获得更好的效果。可以先在棋盘的若干行中随机地放置相容的皇后，然后在其他行中用回溯法继续放置，直至找到一个解或宣告失败。,在棋盘中随机放置的皇后越多，回溯法搜索所需的时间就越少，但失败的概率也就越大。,例如八皇后问题，随机地放置两个皇后再采用回溯法比完全采用回溯法快大约两倍；随机地放置三个皇后再采用回溯法比完全采用回溯法快大约一倍；而所有的皇后都随机放置比完全采用回溯法慢大约一倍。,很容易解释这个现象：不能忽略产生随机数所需的时间，当随机放置所有的皇后时，八皇后问题的求解大约有,70%,的时间都用在了产生随机数上。,2024/10/2,第10章 概率算法,Page,31,10.4.1,主元素问题,10.4,蒙特卡罗,(Monte Carlo),型概率算法,2024/10/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,主元素问题,2024/10/2,第10章 概率算法,Page,33,蒙特卡罗型概率算法求解主元素问题可以随机地选择数组中的一个元素,Ti,进行统计，如果该元素出现的次数大于,n,/2,，则该元素就是数组的主元素，算法返回,true,；否则随机选择的这个元素,Ti,不是主元素，算法返回,false,。此时，数组中可能有主元素也可能没有主元素。如果数组中存在主元素，则非主元素的个数小于,n,/2,。因此，算法将以大于,1/2,的概率返回,true,，以小于,1/2,的概率返回,false,，这说明算法出现错误的概率小于,1/2,。如果连续运行算法,k,次，算法返回,false,的概率将减少为,2,-,k,，则算法发生错误的概率为,2,-,k,。,2024/10/2,第10章 概率算法,Page,34,算法,10.8,主元素问题,bool Majority(int T , int n),i=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; i=k; i+),if (Majority(T, n) return true;,return false;,C+,描述,