算法设计与分析ch8-随机算法课件

第八章,Randomized Algorithms,第八章,8.1,Introduction to Randomized Algorithms,随机算法的基本概念,随机算法的分类,随机算法的性能分析方法,随机算法的基本概念,随机算法的分类,随机算法的性能分析方法,8.1 Introduction to Randomize,什么是随机算法,随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法,随机算法的优越性,对于有些问题,:,算法简单,对于有些问题,:,时间复杂性低,对于有些问题,:,同时兼有简单和时间复杂性低,随机算法的随机性,对于同一实例的多次执行,效果可能完全不同,时间复杂性的一个随机变量,解的正确性和准确性也是随机的,随机算法的基本概念,什么是随机算法随机算法的基本概念,随机算法的分类,随机数值算法,主要用于数值问题求解,算法的输出往往是近似解,近似解的精确度与算法执行时间成正比,Monte Carlo,算法,主要用于求解需要准确解的问题,算法可能给出错误解,获得精确解概率与算法执行时间成正比,随机算法的分类随机数值算法,Las Vegas,算法,一旦找到一个解,该解一定是正确的,找到解的概率与算法执行时间成正比,增加对问题反复求解次数,可是求解无效的概率任意小,Sherwood,算法,一定能够求得一个正确解,确定算法的最坏与平均复杂性差别大时,加入随机性,即得到,Sherwood,算法,消除最坏行为与特定实例的联系,Las Vegas算法,随机算法分析的特征,仅依赖于随机选择,不依赖于输入的分布,确定算法的平均复杂性分析,:,依赖于输入的分布,对于每个输入都要考虑算法的概率统计性能,随机算法分析的目标,平均时间复杂性,:,时间复杂性随机变量的均值,获得正确解的概率,获得优化解的概率,解的精确度估计,随机算法的性能分析,随机算法分析的特征随机算法的性能分析,8.2,Randomized Numerical Algorithms,计算,值,计算定积分,8.2 Randomized Numerical Algo,计算,值,数学基础,设有一个半径为,r,的园及其外切四边形,向正方形随机地投掷,n,个点,设,k,个点落入园内,投掷点落入园内的概率为,(,r,2,),/,(4r,2,)=,/,4,.,用,k,/,n,逼近,/,4,即,k,/,n,/,4,于是,(4,k,)/,n.,我们可以令,r=1,用投掷,n,个点的方法计算,计算值数学基础向正方形随机地投掷n个点,设k个点落入园内,算法,K=0,;,For,i=1,To,n,随机地产生四边形中的一点,(,x,y,);,If,x,2,+y,2,1,Then,k=k+1,;,Endfor,Return (,4k,)/,n,时间复杂性,=,O(n),不是输入的大小,而是随机样本的大小,解的精确度,随着随机样本大小,n,增加而增加,算法,计算,定积分,问题,计算积分,数学基础,令,f(x),是,区间,a,b,上的一组独立、同分布的,随机变量,i,的任意密度函数,令,g*(x)=g(x),/,f(x),则,g*(),是密度为,f(x),的随机变量集合,而且,计算定积分问题数学基础,由强大数定律,我们可以用 来近似计算,I,令,f(x)=,1,/,(b-a)a,x,b,索求积分可以由如下,I,来近似计算,I,由强大数定律我们可以用,算法,I=0,;,For,i=1,To,n,随机产生,a,b,中点,x,;,I,=,I,+,g(x),;,Endfor,Return (,b-a,)*,I,/,n,时间复杂性,=,O(n),不是输入的大小,而是随机样本的大小,解的精确度,随着随机样本大小,n,增加而增加,算法,8.3,Randomized Selection Algorithms,问题的定义,随机算法,算法的性能分析,8.3 Randomized Selection Algo,问题的定义,输入,:,S,=,x,1,x,2,x,n,，,整数,k,，,1,k,n,.,输出,:,S,中第,k,个最小元素,.,记号,Rank(,Q,t),=,集合,Q,中的元素,t,的,rank,(,第,k,小元素的,rank,是,k,),min(,Q,i,)=,集合,Q,中第,i,个最小元素,.,问题的定义 输入:S=x1,x2,xn，记号,随机算法,基本思想,从,S,中随机地抽取,n,3/4,个样本存入,R,排序,R,S,中第,k,最小元素可能成为,R,中,x,=,kn,3/4,/n,最小元素,为了解决误差问题,我们考察区间,x-n,1/2,x+n,1/2,x,r,l,r,h,r,1,r,n,3/4,l,h,L,H,把,S,中属于,L,H,数据存入,P,在,P,中查找,min(S,k),随机算法 基本思想xrlrhr1rn3/4lhL,LAZYSELECT(,S,k,),R,=,独立、均匀、可放回地从,S,随机选取的,n,3/4,元素,;,在,O(n,log,n),时间内排序,R,;,x,=(,k/n,),n,3/4,;,/*(,k/n,),n,3/4,=,kn,-1/4,*/,l,=max ,0;,h,=min ,n,3/4,;,L=min(R,l),;,H=min(R,h),;,L,p,=,Rank,(,S,L,),H,p,=,Rank,(,S,H,);,/*,L,和,H,与,S,元素比较*,/,P,=,y,S,|,L,y,H,;,If,min(S,k,),P,and|,P,|,4,n,3/4,+1,/*,max(S,k,),P,可由,L,p,k,H,p,确定*,/,9.Then,排序,P,min(S,k),=,min(P,(k-L,p,),),算法结束,;,10.ELSE goto 1.,LAZYSELECT(S,k),数学基础,数学期望,离散随机变量,X,的数学期望,E,X,=,i,iP(X=i),若,f(x),是定义在整数集上的实数值函数,则,E,f(X),=,i,f(i)P(X=i),.,Markov,不等式,P,(,Y,t,),E,Y,/,t,其中,Y,为非负随机变量,t,0.,算法的性能分析,数学基础算法的性能分析,方差的性质与,Chebyshev,不等式,方差,x,2,=,E,(,X-,x,),2,x,为随机变量,X,的数学期望,x,称为标准差,Chebyshev,不等式,:,P,(|,X-,x,|,t,x,),1/,t,2,如果随机变量,X,满足,P,(,X=1,)=,p,P,(,X=0,)=,1-p,则,x,2,=,p,(,1-p,).,若,X,=,1,i,n,X,i,x,2,=,1,i,n,x,i,2,X,i,是独立随机变量,若随机变量,X,i,满足,P,(,X,i,=1)=,p,P,(,X,i,=0)=,1-p,则,x,2,=,np(1-p),.,方差的性质与Chebyshev不等式,算法的性能分析,定理,.,算法执行,1-9,步一遍就可求出,min(S,k),的概率是,1-O(n,-1/4,),即算法需要,2n+O(n,log,n),次比较就可求出,min(S,k),的概率,是,1-O(n,-1/4,),.,证明,.,若算法执行,1-9,一遍可求出,min(S,k),则第,6,步需,2n,次比较,其他步需,O(n,log,n),次比较,总需,2n+O(n,log,n),次比较,.,往证算法执行,1-9,一遍可求出,min(S,k),的概率是,1-O(n,-1/4,),.,算法执行,1-9,一遍可求出,min(S,k),的条件是,:,(1).,min(S,k),在,L,和,H,之间即,P,包含,min(S,k),(2).|,P,|,4n,3/4,+1.,我们首先来计算上述两个条件失败的概率,.,算法的性能分析,A.,计算条件,(1),不成立的概率,条件,(1),不成立当且仅当,L,min(S,k),或,H,min(S,k),X,l,.,如果,H,min(S,k),)=,P,(,X,l,)=,P,(,X,n,1/2,),P,(,H,h,)+,P,(,X=h,)=,P,(|,X-,x,|,n,1/2,)+(,n,3/4,+1),-1,.,应用,Chebyshev,不等式,又由,2n,1/8,x,n,1/2,我们有,P,(|,X,-,x,|,n,1/2,),P,(|,X-,x,|,2n,1/8,x,),1/(2n,1/8,),2,=,O(n,-1/4,),.,于是,P,(,L,min(S,k),)=,P,(,H,min(S,k),)=,O(n,-1/4,),.,A.计算条件(1)不成立的概率x=xrlrhr1rn3/,B.,计算,P,包含,min(S,k),但,|,P,|,4n,3/4,+1,不成立的概率,令,k,l,=max,0,k-2n,3/4,k,h,=min,k+2n,3/4,n,.,“,P,包含,min(S,k),但,|,P,|,4n,3/4,+1,不成立”发生当且仅当,L,min(S,k,h,),.,类似与上面,A,中的分析，,P,(,L,min(S,k,h,),)=,O(n,-1/4,).,由,A,和,B,“,算法执行,1-9,一遍就可以求出,min(S,k,),”,不,成立的概率是,O(n,-1/4,),.,即，“算法执行,1-9,一遍就可以求出,min(S,k),”,的概率,是,1-O(n,-1/4,),.,k,2n,3/4,2n,3/4,k,h,k,l,min(S,k,h,),min(S,k,l,),l,L,h,H,B.计算P包含min(S,k)但|P|4n3/4+1不,8.4,Randomized Algorithm to Test Whether,Number is Prime,问题的定义,随机算法设计,算法的性能分析,8.4 Randomized Algorithm to,输入,一个正整数,N,输出,N,是否素数,问题的定义,输入问题的定义,基本思想,对,N,进行,m,次测试,如果有一次测试成功,则回答,N,是合数,如果,m,次测试均失败,则回答,N,是素数,回答,N,是合数时,答案百分之百正确,回答,N,是素数时,答案正确的概率是,1-2,-m,随机算法的设计,基本思想随机算法的设计,随机算法,随机地选择,m,个数,b,1,b,2,b,m,满足,1,b,1,b,2,b,m,N,;,For,i=1,To,m,Do,If,W(b,i,),成立,Then Return(,N,是合数,);,Return(,N,是素数,),W(b,i,),定义如下,:,(1),b,i,N-1,1 mod N,或,(2),j,(N-1)/2,j,=,k,是整数,1,(,b,i,k,与,N,的最大公因子,),N,.,随机算法,例,1,.,给定,N=12.,选择测试数集,2,3,7,测试,2,:,2,12-1,=2048,1 mod 12,W(2),成立,.,N,是合数,.,例1.给定N=12.选择测试数集2,3,7,例,2.,给定,N=11,选择测试数集,2,5,7,测试,2,:,2,11-1,=1024,=,1 mod 11,令,j=1,k=(N-1)/2,j,=10/2=5,gcd(2,k,-1,N)=gcd(31,11)=1,j=1,是唯一使,(N-1)/2,j,为整数的,j,W(2),不成立,.,测试,5,:,5,11-1,=9765625,=,1 mod 11,令,j=1,k=(N-1)/2,j,=10/2=5,gcd(5,k,-1,N)=gcd(3124,11)=11=N,j=1,是唯一使,(N-1)/2,j,为整数的,j,W(5),不成立,.,测试,7,:,7,11-1,=282475249,=,1 mod 11,令,j=1,k=(N-1)/2,j,=10/2=5,gcd(7,k,-1,N)=gcd(16806,11)=1,j=1,是唯一使,(N-1)/2,j,为整数的,j,W(5),不成立,.,结论,:,11,可能是素数,答案正确的概率