Proyecto #5
Tema: Árboles de Steiner
¿Qué son los árboles de Steiner?
Son una solucion mas óptima que los árboles EMST (Euclidean Minimum Spanning Tree), de hecho se forman mediante este tipo de árboles pero con la diferencia que para lograr la maxima optimizacion se puede agregar mas vértices. Estos vértices adicionales
se denominan Vértices o Nodos de Steiner.
Mediante estos vértices se busca efectuar una minimización más óptima de los árboles de recubrimiento.
Para lograr esto se deben cumplir los suguientes criterios:
• Las aristas adyacentes concurrentes en un vérticecomún, forman un ángulo por lo menos de
120 grados
• No debe existir cruces de aristas.
• Cada punto de Steiner tiene grado tres, es decir, existen tres aristas que concurren a él.
Consideraciones:
Para un conjunto de N vértices, se tiene como máximo N-2 vértices de Steiner.
Ejemplo de árbol steiner
¿Para que se utilizan los Árboles de Steiner?
Para optimizar las redes de comunicaciones. Uno de los principales problemas en la construción de redes de comunicaciones es el diseño de una topología óptima para la mejor comunicacion entre los pares de nodos.
Tambien son utilizados en redes de transportes.
Complejidad Computacional:
La generación de Árboles de Steiner representa un tipo de problemas en el cual la respuesta es la mejor aproximación, pero el costo computacional es elevado.
En 1973 Karp demostró que el problema del árbol de Steiner es NP-Completo. Desde entonces, diferentes enfoques de métodos heurísticos han sido aplicados para obtener buenas soluciones del problema en tiempos razonables.
Se estan llevando a cabo investigaciones para diseñar e implementar en un "futuro próximo" los métodos heurísticos correspondientes a técnicas evolutivas, que permitan llegar a la optimización de un conjunto de N vértices fuertemente conexo, más allá del obtenido por los árboles EMST, permitiendo obtener inclusive la solución del Problema de Steiner Generalizado.
Autoevaluación: Los Árboles de Steiner son una muy buena aproximacion a la mejor opción, aunque es muy complejo y costoso obtenerla mediante metodos computacionales, pienso que la informacion que les dejo aquí es algo muy bueno para comprender un poco el funcionamiento básico de este tipo de árboles espero que les sea de utilidad.
Si notan algun error me lo hacen saber y pueden dejar comentarios sobre el tema. Gracias!!!
Bibliografía:
En esta pagina hay un applet que muestra el EMST
http://personal.us.es/almar/docencia/practicas/proximidad/emst.htm
http://sisbib.unmsm.edu.pe/bibvirtualdata/publicaciones/risi/n3_2005/a05.pdf
¿A que se refiere con "efectuar minimización más óptima de los árboles de recubrimiento"?
ResponderEliminarAh otra pregunta : ¿puedo poner los nodos donde yo quiera o tienen que ser donde sea la mejor posicion?
Respuesta a Cynthia Telles:
ResponderEliminarSignifica que la suma de las aristas sea la menor y mejor posible, como en la imagen, las aristas que estaban muy largas fueron reducidas colocando los nodos de Steiner.
Y estos se colocan en un lugar apropiado para buscar la mejor otimizacion, claro siguendo las condiciones para los nodos.
Buena la presetnacion de hecho le pude entender porque pase al frente jeje..
ResponderEliminarPero tengo una duda, dices que este algoritmo es un Np duro, mi pregunta es hasta donde se podria calcular en modo computacional sin que tarde mucho tiempo en resolver el problema
saludos...
Respuesta a Abraham:
ResponderEliminarBuena pregunta mira mientras revisaba informacion para el proyecto, en una pagina leí, que se podia calcular con maximo 25 nodos o vertices en un tiempo mas o menos razonable apartir de ahí es muy exagerado lo que tarda.
Bueno el tema, me gusto por las aplicaciones en redes. Una pregunta.Se puede optimizar el algoritmo para que tarde menos en dar resultado después de esos 25 nodos?
ResponderEliminarEspero tu respuesta.
Saludos.
Respuesta a Emmanuel Garcia:
ResponderEliminarGracias!! saludos, mira se esta buscando la manera de hacerlo más eficiente y que pueda resolverse para N nodos, pero no se a conseguido, tan solo se logra una pequena optimizacion con los métodos que se utilizan, pero si alguien lograra lo que parece imposible y creara una mejor solución se volvería famoso y le darian mucho dinero. Y se resolveria el problema de Steiner Generalizado.
Bien.
ResponderEliminar