论文研究-基于降阶的最小生成树快速算法.pdf

所需积分/C币:9 2019-07-22 18:07:38 253KB .PDF
21
收藏 收藏
举报

在分析最小生成树问题数学性质的基础上,给出了一种基于降阶技术的快速最小生成树算法。该算法采用降阶技术,大大加快了算法的求解速度,在最坏情况下算法的时间复杂度为O(m);另一方面,算法易于找到问题的全部最小生成树。
第6期 熊小华,等:基于降阶的最小生成树快逸算法 2053 在G1中找到仅关联一条最短边的节点,用v表示最短中:Vn={v,vk},Em={(n1,t6)},Wn={2,31,En2={(n2, 边的另一端点 )},Vn={n4,m,n3,1l,n,"10},Fn={(n,n3),(n2,n),(n 将边e=(2,b)添加到T中,并从G1中移除边(",t);D0),(n4,7),(n,v7)}。 若不能在G1中找到仅关联一条最短边的节点,则跳转至 计算得E(1,2)={(v1,n2)},E(1,3)={(n6,),(n 步骤d) Us) Emin=3 跳转至步骤c) 此时可以从E(1,3)中任取一条添加到T中,假定取边 d)//寻找连通各子树的最短割边以构成最小生成树 (v,v3),则此时T的情况如图4所示。 若=n-1则{T”=T,结束整个算法; 由图4知包含两个不连通的子树T1和。其中:Wn= 否则{ n,,n4,1,n,8,,n0},Fn={(n,),(3,2),(,) 找出T中所有不连通的子树,设子树的棵数为 (n3,n),(n,v3)} 按照公式E(i,)计算子树1到其他子树的最短割边(其{(n2,23)}。 ≤i≤k,=1) 计算得E(1,2)={(n,2),(u,l3)Emn=2}。 Fm=分(i,中边的权值最小,2≤j≤k表示与子树1 任取F(1,2)中一条边添加到T中,此时T中边的条数为 连通最短割边权值最小的子树; n-1,即为所求的最小生成树T(图5),则算法结束 从Emn任取一棵子树,记为T,从E(1,r)中任取一条边添 7 加到T中。 跳转至步骤d);} 算法时间复杂度分析 步骤b)在最差情况下的时间复杂度为O(n);步骤灬)在 图4子图T 图5最小生成树T 最坏情况下的时问复杂度为O(m);步骤d)在最坏情况下的 时间复杂度为O(m)。因此整个算法的时间复杂度为O(m)。 由前面的分析可知,在3)中存在两次任取一条最短割边 的情况,两次取边的组合情况如下:(v,),(v,2)},{(t2, 3示例分析 ),(n4,n3)},{(2o,v3),(n,n2)},(ns,v3),(v2,n3)},将这 四种组合情况确定的边加入到2)中处理得到的T,就可以得 为了更清楚地了解算法的原理及应用,下面给出一个示例到题的全部最小牛成树 来进行分析 示例1如图1所示,边上的数字为边的权值。 4结束语 1)处理度为1的节点 Er={(vs,n3),(l,v),(v3,n)},此时G1的情形如图2 本文给出的最小生成树快速降阶算法,相比传统的求最小 所示。 生成树的贪心算法,充分利用最小生成树问题的数学性质来实 现问题的降阶,从而大大提高了问题的求解速度。另一方面 利用本算法可以方便地找到问题的全部最小生成树。 参考文献: [1 AHUJA R K, MAGNA NTI T L, ORLIN J B. Network flows: theory algorithms, and applications( English Version)[M. Beijing: Me chanical Industry Press, 2005: 510-536. 图1图G 图2图G [2 DASGUPTA S, PAPADIMITRIOU C H, VAZIRANI U V. Algorithms [eb/Olj.hllP://www.es.berkeleyedlu/-vazirani/algurithms.hl 2)处理关联的最短边惟一的节点 节点v,D2,D1,D,均为关联惟一一条最短边的节点,将3sYs1oMM,DEoN, KOWALIk J S. Discrete optimization algo 它们关联的最短边分别添加到T上并从G1上移除,此时G1和 rithms: with pascal programs[ M]. New Jersey: Prentice-Hall, 1983 212-236 T的情形如图3(a)和(b)所示。 [4 KARGER D R, KLFIN P N. TARJAN R E. A randomized linea 6 time algorithm to find minimum spanning trees[ J]. Journal of the AcM,1995,42(2):321-328 [5 NEUMANN F, WEGENER I. Randomized local search, evolutionary 3 algorithms, and the minim um spanning tree problem[J]. Theoretical Computer Science, 2007, 378(1): 32-40 [6 LIU Xi-kui, LI Yan, XU Jin. Solving minimum spanning tree prob 4● lem with DNA computing[J]. Journal of Electronics, 2005. 22 (a)图G1 (b)子图T (2):112-117 图3图G1与子图T [7 NEU MANN F, WITT C. Ant colony optimization and the minimum spanning tree problem: learning and intelligent optimiz ation [C// 3)寻找连通各子树的最短割边以构成最小生成树 the 2ud Inle rational Conlerence. Berlin, Heidelberg: Springer 出图3(b)可知T包含三个不连通的子树T1、T2和T。其 Verlag,2007:153-166.

...展开详情
试读 3P 论文研究-基于降阶的最小生成树快速算法.pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-基于降阶的最小生成树快速算法.pdf 9积分/C币 立即下载
1/3
论文研究-基于降阶的最小生成树快速算法.pdf第1页

试读结束, 可继续阅读

9积分/C币 立即下载