期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

蚁群算法求解直径约束最小生成树问题 被引量：1

Ant Colony Algorithm for Bounded Diameter Minimum Spanning Tree Problem
下载PDF
导出
摘要 给定无向赋权图G和直径约束值D,直径约束最小生成树问题是查找一个直径不超过D最小权重的生成树.当时,其是NP-hard问题.用蚁群算法对其进行求解,设计了一种新的当前节点选择规则.分析和实验表明,基于新的节点选择规则的蚁群算法对直径约束最小生成树问题有较好的求解效果. Given a connected, weighted, undirected Rraph G and a bound D, The bounded diameter minimum spanningtree problem sought a spanning tree on G of mintmurn weight among the trees in which no path between two -vertices contains more than D edges. This problem was NP-hard for 4≤D ≤│V│-1. Ant colony algorithm was designed for the bounded diameter minimum spanning tree problem, which based on new node-selection strategy. The algorithm was proved to be effective by analysis and experiments..
作者 石磊 冯祖针 杨建强
机构地区 红河学院数学学院
出处 《红河学院学报》 2012年第4期16-18,共3页 Journal of Honghe University
关键词 蚁群算法 直径约束最小生成树 直径约束 ant colony algorithm： bounded diameter minimum spanning tree： bounded diameter
分类号 O157.6 [理学—基础数学]
  • 相关文献

参考文献9

  • 1Cho J,Breen J.Analysis of the performance of dynamic multicastrouting algorithms[J].Computer Communications,1999,22(7):667-674..
  • 2Flajolet P,Gao Z,Odlyzko A.The distribution of heights of binarytrees and other simple trees[J].Probability and Computing,1992,42:243-248.
  • 3M.R.Garey,D.S.Johnson.Computers and Intractability:AGuide to the Theory of NP-Completeness[M].New York:W.H.Freeman,1979:206-218.
  • 4Narsingh Deo,Ayman Abdalla.Computing a Diameter-ConstrainedMinimum Spanning Tree in Parallel[J].Lecture Notes in ComputerScience,2000,1767:17-31.
  • 5Raidl G.R,Julstrom B.A.Greedy heuristics and an evolutionaryalgorithm for the bounded-diameter minimum spanning treeproblem[C].Florida:Proceedings of the 2003 ACM Symposiumon Applied Computing,2003.
  • 6Julstrom B.A,Raidl G.R.A permutation-coded evolutionaryalgorithm for the bounded-diameter minimum spanning treeproblem[C].Chicago:Genetic and Evolutionary ComputationConference’s Workshops Proceedings,2003.
  • 7Gunther Raidl,Ulrich Pferschy.Exact and Heuristic ApproachesforSolvingtheBoundedDiameterMinimumSpanningTreeProblem[M].Vienna:InstituteofComputerGraphicsandAlgorithms,2009.
  • 8Colorni A,Dorigo M,Maniezzo V.Distributed optimization byant colonies[C].Paris:Proceedings of the 1st European Conferenceon Artificial Life,1991:134-142.
  • 9李士勇,陈永强,李研.蚁群算法及应用[M].哈尔滨工业大学出版社,2004:19.

同被引文献17

  • 1Gary.Chartrand,PingZhang,著.范益政,汪毅,龚世才,等译.图论导引[M].北京:人民邮电出版社,2007.81-86.
  • 2Binh. H. T. T, McKay. R. I, Nghia. N. D , etc. New Heuristic and Hybrid Genetic Algorithm for Solving the Bounded Di- ameter Minimum Spanning Tree Problem, in Proceedings of Annual Conference on Genetic and Evolutionary Computation [ J ]. Montreal, 2009,25 (5): 373 - 380.
  • 3Garey M. R, Johnson D. S. Computers and Intractability: a Guide to the Theory of NP - Completeness [ J ]. SIAM Re- view,1982,24( 1 ) : 90 -91.
  • 4Achuthan. N. R, Caccetta L, Caccetta P, etc. Computational Methods for the Diamter Restricted Minimum Weight Span- ning Tree Problem[J]. Australian Journal of Combinatorics, 1994,10 (2) :379 - 384.
  • 5Gouveia. L, Magnanti T. L, Requejo C. A2 - Path Approach for Odd Diameter Constrained Minimum Spanning and Stei- her Trees [ J ]. Networks, 2004,44 (4) :254 - 265.
  • 6Gruber. M , Raidl G. R. A new 0 - 1 ILP Approach for the Bounded Diameter Minimum Spanning Tree Problem, in Pro- ceedings of the Second International Network Optimization Conference [ J ]. Vienna, 2005,15 (3) : 1 - 8.
  • 7Deo. N, abdalla. A. Computing a Diameter - constrained Minimum Spanning Tree in Parallel [ J ] Lecture Notes in Computer Science, 2000,15 ( 4 ) : 17 - 31.
  • 8Julstrom B A. Greedy Heuristic for the Diameter - Con- strained Minimum Spanning Tree Problem [ J ]. Journal of Mathemation Sciences ,2009,161 (6) : 930 - 943.
  • 9Alok Singh Ashok K. Gupta. Improved Heuristics for the Bounded -diameter Minimum Spanning Tree Problem[ J]. Soft Computer,2007,11 (10) : 911 -921.
  • 10Raidl G. R,Julstrom B. A. Greedy Heuristics and an Evolu- tionary Algorithm for the Bounded - Diameter Minimum Spanning Tree Problem [ J ]. Proceeding of the 2003 ACM Symposium on Applied Computing, 2003,102 ( 5 ) : 747 - 752.

引证文献1

红河学院学报
2012年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部