算法设计与分析ch8随机算法.ppt

第八章第八章 Randomized AlgorithmsRandomized Algorithms8.1 Introduction to Randomized Introduction to Randomized AlgorithmsAlgorithms随机算法的基本概念随机算法的基本概念随机算法的分类随机算法的分类随机算法的性能分析方法随机算法的性能分析方法随机算法的基本概念随机算法的基本概念随机算法的分类随机算法的分类随机算法的性能分析方法随机算法的性能分析方法什么是随机算法什么是随机算法随机算法是一种使用概率和统计方法在其执行随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法过程中对于下一计算步骤作出随机选择的算法随机算法的优越性随机算法的优越性对于有些问题对于有些问题:算法简单算法简单对于有些问题对于有些问题:时间复杂性低时间复杂性低对于有些问题对于有些问题:同时兼有简单和时间复杂性低同时兼有简单和时间复杂性低随机算法的随机性随机算法的随机性对于同一实例的多次执行对于同一实例的多次执行,效果可能完全不同效果可能完全不同时间复杂性的一个随机变量时间复杂性的一个随机变量解的正确性和准确性也是随机的解的正确性和准确性也是随机的随机算法的基本概念随机算法的基本概念随机算法的分类随机算法的分类随机数值算法随机数值算法主要用于数值问题求解主要用于数值问题求解算法的输出往往是近似解算法的输出往往是近似解近似解的精确度与算法执行时间成正比近似解的精确度与算法执行时间成正比Monte Carlo算法算法主要用于求解需要准确解的问题主要用于求解需要准确解的问题算法可能给出错误解算法可能给出错误解获得精确解概率与算法执行时间成正比获得精确解概率与算法执行时间成正比Las Vegas算法算法一旦找到一个解一旦找到一个解,该解一定是正确的该解一定是正确的找到解的概率与算法执行时间成正比找到解的概率与算法执行时间成正比增增加加对对问问题题反反复复求求解解次次数数,可可是是求求解解无无效效的概率任意小的概率任意小Sherwood算法算法一定能够求得一个正确解一定能够求得一个正确解确确定定算算法法的的最最坏坏与与平平均均复复杂杂性性差差别别大大时时,加入随机性加入随机性,即得到即得到Sherwood算法算法消除最坏行为与特定实例的联系消除最坏行为与特定实例的联系随机算法分析的特征随机算法分析的特征仅依赖于随机选择仅依赖于随机选择,不依赖于输入的分布不依赖于输入的分布确定算法的平均复杂性分析确定算法的平均复杂性分析:依赖于输入的分布依赖于输入的分布对于每个输入都要考虑算法的概率统计性能对于每个输入都要考虑算法的概率统计性能随机算法分析的目标随机算法分析的目标平均时间复杂性平均时间复杂性:时间复杂性随机变量的均值时间复杂性随机变量的均值获得正确解的概率获得正确解的概率获得优化解的概率获得优化解的概率解的精确度估计解的精确度估计随机算法的性能分析随机算法的性能分析 8.2 Randomized Numerical Randomized Numerical AlgorithmsAlgorithms计算计算 值值计算定积分计算定积分计算计算 值值数学基础数学基础设有一个半径为设有一个半径为r的园及其外切四边形的园及其外切四边形向正方形随机地投掷向正方形随机地投掷n个点个点,设设k个点落入园内个点落入园内投掷点落入园内的概率为投掷点落入园内的概率为(r2)/(4r2)=/4.用用k/n逼近逼近/4,即即k/n /4,于是于是 (4k)/n.我们可以令我们可以令r=1用投掷用投掷n个点的方法计算个点的方法计算 算法算法K=0;For i=1 To n 随机地产生四边形中的一点随机地产生四边形中的一点(x,y);If x2+y2 1 Then k=k+1;EndforReturn (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);EndforReturn (b-a)*I/n时间复杂性时间复杂性=O(n)不是输入的大小不是输入的大小,而是随机样本的大小而是随机样本的大小解的精确度解的精确度随着随机样本大小随着随机样本大小n增加而增加增加而增加 8.3 Randomized Selection AlgorithmsRandomized Selection Algorithmsl问题的定义问题的定义l随机算法随机算法l算法的性能分析算法的性能分析问题的定义问题的定义 输入输入:S=x1,x2,xn，整数整数k，1 k n.输出输出:S中第中第k个最小元素个最小元素.记号记号 Rank(Q,t)=集合集合Q中的元素中的元素t的的rank (第第k小元素的小元素的rank是是k)min(Q,i)=集合集合Q中第中第i个最小元素个最小元素.随机算法随机算法 基本思想基本思想 从从S中随机地抽取中随机地抽取n3/4个样本存入个样本存入R,排序排序R S中第中第k最小元素可能成为最小元素可能成为R中中x=kn3/4/n最小元素最小元素 为了解决误差问题为了解决误差问题,我们考察区间我们考察区间x-n1/2,x+n1/2x xr rl lr rh hr r1 1r rn n3/43/4l lh hL LHH 把把S中属于中属于L,H数据存入数据存入P 在在P中查找中查找min(S,k)LAZYSELECT(S,k)1.R=独立、均匀、可放回地从独立、均匀、可放回地从S随机选取的随机选取的n3/4元素元素;2.在在O(nlogn)时间内排序时间内排序R;3.x=(k/n)n3/4;/*(/*(k/nk/n)n n3/43/4=knkn-1/4-1/4*/*/4.l=max ,0;h=min ,n3/4;5.L=min(R,l);H=min(R,h);6.Lp=Rank(S,L),Hp=Rank(S,H);/*/*L L和和和和HH与与与与S S元素比较元素比较元素比较元素比较*/7.P=y S|L y H;8.If min(S,k)P and|P|4n3/4+1 /*/*max(S,kmax(S,k)P P可由可由可由可由L Lp p k k HHp p确定确定确定确定*/9.Then 排序排序P,min(S,k)=min(P,(k-Lp),算法结束算法结束;10.ELSE goto 1.数学基础数学基础数学期望数学期望离散随机变量离散随机变量离散随机变量离散随机变量X X的数学期望的数学期望的数学期望的数学期望E E X X=i i i i P(X=i)P(X=i)若若若若f(x)f(x)是定义在整数集上的实数值函数是定义在整数集上的实数值函数是定义在整数集上的实数值函数是定义在整数集上的实数值函数,则则则则 E E f(X)f(X)=i i f(i)f(i)P(X=i)P(X=i).Markov不等式不等式P P(Y Y t t)E E Y Y/t t,其中其中其中其中Y Y为非负随机变量为非负随机变量为非负随机变量为非负随机变量,t t 0.0.算法的性能分析算法的性能分析方差的性质与方差的性质与Chebyshev不等式不等式方差方差方差方差 x x2 2=E E(X-X-x x)2 2,x x为随机变量为随机变量为随机变量为随机变量X X的数学期望的数学期望的数学期望的数学期望 x x称为标准差称为标准差称为标准差称为标准差ChebyshevChebyshev不等式不等式不等式不等式:P P(|(|X-X-x x|t t x x)1/1/t t2 2如果随机变量如果随机变量如果随机变量如果随机变量X X满足满足满足满足P P(X=1X=1)=)=p p,P P(X=0X=0)=)=1-p1-p,则则则则 x x2 2=p p(1-p1-p).).若若若若X X=1 1 i i n n X Xi i,x x2 2=1 1 i i n n x xi i2 2,X Xi i是独立随机变是独立随机变是独立随机变是独立随机变量量量量若随机变量若随机变量若随机变量若随机变量X Xi i满足满足满足满足P P(X Xi i=1)=1)=p p,P P(X Xi i=0)=0)=1-p1-p,则则则则 x x2 2=np(1-p)np(1-p).算法的性能分析算法的性能分析定理定理定理定理.算法执行算法执行算法执行算法执行1-91-9步一遍就可求出步一遍就可求出步一遍就可求出步一遍就可求出min(S,k)min(S,k)的概率是的概率是的概率是的概率是1-O(n1-O(n-1/4-1/4),即算法需要即算法需要即算法需要即算法需要2n+O(n2n+O(nloglogn)n)次比较就可求出次比较就可求出次比较就可求出次比较就可求出min(S,k)min(S,k)的概率的概率的概率的概率 是是是是1-O(n1-O(n-1/4-1/4).证明证明证明证明.若算法执行若算法执行若算法执行若算法执行1-91-9一遍可求出一遍可求出一遍可求出一遍可求出min(S,k)min(S,k),则第则第则第则第6 6步需步需步需步需2n2n次比较次比较次比较次比较,其他步需其他步需其他步需其他步需O(nO(nloglogn)n)次比较次比较次比较次比较,总需总需总需总需2n+O(n2n+O(nloglogn)n)次比较次比较次比较次比较.往证算法执行往证算法执行往证算法执行往证算法执行1-91-9一遍可求出一遍可求出一遍可求出一遍可求出min(S,k)min(S,k)的概率是的概率是的概率是的概率是1-O(n1-O(n-1/4-1/4).算法执行算法执行算法执行算法执行1-91-9一遍可求出一遍可求出一遍可求出一遍可求出min(S,k)min(S,k)的条件是的条件是的条件是的条件是:(1).(1).min(S,k)min(S,k)在在在在L L和和和和HH之间即之间即之间即之间即P P包含包含包含包含min(S,k)min(S,k),(2).|(2).|P P|4n4n3/43/4+1.+1.我们首先来计算上述两个条件失败的概率我们首先来计算上述两个条件失败的概率我们首先来计算上述两个条件失败的概率我们首先来计算上述两个条件失败的概率.A.A.计算条件计算条件计算条件计算条件(1)(1)不成立的概率不成立的概率不成立的概率不成立的概率条件条件条件条件(1)(1)不成立当且仅当不成立当且仅当不成立当且仅当不成立当且仅当L L min(S,k)min(S,k)或或或或HH min(S,k)min(S,k),X,Xl l.如果如果如果如果HH min(S,k)min(S,k)=)=P P(X X l l)=)=P P(X X n n1/21/2),),P P(HH hXh)+)+P P(X=hX=h)=)=P P(|(|X-X-x x|n n1/21/2)+()+(n n3/43/4+1)+1)-1 1.应用应用应用应用ChebyshevChebyshev不等式不等式不等式不等式,又由又由又由又由2n2n1/8 1/8 x x n n1/21/2,我们有我们有我们有我们有 P P(|(|X X-x x|n n1/21/2)P P(|(|X-X-x x|2n2n1/81/8 x x)1/(2n1/(2n1/81/8)2 2=O(nO(n-1/4-1/4).于是于是于是于是 P P(L L min(S,k)min(S,k)=)=P P(HH min(S,k)min(S,k)=)=O(nO(n-1/4-1/4).B.计算计算P包含包含min(S,k)但但|P|4n3/4+1不成立的概率不成立的概率令令kl=max0,k-2n3/4,kh=mink+2n3/4,n.“P包含包含min(S,k)但但|P|4n3/4+1不成立不成立”发生当且仅发生当且仅当当 Lmin(S,kh).类似与上面类似与上面A中的分析，中的分析，P(Lmin(S,kh)=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 k2n2n3/43/42n2n3/43/4k kh hk kl lmin(S,kmin(S,kh h)min(S,kmin(S,kl l)l lL Lh hHH8.4 Randomized Algorithm to Test Whether Randomized Algorithm to Test Whether Number is Prime Number is Primel问题的定义问题的定义l随机算法设计随机算法设计l算法的性能分析算法的性能分析输入输入一个正整数一个正整数N输出输出N是否素数是否素数问题的定义问题的定义基本思想基本思想对对N进行进行m次测试次测试如果有一次测试成功如果有一次测试成功,则回答则回答N是合数是合数如果如果m次测试均失败次测试均失败,则回答则回答N是素数是素数回答回答N是合数时是合数时,答案百分之百正确答案百分之百正确回答回答N是素数时是素数时,答案正确的概率是答案正确的概率是1-2-m随机算法的设计随机算法的设计随机算法随机算法1.随机地选择随机地选择m个数个数b1,b2,bm,满足满足 1 b1,b2,bm N;2.For i=1 To m Do3.If W(bi)成立成立 Then Return(N是合数是合数);4.Return(N是素数是素数)W(bW(bi i)定义如下定义如下定义如下定义如下:(1)(1)b bi iN-1 N-1 1 mod N,1 mod N,或或或或(2)(2)j j(N-1)/2(N-1)/2j j=k k是整数是整数是整数是整数,1 1 (b bi ik k与与与与N N的最大公因子的最大公因子的最大公因子的最大公因子)N N.例例1.给定给定N=12.选择测试数集选择测试数集2,3,7 测试测试 2:212-1=2048 1 mod 12,W(2)成立成立.N是合数是合数.例例2.给定给定N=11,选择测试数集选择测试数集2,5,7 测试测试 2:211-1=1024=1 mod 11,令令j=1,k=(N-1)/2j=10/2=5,gcd(2k-1,N)=gcd(31,11)=1,j=1是唯一使是唯一使(N-1)/2j为整数的为整数的j,W(2)不成立不成立.测试测试 5:511-1=9765625=1 mod 11,令令j=1,k=(N-1)/2j=10/2=5,gcd(5k-1,N)=gcd(3124,11)=11=N,j=1是唯一使是唯一使(N-1)/2j为整数的为整数的j,W(5)不成立不成立.测试测试 7:711-1=282475249=1 mod 11,令令j=1,k=(N-1)/2j=10/2=5,gcd(7k-1,N)=gcd(16806,11)=1,j=1是唯一使是唯一使(N-1)/2j为整数的为整数的j,W(5)不成立不成立.结论结论:11可能是素数可能是素数 答案正确的概率为答案正确的概率为1-2-3定理定理1.(1)如果对于任意如果对于任意1 bN,W(b)成立成立,则则N是合数是合数.(2)如果如果N是合数是合数,则则(N-1)/2|b|1 bN,W(b)|*(1)(1)说明算法是正确的说明算法是正确的说明算法是正确的说明算法是正确的.*(2)*(2)说明说明说明说明,如果如果如果如果N N是合数是合数是合数是合数,则至少一半则至少一半则至少一半则至少一半b b(bNbN)使使使使W(b)W(b)成立成立成立成立定理定理2.算法的回答算法的回答“N是素数是素数”正确的概率是正确的概率是1-2-m.算法性能的分析算法性能的分析 8.5 Randomized Sorting AlgorithmRandomized Sorting Algorithm 问题的定义问题的定义 随机随机算法算法 算法性能的分析算法性能的分析问题的定义问题的定义输入输入 S=x1,x2,xn 输出输出l l 排序的排序的S基本思想基本思想采用随机抽样的方法确定集合的划分点采用随机抽样的方法确定集合的划分点把集合划分为两个子集合把集合划分为两个子集合分别递归地在每个子集合上使用随机排序算法分别递归地在每个子集合上使用随机排序算法随机算法随机算法 算法算法1.均匀等可能地在均匀等可能地在S中随机抽取一个样本中随机抽取一个样本y;2.比较比较S中每个元素中每个元素,把把S划分为如下两个集合划分为如下两个集合:S1=x|x S,xy;3.递归地排序递归地排序S1和和S2;4.顺序输出排序的顺序输出排序的S1,y,S2;算法性能的分析算法性能的分析 基本概念基本概念 S(i)表示表示S中阶为中阶为i的元素的元素 例如例如,S(1)和和和和S(n)分别分别是是是是最小和最大元素最小和最大元素 随机变量随机变量Xij 定义如下定义如下:Xij=1如果如果S(i)和和S(j)在运行中被比较在运行中被比较,否则为否则为0 Xij是是S(i)和和S(j)的比较次数的比较次数 算法的比较次数为算法的比较次数为 算法的平均复杂性为算法的平均复杂性为 计算计算EXij 设设pij为为S(i)和和S(j)在运行中比较的概率在运行中比较的概率,则则 EXij=pij 1+(1-pij)0=pij关键问题成为求解关键问题成为求解pij 求解求解Pij我们可以用树表示算法的计算过程我们可以用树表示算法的计算过程 y yT T1 1T T2 2y yx xT T1111T T1212x xT T2121T T2222 我们可以观察到如下事实我们可以观察到如下事实:一个子树的根必须与其子树的所有节点比较一个子树的根必须与其子树的所有节点比较 不同子树中的节点不可能比较不同子树中的节点不可能比较 任意两个节点至多比较一次任意两个节点至多比较一次 当当S(i),S(i+1),S(j)在同一子树时在同一子树时,S(i)和和S(j)才可能比较才可能比较 由随机算法的特点由随机算法的特点,S(i),S(i+1),S(j)在同一子树的概在同一子树的概 率为率为1 只有只有S(i)或或S(j)被选为划分点时被选为划分点时,S(i)和和S(j)才可能比较才可能比较 S(i),S(i+1),S(j)等可能地被选为划分点等可能地被选为划分点,所以所以S(i)和和S(j)进行比较的概率是进行比较的概率是:2/(j-i+1),即即pij=2/(j-i+1)现在我们有现在我们有 定理定理.随机排序算法的期望时间复杂性为随机排序算法的期望时间复杂性为O(nlogn)8.6 A Min-Cut AlgorithmA Min-Cut Algorithml问题定义问题定义 l随机算法随机算法l算法性能的分析算法性能的分析输入输入:无向多重连通图无向多重连通图G输出输出一个一个Min-Cut问题定义问题定义 图图G的一个的一个Cut是一组边是一组边,从从G中删除这个中删除这个Cut将导致将导致 两个或多个连通分量两个或多个连通分量 Cut的大小是其边数的大小是其边数,多重边重复计算多重边重复计算 最小最小Cut是具有最少边的是具有最少边的Cut随机算法随机算法基本概念基本概念Cut可以视为节点集的划分可以视为节点集的划分V=(C,V-C),Cut是所有是所有G中连接中连接C和和V-C的边集合的边集合.图图G的边的边(x,y)的的contraction:用新节点代替节点用新节点代替节点用新节点代替节点用新节点代替节点x x和和和和y y或边或边或边或边(x,y),(x,y),v v V V,用边用边用边用边(v,z)(v,z)代替边代替边代替边代替边(x,v)(x,v)或或或或(y,v),(y,v),G G的其余部分保持不变的其余部分保持不变的其余部分保持不变的其余部分保持不变 例如例如:收缩收缩收缩收缩e ee1 12 25 54 43 35 54 43 31212我们用我们用G/(x,y)表示表示G的边的边(x,y)的收缩的收缩边集合边集合F G收缩记作收缩记作G/F图图G/F的节点集合表示为的节点集合表示为V/F图图G/F的节点集合表示为的节点集合表示为E/F随机算法随机算法1.H=G;2.While|H(V)|2 Do3.随机地从随机地从H(E)中选择一条边中选择一条边(x,y);4.F=F(x,y);5.H=H/(x,y);6.Cut=连接连接H中两个元节点的中两个元节点的G的所有边的所有边.例例收缩收缩收缩收缩e ee1 12 25 54 43 35 54 43 31212e1e1收缩收缩收缩收缩e1e14 43 3125125e3e33 312541254收缩收缩收缩收缩e3e3Cut=(1,3),(2,3)定理定理1.如果算法的输入是具有如果算法的输入是具有n个节点的多重图个节点的多重图,则则 算法的时间复杂性为算法的时间复杂性为O(n2).证明证明.一次边收缩需要一次边收缩需要O(n)时间时间.至多进行至多进行O(n)次收缩次收缩.于是于是,算法时间复杂性为算法时间复杂性为O(n2).注意注意:我们仅证明了在我们仅证明了在O(n2)时间内算法能够求出一个时间内算法能够求出一个Cut,但是这个但是这个Cut不一定是优化的不一定是优化的.算法的性能分析算法的性能分析引理引理1.如果如果k是是min-cut的大小的大小,则则G至少有至少有kn/2条边条边.证证.如果如果|G(E)|kn/2,则存在一个度小于则存在一个度小于k的节点的节点p.删除与删除与p相关连的相关连的k条条,把把G划分为两个连通分划分为两个连通分 量量,其一是仅包含其一是仅包含p.于是于是,与与p相关连的边集合是一个相关连的边集合是一个cut.但是这个但是这个cut的大小的大小k,与与min-cut大小为大小为k矛盾矛盾.引理引理2.算法输出的算法输出的cut是连接两个剩余节点的没有被收是连接两个剩余节点的没有被收 缩过的边缩过的边.证证.从算法定义可以看到从算法定义可以看到,算法输出的算法输出的cut是连接两是连接两 个剩余节点的没有被收缩的边的集合个剩余节点的没有被收缩的边的集合.引理引理1.如果如果k是图是图G的一个的一个min-cut的大小的大小,则则G至少有至少有 kn/2条边条边.证证.如果如果|G(E)|kn/2,则存在一个度小于则存在一个度小于k的节点的节点p.删除与删除与p相关连的相关连的k条条,把把G划分为两个连通分划分为两个连通分 量量,其一是仅包含其一是仅包含p的连通分量的连通分量.于是于是,与与p相关连的边集合是一个相关连的边集合是一个cut.但是这个但是这个cut的大小的大小2/n1-2/(n-i+1)=2/n(n-1)2/n2 2推论推论1.如果重复运行算法如果重复运行算法n2/2次次,每次独立随机地选每次独立随机地选 择收缩边择收缩边,不能发现一个不能发现一个min-cut的概率为的概率为