En algoritmos , el problema del árbol de Steiner es un problema de optimización combinatoria . Lleva el nombre del matemático Jakob Steiner . Este problema está cerca del problema del árbol de expansión mínimo y tiene aplicaciones en el diseño de redes, incluidos los circuitos electrónicos y las telecomunicaciones .
Hay varias variaciones del problema.
En un espacio métrico, dado un conjunto de puntos P , un árbol para P es una red (es decir, un conjunto de caminos conectados) tal que todos los puntos están conectados, y se dice que un árbol es el árbol de Steiner si la longitud total de la red es mínimo.
En la variante euclidiana del problema, el espacio métrico es un espacio euclidiano .
El marco más clásico en la optimización combinatoria es el siguiente: dado un gráfico G , cuyas aristas tienen pesos, y un subconjunto S de vértices de G , encuentre un conjunto de aristas de peso mínimo tal como la armadura del subgrafo está conectada y contiene todos los vértices S .
En ambos problemas, dado un conjunto V de vértices, se trata de encontrar un árbol A de costo mínimo que conecte todos los vértices de V (donde el costo del árbol se define como la suma del costo de sus aristas). A diferencia del problema del árbol de expansión mínimo donde todos los vértices del árbol A deben estar en V, en el problema del árbol de Steiner se permite usar puntos fuera de V.
Hay diferentes restricciones que se pueden aplicar al árbol. La mayoría de los problemas son NP-completos (por lo tanto, se consideran difíciles de calcular). Algunos casos Son solubles en tiempo polinomial . Existen algoritmos de aproximación para el problema, por ejemplo, se puede obtener una aproximación (2-2 / | S |) calculando un " árbol de expansión terminal de costo mínimo ", es decir, un árbol que cubre en un gráfico adecuado.
Uno de los algoritmos más conocidos es el proporcionado por Melzack en 1961 consistente en el problema de tres vértices planteado por Fermat, resuelto por el matemático italiano Evengelista Torricelli. La idea es reducir el número de puntadas para volver a este problema y luego recuperar las puntadas a medida que avanza. Antes de Melzack no había forma de solucionar un problema con más de 20 puntos. Hasta la fecha, el algoritmo exacto más eficiente parece ser GeoSteiner.