A minimal spanning tree (MST) connects a given set of points in a plane so that the sum of all links is minimal.
Often this sum of all links can be reduced, if additional points are added. These points are called Steiner
points, and the corresponding minimal spanning tree Steiner tree.
For more than 3 points given, it is a hard optimization problem to compute the optimal number and position of
Steiner points.
This app finds Steiner trees using a simple evolutionary algorithm for demonstration purposes.
It uses a
population of individuals that develops towards a solution of the problem in an evolutionary loop:
Each individual initially sets random Steiner points, and constructs the corresponding Steiner tree. The minimal
length of the Steiner tree in the population is stored. Each individual has now a fitness value, which is the
higher the closer its Steiner tree length is to the minimal length of the population. Fitter individuals have
more descendants by reproduction, and less fit individuals die out.
In order to explore better solutions, reproduction does not create descendants that are identical to the parent
individual, i.e. do not have their Steiner points at the same position. Rather these positions are shifted
randomly by mutation, using a Gaussian distribution. How far they are shifted on average is determined also by
their fitness: Good individuals do shift their Steiner points less than worse individuals.
iPhone | Requires iOS 3.0 or later. |
iPad | Requires iPadOS 3.0 or later. |
iPod touch | Requires iPadOS 3.0 or later. |
Mac | Requires macOS 11.0 or later and a Mac with Apple M1 chip. |