蚁群算法求解直径约束最小生成树问题  

Ant Colony Algorithm for Bounded Diameter Minimum Spanning Tree Problem

作　　者：石磊[1] 冯祖针[1] 杨建强[1] 

机构地区：[1]红河学院数学学院,云南蒙自661100

出　　处：《红河学院学报》2012年第4期16-18,共3页Journal of Honghe University

摘　　要：给定无向赋权图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..

关 键 词：蚁群算法 直径约束最小生成树 直径约束 

分 类 号：O157.6[理学—数学]