摘要：Given a connected, weighted, undirected graph G and a bound D, the bounded diameter minimum spanning tree (BDMST) problem seeks a spanning tree on G of minimum weight among the trees in which no path between two vertices contains more than D edges. This problem is NP-hard for 4 _ D _ |v| -1. In present paper a new randomized greedy heuristic algorithm for solving BDMST is proposed. An evolutionary algorithm encodes spanning trees as lists of their edges, augmented with their center vertices. It applies operators that maintain the diameter bound and always generate valid offspring trees. These operators are efficient, so the algorithm scales well to larger problem instances. On 25 Euclidean instancesof up to 1000 vertices, the EA improved substantially on solutions found by the randomized greedy heuristic.
Loading...
