ĐỀ XUẤT CHIẾN LƯỢC TÌM KIẾM LÂN CẬN CHO BÀI TOÁN CÂY STEINER NHỎ NHẤT

Abstract

Steiner Minimum Tree (SMT) is a graph theory optimization problem that has many important applications in science and technology. This is a NP-hard problem. Many approaches have been developed to solve the Steiner Minimum Tree such as algorithms for finding exact solutions, Approximation Algorithms, algorithms heuristic algorithms, metaheuristic algorithms. In which, neighborhood search strategies are decisive for improving the quality solution of metaheuristic algorithms. In this paper, we propose two neighborhood search strategies for the Steiner Minimum Tree problem, and we use these neighborhood search strategies in the context of a variable neighbor search algorithm. Experimental results with the standard experimental data system show that our proposed algorithm offers better quality solution than some existing heuristic algorithms and metaheuristic algorithms on some data sets.