Steiner Tree Problem

The generalization of the minimal links problem is known as the Steiner Tree Problem which tries to find the network of minimum length which will connect a given number of points and allowing the selection of arbitrary intermediate points. Below are two Steiner trees for the same set of four points. They correspond to two local minima with the first being the global minimum. The two functions, f1 and f2, are the objective functions and give the sum of the length of the lines in the network. The two intermediate points are based on different choices for circles associated with opposing pairs of points. Pairing points that lie closer together yields the global minimum. Note the honey comb like structure of the trees.