最小生成树期望线性时间算法

最小生成树(MST)线性时间算法[e-mail]相关算法Borůvka算法O(min{n^2,mlogn})Prim算法O(m+nlgn)Kruskal算法O(mlgm)Karger，Klein&Tarjan提出的算法（今天报告的内容）O(m)最快的非随机比较算法是由伯纳德·沙泽勒提出的。该算法依赖于softheap。最小生成树(MST)简介在一给定的无向图G=(V,E)中，(u,v)代表连接顶点u与顶点v的边，而w(u,v)代表此边的权重，若存在T为E的子集且为连通无环图，使得T中边权之和最小，则此T为G的最小生成树。最小生成树其实是最小权重生成树的简称。ARandomizedLinear-TimeAlgorithmtoFindMinimumSpanningTrees1DAVIDR.KARGERStanfordUniversity,Stanford,California2PHILIPN.KLEINBrownUnilerslty,Providence,RhodeIsland3ROBERTE.TARJANPrincetonUniversityandNECResearchInstitute,Princeton,NewJersey关键词：Matroid拟阵minimumspanningtree最小生成树network网络randomizedalgorithm随机化算法前言与引理RedRule&BlueRuleCyclePropertyForanycycleCinagraph,theheaviestedgeinCdoesnotappearintheminimumspanningforest.对于图中的任何环C，C中权值最大的边一定不属于最小生成森林。CutPropertyForanypropernonemptysubsetXofthevertices,thelightestedgewithexactlyoneendpointinXbelongstotheminimumspanningforest.对于图的点集的任何子集X，恰好有一个端点在X中的所有边中最小的那条边一定属于最小生成森林。F-light&F-heavyF-lightedge(F的轻边)设F为图G中的一个森林，令w(x,y)表示边(x,y)的权，F(x,y)表示森林中连接x和y的一条路径，而WF(x,y)表示路径上边权的最大值（如果x,y不连通，则WF(x,y)为正无穷）。若w(x,y)WF(x,y)，则(x,y)是F-heavyedge，否则称(x,y)为F-lightedge。F-heavyedge(F的重边)1.任何森林F的F-heavyedge不可能在最小生成树中。（由cycleproperty导出）2.给定一个森林F，F-heavyedge可以在O(n)时间内计算出来，使用改编过的Dixon等人的验证算法。modifiedDixon-Rauch-TarjanverificationalgorithmLemma&RemarkTEXTHERE通过以独立的概率p来加入每个边，获得一个G的子图H。令F为H的最小生成森林，则F-lightedge的期望数量最多是n/p（其中n是G的顶点数）TEXTHERE上面的证明实际上表明了F-轻边的数量随机地由具有负二项分布的变量主导。negativebinomialdistributionTEXTHERE引理2-3适用于所有拟阵。Lemma2.1directlygeneralizestomatroids.引理2-1备注2-2备注2-3算法Algorithmrandom-samplingsteps随机取样操作zBorůvkasteps布卢瓦卡操作每一步布卢瓦卡操作都把点数量降低到1/2以下每一步随机取样都丢弃足够多的边来降低密度，并且有极大的可能会降到一个固定的常量Borůvkasteps对于每个点，选择一条与该点相连的最小权值的边。用一个点去替代上述边集产生的所有连通分量，并删除所有孤立点和自环，对于缩点产生的重边，只保留权值最小的。Foreachvertex,selecttheminimum-weightedgeincidenttothevertex.Contractalltheselectededges,replacingbyasinglevertexeachconnectedcomponentdefinedbytheselectededgesanddeletingallresultingisolatedvertices,loops(edgesbothofwhoseendpointsarethesame),andallbutthelowest-weightedgeamongeachsetofmultipleedges.BorůvkastepsAlgorithm(1)应用两次布卢瓦卡操作。这会使点数量减少到1/4以下。(3)递归地调用算法生成最小生成森林F'，返回F'以及在(1)中被压缩的边。(2)以1/2的概率，在压缩图中独立地加入边构造出子图H。递归调用该算法，构造最小生成森林F。寻找所有F-heavyedge，并把它们从压缩图中删去。如果输入是空图，则返回空森林。如果输入不是空图，则执行以下操作算法正确性分析根据cutproperty，步骤（1）中收缩的每个边都在最小生成森林中。因此，原始图形的最小生成森林的剩余边形成压缩图的最小生成森林。这表明步骤（3）中的递归调用找到压缩图的的最小生成森林。根据cycleproperty，步骤（2）中删除的边不属于最小生成森林。通过归纳假设，在步骤（3）的递归调用中正确地确定了剩余图的最小生成森林。备注3.1我们的算法可以被视为Tarjan[1983]中提出的广义贪心算法的一个实例，所以它的正确性可以直接得到证明。Matroid算法复杂度分析及实验结果时间复杂度runningtime2期望复杂度为O(m)1最坏情况O(min{n^2,mlogn})3绝大多数情况下，运行时间是线性的Algorithm(1)应用两次布卢瓦卡操作。这会使点数量减少到1/4以下。这一步是O(m)(3)递归地调用算法生成最小生成森林F'，返回F'以及在(1)中被压缩的边。同样不考虑递归调用，时间是O(m)(2)以1/2的概率，在压缩图中独立地加入边构造出子图H。递归调用该算法，构造最小生成森林F。寻找所有F-heavyedge，并把它们从压缩图中删去。先不考虑递归调用，寻找F-heavyedge的开销是O(m)小结：若图为连通图，m=n/2。在不考虑递归调用的情况下，算法每一步的开销是O(m)。每一步点数量减少为1/4，因此在递归树的第d层，节点数为n/4d。所以原问题和子问题的节点总数为Σ2dn/4d=Σn/2d=2nTheorem4.1最坏情况的时间复杂度为O(min{n^2,mlogn})回忆：递归调用时产生了两个子问题，一个用于剪枝，一个用于解决问题。我们设用于剪枝的子问题在递归树是左儿子，用于解决问题的子问题在递归树中是右儿子。一方面，递归树深度为d的节点上，边数不会超过(n/4d)2/2（完全图），对d求和（分子n^2，Σ8d收敛）得O(n^2)另一方面，步骤1中被删除的边不出现在子问题中；在最终的生成树里的边出现在两个子问题中；其余的边仅在子问题中出现一次。最终生成树里的边数不会超过节点数n/4，而步骤1删除的边至少n/2条。所以，每一层的子问题都是O(m)，所以最终结果O(mlgn)。Theorem4.2期望的时间复杂度为O(m)考虑一个X条边的子问题，这X条边中，有的边被布卢瓦卡操作删掉，剩下的边有1/2的概率在步骤2中被选择为左儿子对应的子图，所以子图的边E(Y)=E(X)/2，所以，所有左儿子的边总数量加起来为2m。通过引理2.1我们知道，所有右儿子的边数最多是点数量的两倍，所以所有右儿子中点的总数最多Σ2d-1n/4d=n/2，右儿子的边数总量为n。又因为m=n/2，所以总的期望时间为O(4m)=O(m)Theorem4.3此最小生成树算法以O(m)的时间运行的概率是1–exp(–Ω(m))换句话说，每e^Ω(m)次运行，只会出现1次该算法不是以线性时间运行的情况。这是相当好的结果，只要边的数量一上去，这个概率很快就可以忽略不计了。这个定理在论文中有证明，这里略去。Remark可并行化这个算法是可并行的。尚未解决的问题1.存在100%可靠的线性算法吗？2.随机化策略或其他技巧可以用于简化线性的验证算法吗？3.随机化策略已经被证明可以用于优化最大流最小割问题。那么它是否可以用于其他网络优化(networkoptimization)问题，例如最短路？ReferencePaper:1.VerificationandSensitivityAnalysisofMinimumSpanningTreesinLinearTime=summon2.ARandomizedLinear-TimeAlgorithmtoFindMinimumSpanningTrees:3.MinimumSpanningTreeVerificationInLinearTimeComplexity~idddo/mstverif.pdfTHANKSPresentation