Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2008

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Equivalence, Indicators, Quasi-indicators and Optimal Steiner Topologies on Four Points in Space

Weng J.F., Smith J.MacGregor, Brazil M., Thomas D.A.

Fundamenta Informaticae

2008

Vol. 84, nr 1

135-149

The Steiner tree problem is an intractable optimization problem, which asks for a network, in fact a tree, interconnecting a given point set V in a metric space and minimizing the total length of the network. The tree topology t of the network is called a Steiner topology and a tree T with minimum length with respect to its Steiner topology is called a Steiner tree. As a combinatorial optimization problem, the Steiner tree problem asks for a Steiner tree T with minimum length over all possible topologies t on V. It has been proved that if T is in E3 then the length of T cannot be expressed by radicals even when T spans just 4 points. For such optimization problems in which the objective functions do not have closed form solutions the traditional approach is approximation. In this paper we propose a new approach by introducing some new concepts: equivalence, indicators and quasi-indicators, and then we apply these concepts to the Steiner tree problem. Roughly speaking, a quasi-indicator is a function that is simple to compute but indicates with high probability the optimal solution to the original optimisation problem. For a specific optimisation problem - finding the optimal Steiner topologies on 4 points in space, we demonstrate how to find good quasi-indicators. The extensive computational experiments over 5000 random 4-point sets show that the best quasi-indicator for finding optimal Steiner topologies on 4 points in space is not only easy to compute but also extremely successful with less than 1.5% failures in indicating optimal topologies even if degeneracy of Steiner minimal trees exists. Moreover, within the 1.5% cases of failure, the maximum and the average relative error are 1.5% and 0.2% respectively. Therefore, the performance of the proposed Q-indicator is very good and could be applied to the four vertices surrounding any pair of adjacent Steiner points in a Steiner tree on n ( > 4) points in space to make local improvements to the topology of the Steiner minimal tree in space.