Novel degree constrained minimum spanning tree algorithm based on an improved multicolony ant algorithm (Q1666108)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Novel degree constrained minimum spanning tree algorithm based on an improved multicolony ant algorithm |
scientific article |
Statements
Novel degree constrained minimum spanning tree algorithm based on an improved multicolony ant algorithm (English)
0 references
27 August 2018
0 references
Summary: Degree constrained minimum spanning tree (DCMST) refers to constructing a spanning tree of minimum weight in a complete graph with weights on edges while the degree of each node in the spanning tree is no more than \(d\) (\(d\geq 2\)). The paper proposes an improved multicolony ant algorithm for degree constrained minimum spanning tree searching which enables independent search for optimal solutions among various colonies and achieving information exchanges between different colonies by information entropy. Local optimal algorithm is introduced to improve constructed spanning tree. Meanwhile, algorithm strategies in dynamic ant, random perturbations ant colony, and max-min ant system are adapted in this paper to optimize the proposed algorithm. Finally, multiple groups of experimental data show the superiority of the improved algorithm in solving the problems of degree constrained minimum spanning tree.
0 references
0 references