# Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space
## 1 Introduction
### Definitions  
The following definitions and characteristics of ESTP will be used in this paper. They are correct for the Euclidean space \(\mathbb{R}^{n}\) for any \(n\). Points in \(P\) are called terminals, and it is assumed that their count is \(p\). Points in \(S\) are Steiner points. For an optimal solution to the ESTP of size \(p\), the maximum number of Steiner points in the SMT (Steiner Minimum Tree) is \(p-2\). The degree conditions are also met: (1) in the SMT, a terminal from \(P\) can only have a degree of 1, 2, or 3; (2) a Steiner point in the SMT has a degree exactly equal to 3. The angle condition can be formulated as follows: Every Steiner point and the three points it is connected to lie on a plane, and the edges connecting the vertices form angles of 120 degrees. A tree that meets the angle condition is called a Steiner tree. If we fix the number of Steiner points and the way they are connected to vertices from \(P\) but do not determine the location of the Steiner points, we define the Steiner topology. If in a given topology we use the maximum number of Steiner points, which is \(p-2\), then such a topology is called a full Steiner topology (FST). Such a full topology describes a Steiner tree in which each terminal has a degree equal to 1. Figure 1: An example of a minimal spanning tree (**left**) and a minimal Steiner tree (**right**) in 2D. Additional Steiner points are presented as squared marks. Figure 2: An example of a minimal spanning tree (**left**) and a minimal Steiner tree (**right**) in 3D. Additional Steiner points are presented as squared marks. As mentioned, for a given FST (Full Steiner Topology), the positions of the Steiner points are not determined. If these positions are optimized in such a way that the resulting tree has the minimum total edge length, a so-called relatively minimal tree (RMT) for the given topology is formed. If during the optimization process of the Steiner points' positions their locations coincide with terminal points or other Steiner points, then the obtained RMT is referred to as a degeneration of the given topology. An RMT for a given topology always exists. A very important feature of the problem under consideration is the fact that for an SMT (Steiner Minimum Tree) in a given ESTP (Euclidean Steiner Tree Problem), there always exists an FST whose RMT is equal to the given MST. From the above description, a general approach to the ESTP emerges: for a given set \(P\), construct successive FSTs, find their RMTs, and present the smallest of them as the SMT (Steiner Minimum Tree). Many exact algorithms approach the ESTP in this way, trying to limit the number of FSTs checked. A review of these methods can be found in [1]. In this paper, a different approach is proposed. Instead of developing methods to limit the number of FSTs checked, it is assumed that not all of them will be examined. Instead, a genetic algorithm is used to optimize successive FSTs. This is significant, as the space of possible FSTs grows rapidly for successive \(p\). Figure 3 shows an example of an FST for \(p=5\). It is noted that the coordinates of the vertices are not important here, and only their mutual connections matter. This implies that in constructing an FST, the order in which terminals are added to the FST through a Steiner point is crucial. This fact will be utilized in the proposed approach based on the genetic algorithm. On the other hand, Figure 4 provides more details regarding the process of building an FST. Even if the order in which terminals are added to the FST is fixed, it is still possible to construct many different topologies by choosing how the new terminal is connected through a new Steiner point. For three terminals, there is only one unique way to connect them using one Steiner point. Figure 4 further shows that the fourth terminal can be added to the developing FST in three different ways through a new Steiner point. Starting from the initial three edges, adding each subsequent Steiner point and terminal increases the number of edges by 2.