关键词: 三维欧氏Steiner最小树, Delaunay四面体网格, 凸多面体剖分, 智能算法

Abstract: Euclidean Steiner minimum tree problem, a classical NP-hard problem in combination optimization, has been widely studied in many fields. Euclidean Steiner minimal tree problem in 3-space is the generalization of Euclidean Steiner minimum tree problem in 2-space. The research results on Euclidean Steiner minimal tree problem in 3-space have been rarely published because of their difficulties. In this paper, a hybrid intelligent method is designed by using Delaunay tetrahedron mesh generation technology to solve the Euclidean Steiner minimal tree problem in 3-space, which can not only avoid falling into local optima, but also has good effects in solving large scale problems. Promising results are obtained by using this hybrid method coded in MATLAB to solve series of Euclidean Steiner minimum tree problem instances in 3-space.

Key words: euclidean steiner minimum tree problem in 3-space, delaunay tetrahedron mesh generation, convex polyhedron decomposition, intelligent algorithm