并行计算-多媒体课件-并行算法设计与分析-ch18 Randomized Algorithms

ParallelAlgorithms1/Ch18Y.XuCopyrightUSTC2020/2/23ParallelAlgorithmsChapter18RandomizedAlgorithmsParallelAlgorithms2/Ch182020/2/23Y.XuCopyrightUSTC主要内容18.1引言-基本知识-时间复杂性度量-设计方法18.2低度顶点部分独立集-串行算法-随机并行算法18.5多项式恒等的验证-基本技术-矩阵乘积的验证ParallelAlgorithms3/Ch182020/2/23Y.XuCopyrightUSTC18.1引言18.1.1基本知识1.随机算法的定义-定义:是一个概率图灵机.也就是在算法中引入随机因素,即通过随机数选择算法的下一步操作.-三要素:输入实例、随机源和停止准则.-特点:简单、快速和易于并行化.-一种平衡:随机算法可以理解为在时间、空间和随机三大计算资源中的平衡(LuC.J.PhDThesis1999).-重要文献MotwaniR.andRaghavanP.,RandomizedAlgorithms.CambridgeUniversityPress,NewYork,1995ParallelAlgorithms4/Ch182020/2/23Y.XuCopyrightUSTC18.1引言18.1.1基本知识2.背景和历史(1)重要方法-MonteCarlo求定积分法-随机k-选择算法-随机快排序-素性判定的随机算法-二阶段随机路由算法(2)重要人物和工作-deLeeuw等人提出了概率图灵机(1955)-JohnGill的随机算法复杂性理论(1977)-Rabin的数论和计算几何领域的工作(1976)-Karp的算法概率分析方法(1985)-Shor的素因子分解量子算法(1994)ParallelAlgorithms5/Ch182020/2/23Y.XuCopyrightUSTC18.1引言18.1.1基本知识3.随机算法的分类-LasVegas算法和MonteCarlo算法是常见的两类随机算法。-LasVegas算法运行结束时总能给出正确的解，但其运行时间每次有所不同。-MonteCarlo算法可能得到不正确的结果，但这种概率是小的且有界的。ParallelAlgorithms6/Ch182020/2/23Y.XuCopyrightUSTC18.1引言18.1.1基本知识4.研究意义-求解问题的一种重要让步策略-有效的随机算法-实际可行的随机算法-可转化为确定算法-易于并行化-促进智能计算的发展ParallelAlgorithms7/Ch182020/2/23Y.XuCopyrightUSTC18.1引言18.1.2时间复杂性度量1.运行时间的期望和方差(1)实例的运行时间期望对固定实例x,设随机算法A的运行时间是一个[0,+∞)上的随机变量,定义随机算法A在实例x上的运行时间期望为,也称为随机算法A在实例x上的执行时间.(2)算法的运行时间期望如果对一个规模为n问题的所有实例是均匀选取的,则定义各个实例上的平均执行时间为随机算法在该问题上的运行时间期望,记为T(n)注:类似地可以定义方差.2.随机复杂度类(参见MotwaniR.andRaghavanP.,RandomizedAlgorithms.)RP(RandomizedPolynomialtime),ZPP,PP,BPPetc.Ax][AxEParallelAlgorithms8/Ch182020/2/23Y.XuCopyrightUSTC18.1引言18.1.3随机算法的设计方法1.挫败对手(FoilingtheAdversary)将不同的算法组成算法群,根据输入实例的不同随机地或有选择地选取不同的算法,以使性能达到最佳.2.随机采样(RandomSampling)用“小”样本群的信息,指导整体的求解.3.随机搜索(RandomSearch)是一种简单易行的方法,可以从统计角度分析算法的平均性能,如果将搜索限制在有解或有较多解的区域,可以大大提到搜索的成功概率.4.指纹技术(Fingerprinting)利用指纹信息可以大大减少对象识别的工作量.通过随机映射的取指方法,Karp和Rabin得到了一个快速的串匹配随机算法.5.输入随机重组(InputRandomization)对输入实例进行随机重组之后,可以改进算法的平均性能.ParallelAlgorithms9/Ch182020/2/23Y.XuCopyrightUSTC18.1引言18.1.3随机算法的设计方法6.负载平衡(LoadBalancing)在并行与分布计算、网络通讯等问题中,使用随机选择技术可以达到任务的负载平衡和网络通讯的平衡.7.快速混合Markov链(RapidlyMixingMarkovChain)使用该方法可以解决大空间中的均匀抽样问题.8.孤立和破对称技术(IsolationandSymmetryBreaking)使用该技术可以解决处理的并行性,避免分布式系统的死锁等问题.如:图着色算法,部分独立集问题9.概率存在性证明(ProbabilisticMethodsandExistenceProofs)如果随机选取的物体具有某种特性的概率大于0,则具有该特性的物体一定存在.10.消除随机性(Derandomization)许多优秀的确定性算法是由随机算法转换而来的.ParallelAlgorithms10/Ch182020/2/23Y.XuCopyrightUSTC18.1引言18.1.4随机算法举例:QuickSort,MinCut1.QuickSort(1)传统的快排序算法-总是取第一个元素作为划分元；-算法的最坏运行时间是O(n2)，平均时间是O(nlogn)；-因此存在一些输入实例，使得算法达到最坏运行时间，如：降序的序列；(2)随机快排序算法-随机选择一个元素作为划分元；-任何一个输入的期望时间是O(nlogn)；-是一个LasVegas算法；ParallelAlgorithms11/Ch182020/2/23Y.XuCopyrightUSTC18.1引言2.MinCut(1)最小截问题定义：给定一个无向图G(V,E)，找一个截(V1,V2)使得V1和V2间的连边数最小。(2)该问题可以用确定性算法（max-flowmin-cutalgorithm）在O(n2)时间内完成。(3)随机算法随机选一条边，将两顶点合一并除去顶点上的环；直到图中只剩下两个顶点；返回剩下两顶点间的连边数；(4)示例：#cut=215423541,234,51,234,51,2,3ParallelAlgorithms12/Ch182020/2/23Y.XuCopyrightUSTC18.1引言2.MinCut(5)出错概率重复k次出错概率为(6)本算法是一个MonteCarlo型算法.)1(2)1(21nnkkennParallelAlgorithms13/Ch182020/2/23Y.XuCopyrightUSTC18.1引言18.1.5相关概率知识-数学期望和方差-Markov和Chebyshev不等式-Chernoff不等式设Xi是n个独立的Bernoulli随机变量,对于1≤i≤n,E[Xi]=pi,0pi1,231122])1(Pr[])1(Pr[,10,][,eXeXpXEXXNiiNii和有和则对于ParallelAlgorithms14/Ch182020/2/23Y.XuCopyrightUSTC主要内容18.1引言-基本知识-时间复杂性度量-设计方法18.2低度顶点部分独立集-串行算法-随机并行算法18.5多项式恒等的验证-基本技术-矩阵乘积的验证ParallelAlgorithms15/Ch182020/2/23Y.XuCopyrightUSTC18.2低度顶点部分独立集18.2.1串行算法1.问题定义:设G(V,E)是一个平面图.顶点集合称为低度顶点部分独立集,满足以下三个条件:(1)对,deg(v)≤d常数;(2)集合X独立，即X中的任何两顶点都不相邻;(3)X的大小满足|X|≥c|v|，c为某个正常数.2.引理18.1:设G(V,E)是一个至少有三个顶点的平面图,则|E|≤3|V|-6.3.串行算法-定理18.6对任何平面图G(V,E),可以在线性时间内构造出低度顶点部分独立集.-算法:①取,d=6;②由Vd构造独立集:反复取加入到X中,每次移去Vd中与v相连的顶点,直至Vd空;X就是所求;Xv}6)deg(|{ddvVvvVd，常数且dVvParallelAlgorithms16/Ch182020/2/23Y.XuCopyrightUSTC18.2低度顶点部分独立集18.2.2并行算法1.算法描述(算法18.2)输入:平面图G(V,E)的边表输出:低度顶点独立集X={v∈V|label(v)=1}begin(1)Par-do:标出低度顶点Vd(deg(v)=6);(2)Par-do:随机等概率分配所有v∈Vd以标号0或1;//破对称技术(3)Par-do:剔除不满足独立性的标号为1的顶点;(4)剩下的标号为1的低度顶点集就是所求的X;endParallelAlgorithms17/Ch182020/2/23Y.XuCopyrightUSTC18.2低度顶点部分独立集18.2.2并行算法2.算法分析(1)算法的正确性定理18.7算法18.2产生的X={v∈V|label(v)=1}就是一个低度顶点集,使得Pr{|X|≤αn}≤e-βn,其中α和β为常数,n是顶点数.证:我们知道算法18.2产生的X满足低度顶点集的前两个条件,现在只要证明条件3高概率成立,即Pr{|X|≤αn}≤e-βn,其中α和β为常数,n是顶点数.考虑一个特殊的低度顶点子集V’⊆V6,这里V’中的任意两顶点之间的距离至少为3,下面只要证明|V’∩X|以高概率满足条件3.V’这样构造:先任取v1∈V6,删去V6中与v1距离小于2的顶点,可知至多删去36个顶点,再从V6的剩余顶点中任取v2,删去V6中与v2距离小于2的顶点,可知至多删去36个顶点,直至V6为空.V’={v1,v2,…}.因此,|V’|≥(1/37)|V6|≥(1/37)(n/7)=cnc=1/259(∵|Vd|≥c0|V|,c0=(d-5)/(d+1))ParallelAlgorithms18/Ch182020/2/23Y.XuCopyrightUSTC18.2低度顶点部分独立集18.2.2并行算法2.算法分析(1)算法的正确性定理18.7的证明(续):由于V’中顶点的距离至少大于等于3,可知随机变量Xi相互独立.从X的生成过程知:E[Xi]=Pr{vi∈X}≥(1/2)7至此证明了条件3高概率成立.(2)算法时间:O(1),使用了O(n)次运算.cniiiiiiXXcniXvXvXVv1;,...,2,1,01,且定义定义随机变量对每个82127212/)(2/][721)(,))(1(]|Pr[|]|Pr[|]][)1(|Pr[|])()1(|Pr[|,10,72122ccenXnXeeXEXcnXChernoffncnXE有对不等式应用ParallelAlgorithms19/Ch182020/2/23Y.XuCopyrightUSTC主要内容18.1引言-基本知识-时间复杂性度量-设计方法18.2低度顶点部分独立集-串行算法-随机并行算法18.5多项式恒等的验证-基本技术-矩阵乘积的验证ParallelAlgorithms20/Ch182020/2/23Y.XuCopyrightUSTC18.5多项式恒等的验证18.5.1基本技术1.原理-定理1