Algorithm And Application Research Of Steiner Tree Problem In Graphs

The Graphical Steiner Tree Problem(GSTP) is a classical combinatorial optimization problem that appears in many practically important applications. The problem is a NP hard. There are some accurate algorithm,but with the increase of network scale, the algorithm is exponentially running time. In order to get the optimal solution or approximate optimal solution in polynomial time,it is particularly important to search for effective heuristic algorithm.In this paper, the genetic algorithm and the traditional heuristic algorithm is improved, the main work is as follows:1. In view of the basic genetic algorithm using adaptive rules, introduced simulated annealing thought, this paper proposes a hybrid genetic algorithm to solve the problem of minimum Steiner tree. Experimental results show that: Compared with the basic genetic algorithm, the improved hybrid genetic algorithm can speed up the convergence, reduce the number of iterations, the resulting solution is more stable.2. Analysis for a typical heuristic algorithm, this paper proposes a Steiner tree heuristic algorithm based on weighted node. According to the shortest path, the nodes of degree, and regular point connection times calculated node weights. According to the node weights to modify the cost of the shortest path.Through fixed costs add regular point to the shortest path multicast tree, achieve more link sharing, thus reducing the cost of the whole tree.3. In order to simulate real communication network, this paper improves the Waxman algorithm, a random network generation algorithm is designed. Generate simulation network of different sizes by using this algorithm, Using heuristic algorithm to solve the simulation network. The results show that the heuristic algorithm based on weighted node is a better algorithm performance.