Resumen de Métodos heurísticos para el problema de Steiner en grafos
Pere Guitart Colom
El problema de Steiner en Grafos (PSG) e sun problema de optimización combinatoria clásico perteneciente a la clase NP-hard y, por lo tanto, son necesarios métodos heurísticos para obtener aproximaciones al óptimo enun tiempo razonable, Aquellos métodos heurísticos que compiten para obtener los mejores resutlados realizan un número relativamente alto de ejecucciones de un algoritmo simple, o algoritmo de base, con el fin de obtener una solución mejor. Los dos alforitmos de base más comúnmente usados son la Shortest Path Heuristic (SPH), propuesta por Takahaski y Matsuyama en 1980, yla Distance Network Heuristic (DNH), propuesta por Choukhmane en 1978,a pesar de que suele ariburise a Kou et al. (1981).
Los dos objetivos pricipales de la tesis son el diseño y la construcción de métodos competitivos para el PSG, y el estudio y mejora de la SPH y la DNH. Se han propuesto dos nuevos métodos competitivos cuyos resutlados experimentales, cuando se utilizan las instancias de prueba más comunes, superan los de los mejores métodos conocidos.El primero es un algoritmo genético (AG) que mejora el propuesto por Esbensen en 1995 el cual, a su vez, es una neuva versióndle AG propeusto por Kapsalis et al. En 1993.
Es de destacar el análisis del funcionamiento del algoritmo de forma independiente a us interpretación en clave genética.El segundo es un método iterativo basado en la SPH e incluye algunas funciones que pueden ser utilizadas para mejorar otros méodos.
En cuanto al segundo objetivo, se han propuesto una nueva implementación de la SPH que reduce su complejidad, y dos nuevas variantes de este algoritmo que mejoran su rendimiento.todas ellas pueden ser utilizadas para incrementar el rendimiento de los métodos competitivos basados enla SPH o en la DNH.
