Resumo: O Problema de Steiner consiste em achar a menor árvore que conecta um conjunto de pontos dados. As Árvores Geradoras Mínimas conectam um conjunto de pontos dados e possuem custo mínimo, mas requerem que todas as conexões sejam entre estes pontos. A diferença, no Problema de Steiner, é que se podem utilizar pontos extras, de modo que o custo da árvore gerada seja ainda menor do que o custo da Árvore Geradora Mínima. Nesta dissertação, abordamos o Problema de Steiner Euclidiano e Retilíneo em 3D, sendo o primeiro NP-difícil e o segundo NP-completo. Muitas são as aplicações do Problema de Steiner em 3D: roteamento fios no problema de projeto físico de VLSI, projeto de sistemas para edifícios, projeto de redes de computadores altamente paralelos e aplicações no campo da bioquímica. Propomos três algoritmos heurísticos para cada métrica. Dois destes algoritmos usam a Árvore Geradora Mínima como solução inicial e melhoram este resultado de forma a gerar a Árvore de Steiner. O terceiro usa uma estrutura da geometria computacional conhecida como Grafo de Gabriel. Apresentamos extensivos resultados computacionais dos nossos algoritmos, e comparamos nossos resultados com os da literatura. Utilizamos VRML como nossa interface gráfica em 3D, o que permite uma boa análise da árvore gerada por nossos algoritmos.
Abstract: The Steiner Problem consists in finding the minimum tree that conects a set of points. Minimum Spanning Trees (MST) conect a set of points and have minimum cost, but all the conection are between two of the given points. The difference, in the Steiner Problem, is that one can insert new points, if they reduce the cost of the tree. In this dissertation, we study the Euclidean and Rectilinear Steiner Problem in 3D. There are many aplications for these problems: routing wires in VLSI, design of building services, design of massively parallel computer network and aplications on biochemistry. We propose three heuristic algorithms for each metric. Two of them use the Minimum Spanning Tree as initial solution and improve it to generate the Steiner Tree. The third algorithm uses a structure studied in computational geometry called Gabriel Graph. We present many computational results of our algorithms, and we compare then to other algorithms. We utilize VRML as graphical interface for the solutions. It enables us to see and analyse the output of our algorithms.
Nossas contribuições: