CAJ | 학술논문

给定无向赋权图G和直径约束值D,直径约束最小生成树问题是查找一个直径不超过D最小权重的生成树.当时,其是NP-hard问题.用蚁群算法对其进行求解,设计了一种新的当前节点选择规则.分析和实验表明,基于新的节点选择规则的蚁群算法对直径约束最小生成树问题有较好的求解效果.
급정무향부권도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..