Aplikace Steinerových stromů v síťové optimalizaci

Applications of Steiner Trees in Network Optimization

conference paper

cs

Steinerův problém v grafech reprezentuje hledání stromu minimální ceny, který spojuje definovanou podmnožinu vrcholů grafu. Tento problém zobecňuje problém minimální kostry grafu, je však mnohem složitější, protože řešení může obsahovat i vrcholy, které nepatří do základní množiny vrcholů. Zatímco pro řešení problému minimální kostry existují jednoduché algoritmy polynomiální složitosti, Steinerův problém v grafech patří mezi tzv. NP-těžké problémy a jeho přesné řešení pro úlohy většího rozsahu nelze získat v reálném čase. Steinerův problém v grafech a jeho varianty (Steinerův problém v euklidovské rovině a rektilineární Steinerův problém) mají řadu praktických aplikací, např. v návrhu telekomunikačních sítí, v návrhu VLSI obvodů a v některých speciálních úlohách (multicast routing, file replication problem). Příspěvek se zabývá řešením problému pomocí stochastických heuristických metod.

Steinerův problém v grafech reprezentuje hledání stromu minimální ceny, který spojuje definovanou podmnožinu vrcholů grafu. Tento problém zobecňuje problém minimální kostry grafu, je však mnohem složitější, protože řešení může obsahovat i vrcholy, které nepatří do základní množiny vrcholů. Zatímco pro řešení problému minimální kostry existují jednoduché algoritmy polynomiální složitosti, Steinerův problém v grafech patří mezi tzv. NP-těžké problémy a jeho přesné řešení pro úlohy většího rozsahu nelze získat v reálném čase. Steinerův problém v grafech a jeho varianty (Steinerův problém v euklidovské rovině a rektilineární Steinerův problém) mají řadu praktických aplikací, např. v návrhu telekomunikačních sítí, v návrhu VLSI obvodů a v některých speciálních úlohách (multicast routing, file replication problem). Příspěvek se zabývá řešením problému pomocí stochastických heuristických metod.

Steiner tree problem in graphs represents searching of minimal tree that connects a given subset of graph vertices. This problem generalises the minimum spanning tree problem but it is much more complicated because its solution can include also additional vertices that do not belong into the given set of vertices. While there are simple polynomial algorithms for solving minimum spanning tree problem, Steiner tree problem in graphs and its modifications (Steiner tree problem in the Euclidean plane and rectilinear Steiner tree problem) have many practical applications, e.g. in design of telecommunication networks, VLSI design and special tasks such as multicast routing and file replication problem. This paper deals with solving the problem using stochastic heuristic methods.

Steiner tree, spanning tree, stochastic heuristics

01.06.2000

Univerzita Pardubice

Kouty na Desnou

80-7194-271-5

Proceedings of the 4th International Scientific-Technical Conference PROCESS CONTROL 2000 (ŘÍP 2000)

1