The Steiner Tree Problem

Abstract

STEINER TREE refers to a family of optimisation problems, where the goal is to find the shortest network connecting a given set of terminals K. We define the Euclidean and Graph versions of the Steiner tree problem and show the corresponding methods for solving them. The first finite-time algorithm for the EUCLIDEAN STEINER TREE was presented by Melzak in 1961. The algorithm is old, and the goal of this thesis is to present this algorithm in modern terms and discuss some of the computational difficulties. In addition, we present the algorithm of Dreyfus and Wagner for the GRAPH STEINER TREE. The goal is to show that the GRAPH STEINER TREE is much faster to solve, which is an essential result for modern approximation algorithms of the EUCLIDEAN STEINER TREE. To illustrate the complexity of the algorithms, two simple examples are presented in the thesis.

Steiner-puu-ongelma viittaa joukkoon optimointiongelmia, joissa tavoitteena on löytää lyhyin verkko, joka yhdistää annetun joukon pisteitä K. Tässä työssä määritellään Steiner-puuongelma Euklidiselle tasolle ja verkolle, sekä esitetään algoritmit niiden ratkaisemiseen. Lisäksi algoritmien ratkaisemiseen vaadittavien laskutoimitusten lukumäärää arvioidaan.

Vuonna 1961 Zdzislaw Alexander Melzak esitti ensimmäisen ratkaisualgoritmin Euklidiselle Steiner-puulle. Algoritmi esitellään tässä työssä käyttäen modernia termistöä ja geometrisiä rakenteita. Erityisesti halutaan osoittaa, että parhaan ratkaisun rakenteen valitseminen on haastavaa. Toinen työssä esiteltävä algoritmi on verkko-Steiner-puun ratkaiseva algoritmi, jonka Dreyfus ja Wagner esittivät vuonna 1972. Olennaisesti algoritmin ratkaisu-aika on exponentiaalinen joukon K pisteiden määrän suhteen, mutta polynominen verkon solmujen kokonaismäärän suhteen.

Tavoitteena on osoittaa, että verkko-Steiner-puu on huomattavasti helpompi ratkaista kuin Euclidinen Steiner-puu. Tämä on keskeinen tulos likiarvojen löytämiselle moderneilla menetelmillä. Erityisesti polynominen kasvu suhteessa verkon solmujen määrään on hyödyllinen ominaisuus, koska käytännön ongelmissa pisteiden K osuus on pieni verkon kaikista solmuista. Työssä on esimerkit kummankin algoritmin käytöstä havainnollistamaan algoritmien toimintaa ja laskennan vaativuutta.