Steinerovy problémy a přibližné metody jejich řešení

Steiner Tree Problems and Approximation Methods for Their Solution

journal article - other

en

The aim of this paper was to describe Steiner tree problems, which are an important subset of mimimal network tasks. The only criterion that we used was total length of the network or the total costs for its creating. In spite of their broad application area, Steiner problems are not studied in the Czech literature, which is evidenced by the references. Graph theory books only note these problems as a special case of the mimimum spanning tree problem or even do not mention them at all. We have tried to deal with he problems in this area in a clear way. It refers to tens of other papers often written in a very sketched form, e.g. proofs are very brief, incomplete or not quite general (e.g. the proof of NP-completeness of the RStMTP. Many theorems were formulated and proved by the author without an analogy to literature. The aim was to explain all Steiner tree problems in the same way as the foreign authors often specialize, e.g. Hwang, Warme and Zachariasen in the geometrical problems (rectilinear and Euclidean), Ganley and Robins in the rectilinear one, Voss and Hougardy to the Steiner problem in graphs, Zelikovsky in the rectilinear and graphical problem, etc. Further, in a simple way, it was proved that Eppstein's proof of the Steiner ratio for rectilinear problem is incorrect and its correct modification was proposed [Šeda-Mendel01} based on the original strategy of two spanning trees, however, their different topology does not exceed the bound of 1.50 for the Steiner ratio. Time complexities of many algorithms were recalculated with respect to the use of effecient data structures, e.g. the implementation of priority queues by a binary heap decreased the time complexity of Jarník's and Dijkstra's algorithm and this was projected into two approximation algorithms for Steiner tree problem in graphs. Due to the NP-completeness of the Steiner tree problems, it was not possible to determine an exact solution for large instances. Using a new mathematical model it was shown that even the professional optimization package GAMS (probably based on Branch and Bound Method) can solve only small instances with no more than 50 vertices. On the other hand, a general applicability of metaheuristics for all Steiner tree problems was not confirmed. They surely cannot be recommended for the rectilinear problem, but are promising for the Steiner problem in graphs where the Steiner ratio is high. As for the Euclidean Steiner tree problem its Steiner ratio 2/sqrt(3). shows that the approximation by the Euclidean minimum spanning tree is a very good initial solution and its improvement by simple deterministic heuristic presented here is quite sufficient. In future, we will try to generalize these problems to the fuzzy case where weights of edges will be given by fuzzy numbers. As yet an algorithm has been implemented determining the shortest path with distances described by fuzzy numbers [Šeda-Zittau01], which will be used for a fuzzy variant of the graphical Steiner tree problem.

Cílem práce bylo podat výklad Steinerových problémů, které tvoří významnou podmnožinu úloh zaměřených na hledání minimálních sítí. Jediným kritériem, které zde bylo použito, byla délka (popř. náklady na zřízení) výsledné sítě. Přes velký význam je problematika Steinerových stromů v české literatuře zatím zcela opomíjena, jak je patrné i ze seznamu odkazů. V učebnicích teorie grafů se informace nejčastěji omezují pouze na několikařádkovou poznámku popisující Steinerův problém jako variantu problému hledání minimální kostry anebo zcela chybí. Záměrem bylo podat srozumitelným způsobem ty partie zkoumané problematiky, které se v originále odkazují na desítky jiných pramenů, resp. jsou uvedeny velmi zhuštěným způsobem (např. v důkazu věty je uvedeno, že tvrzení plyne z věty 3, lemmat 4,5, věty 6 a důsledku 7, popř. jsou zcela ponechány na laskavém čtenáři) anebo v nedostatečně obecné podobě (např. důkaz NP-úplnosti rektilineárního problému). Řada vět, lemmat a tvrzení byla autorem formulována a dokázána bez přímé analogie na studovanou literaturu, a to tak, aby výklad Steinerova problému v grafech, rektilineárního Steinerova problému a euklidovského Steinerova problému byl strukturálně jednotný. Renomovaní autoři jsou totiž velmi často specializováni, např. Hwang, Warme a Zachariasen na geometrické varianty problému (rektilineární a euklidovský), Ganley a Robins na rektilineární problém, Voss a Hougardy na problém v grafech, Zelikovsky na rektilineární problém a problém v grafech apod. Mimo jiné na jednoduchém příkladě byl vyvrácen Eppsteinův důkaz pro určení Steinerova poměru při aproximaci rektilineárního Steinerova minimálního stromu rektilineární minimální kostrou a byla navržena jeho modifikace, která vychází z jeho strategie konstrukce dvou koster, jejich odlišně navržená topologie však v žádném případě neporušuje mez 1.50 pro poměr chování. Časová složitost některých algoritmů byla "přepočítána" s přihlédnutím k použitým efektivním datovým strukturám. Konkrétně se to týká použití prioritní fronty implementované binární haldou, což umožnilo zmenšit časovou náročnost Jarníkova a Dijkstrova algoritmu, a to se pak promítlo do dvou aproximativních algoritmů pro hledání Steinerova minimálního stromu v grafu. Protože, rozhodovací verze Steinerových problémů patří do třídy NP-úplných problémů, přesné řešení bylo možné očekávat pouze pro malé rozsahy dat. Na autorem navrženém matematickém modelu se prokázalo, že i profesionální softwarový nástroj GAMS (patrně založený na metodě větví a mezí) není schopen v dostupném čase přesně vyřešit Steinerův problém v grafech s více jak 50 vrcholy. Na druhé straně (poněkud v rozporu s očekáváním autora po zkušenostech s jejich nasazeních v problémech rozvrhování) se nepotvrdila obecná použitelnost metaheuristik pro všechny Steinerovy problémy. Rozhodně je nelze doporučit pro rektilineární problém. Svůj význam mají především u grafické verze Steinerova problému, kde Steinerův poměr i těch nejlepších aproximativních algoritmů je nepříznivý. U euklidovského Steinerova problému jeho Steinerův poměr 2/sqrt(3) ukazuje, že aproximace minimální kostrou je natolik dobrým přiblížením Steinerově minimálnímu stromu, že stačí výchozí řešení zlepšit jednoduchou deterministickou heuristikou.

The aim of this paper was to describe Steiner tree problems, which are an important subset of mimimal network tasks. The only criterion that we used was total length of the network or the total costs for its creating. In spite of their broad application area, Steiner problems are not studied in the Czech literature, which is evidenced by the references. Graph theory books only note these problems as a special case of the mimimum spanning tree problem or even do not mention them at all. We have tried to deal with he problems in this area in a clear way. It refers to tens of other papers often written in a very sketched form, e.g. proofs are very brief, incomplete or not quite general (e.g. the proof of NP-completeness of the RStMTP. Many theorems were formulated and proved by the author without an analogy to literature. The aim was to explain all Steiner tree problems in the same way as the foreign authors often specialize, e.g. Hwang, Warme and Zachariasen in the geometrical problems (rectilinear and Euclidean), Ganley and Robins in the rectilinear one, Voss and Hougardy to the Steiner problem in graphs, Zelikovsky in the rectilinear and graphical problem, etc. Further, in a simple way, it was proved that Eppstein's proof of the Steiner ratio for rectilinear problem is incorrect and its correct modification was proposed [Šeda-Mendel01} based on the original strategy of two spanning trees, however, their different topology does not exceed the bound of 1.50 for the Steiner ratio. Time complexities of many algorithms were recalculated with respect to the use of effecient data structures, e.g. the implementation of priority queues by a binary heap decreased the time complexity of Jarník's and Dijkstra's algorithm and this was projected into two approximation algorithms for Steiner tree problem in graphs. Due to the NP-completeness of the Steiner tree problems, it was not possible to determine an exact solution for large instances. Using a new mathematical model it was shown that even the professional optimization package GAMS (probably based on Branch and Bound Method) can solve only small instances with no more than 50 vertices. On the other hand, a general applicability of metaheuristics for all Steiner tree problems was not confirmed. They surely cannot be recommended for the rectilinear problem, but are promising for the Steiner problem in graphs where the Steiner ratio is high. As for the Euclidean Steiner tree problem its Steiner ratio 2/sqrt(3). shows that the approximation by the Euclidean minimum spanning tree is a very good initial solution and its improvement by simple deterministic heuristic presented here is quite sufficient. In future, we will try to generalize these problems to the fuzzy case where weights of edges will be given by fuzzy numbers. As yet an algorithm has been implemented determining the shortest path with distances described by fuzzy numbers [Šeda-Zittau01], which will be used for a fuzzy variant of the graphical Steiner tree problem.

Minimum spanning tree, Steiner tree, metaheuristic, approximation

2001

01.11.2001

1213-418X

Habilitační a inaugurační spisy

64

XI

26