A Heuristic Algorithm for the Steiner Tree Problem in the Euclidean Plane

Euclidean Steiner tree problem is to find the tree with minimal Euclidean length spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set (Steiner points). The problem is NP-hard, so polynomial-time heuristics are desired. We present a novel heuristic for the Euclidean Steiner tree problem. The lgorithm utilizes the straight skeleton of simple polygon to generate candidate Steiner points, and a path heuristic to constructing Steiner minimum tree by using some of the candidate Steiner points in Euclidean plane. We present computational results on the Soukup test problems.

کلیدواژه ها:

Euclidean Steiner Minimal Tree ، straight skeleton of simple polygon ، path heuristic