Problema da árvore de Steiner

O problema da árvore de Steiner, problema da auto-estrada, ou problema da árvore mínima de Steiner, denominado em referência a Jakob Steiner, é um problema de otimização combinatória, que pode ser formulado em uma série de configurações, com a parte comum, sendo que é necessário para encontrar a menor interconexão para um determinado conjunto de objetos. O problema da árvore de Steiner é superficialmente semelhante ao problema da árvore de extensão mínima: dado um conjunto V de pontos (vértices), interligá-los através de uma rede (grafo) de menor tamanho, onde o comprimento é a soma dos comprimentos de todas as arestas. A diferença entre o problema da árvore de Steiner e o problema da arvore de extensão minima é que, na árvore de Steiner, vertices intermediários e arestas intermediárias podem ser adicionados ao grafo, a fim de reduzir o comprimento da árvore de expansão. Esses novos vértices introduzidos para diminuir o comprimento total da ligação são conhecidos como pontos de Steiner ou vértices de Steiner. Foi provado que a ligação resultante é uma árvore, conhecida como a árvore de Steiner. Podem existir várias árvores de Steiner para um determinado conjunto de vértices iniciais. O problema da árvore de Steiner tem aplicações em layout de circuito ou em projeto de rede. A maioria das versões do problema da árvore de Steiner são NP-completos. Na verdade, um deles estava entre os 21 problemas originais NP-completos de Karp . Alguns casos restritos podem ser resolvidos em tempo polinomial. Na prática, são utilizadas heurísticas.