El árbol de Steiner, nombrado en honor a Jakob Steiner, es un problema de optimización combinatoria consistente en buscar la interconexión más corta para un conjunto de elementos dado.

El árbol de Steiner tiene aplicaciones en el diseño de circuitos eléctricos y redes de telecomunicaciones.

Considerando una red de comunicaciones con nodos distinguidos denominados terminales, el problema del árbol de Steiner (STP) refiere al diseño de una subred de mínimo costo que garantice la conectividad entre pares de nodos terminales.

Este problema modela el diseño de redes de comunicaciones que requieren una configuración que asegure la existencia de un camino entre pares de nodos terminales, garantizando un valor mínimo de confiabilidad en la comunicación de datos entre nodos emisores/receptores de información.

El STP forma parte de los problemas clásicos de optimización combinatoria y diversos algoritmos han sido propuestos para su resolución.

Cuando las instancias del problema crecen en tamaño y complejidad, los algoritmos

exactos tradicionales dejan de ser aplicables en la práctica y las técnicas heurísticas de resolución emergen como alternativas viables para obtener resultados de calidad aceptable en tiempos de ejecución moderados.

Sobre los nodos no pertenecientes al conjunto de nodos terminales no se plantean requisitos de conectividad. Estos nodos, llamados nodos de Steiner, pueden formar parte de la solución o no, dependiendo de la conveniencia de utilizarlos.

Más información: es.wikipedia.org