Internal Steiner Tree问题的精确算法OA

The Internal Steiner Tree Problem with wide application value is a branch of the classical Steiner tree problem.In this paper,the mathematical properties of Internal Steiner Tree Problem are proposed from several aspects,such as the relationship between nodes,the degree of nodes and the comparison of the weight of paths between nodes.These mathematical properties can re-duce the size of the problem by determining whether the nodes and edges that satisfy the conditions in the problem are or are not in the optimal solution.Then,based on the mathematical properties,this paper proposes a backtracking algorithm with reduction.At the same time,the upper and lower bound sub-algorithms are used to prune the solution space of the problem.Finally,an example is given to illustrate the steps of the algorithm,and then the complexity of the algorithm is analyzed.