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