Show simple item record

El problema de la minimización de la anchura de corte en ordenaciones lineales: Resolución exacta y heurística

dc.contributor.authorGarcía Pardo, Eduardo
dc.date.accessioned2012-12-12T08:33:25Z
dc.date.available2012-12-12T08:33:25Z
dc.date.issued2011
dc.identifier.urihttp://hdl.handle.net/10115/11474
dc.descriptionTesis Doctoral leída en la Universidad Rey Juan Carlos de Madrid en 2011. Director de la Tesis: Dr. D. Abraham Duarte Muñoz y Dr. D. Juan José Pantrigo Fernándezes
dc.description.abstractLa optimización es una disciplina que trata de encontrar solución a problemas de la vida cotidiana. Una gran cantidad de problemas que tienen interés en áreas científicas y tecnológicas pueden ser enunciados como problemas de optimización. Un problema de optimización es aquél en el que, habiendo muchas posibles soluciones y alguna forma clara de comparación entre ellas, se pretende encontrar la mejor de todas, es decir, la solución óptima. Los problemas de Optimización Combinatoria son un tipo de problemas de optimización cuyas soluciones están formadas por números enteros. Existen numerosos problemas de Optimización Combinatoria para los que no se conocen algoritmos capaces de resolverlos en tiempo polinómico. No obstante, dado el interés práctico de muchos de ellos, es necesario disponer de técnicas eficientes para abordarlos. Las técnicas existentes en la actualidad se podrían clasificar en exactas y aproximadas. Las técnicas exactas son capaces de encontrar la solución óptima, pero requieren un tiempo de cómputo elevado, por lo que son inviables cuando el tamaño del problema es grande. De entre las técnicas aproximadas destacan los algoritmos heurísticos, capaces de encontrar soluciones de alta calidad en un tiempo de cómputo razonable, pese a no poder certificar si la solución encontrada es óptima, ni cómo de lejos está de ella. El problema de la minimización de la anchura de corte en ordenaciones lineales es un problema NP-Difícil de Optimización Combinatoria y consiste en encontrar un etiquetado de los vértices de un grafo, de modo que se minimice el máximo número de aristas que sobrepasan el espacio entre cada dos vértices consecutivos, al ordenar los vértices del grafo sobre una línea recta. Este problema tiene aplicaciones en diseño de circuitos, migración y fiabilidad de redes de telecomunicaciones, representación automática de grafos y en recuperación de información. En esta Tesis Doctoral se proponen algoritmos exactos y heurísticos para la resolución del problema de la minimización de la anchura de corte en ordenaciones lineales. Los algoritmos exactos propuestos están basados en la técnica de Ramificación y Acotación, para la que se proponen distintas cotas inferiores y varios recorridos del árbol de exploración. Respecto a los algoritmos heurísticos, se proponen heurísticas constructivas, de mejora y de combinación de soluciones, que son embebidas dentro de un esquema híbrido GRASP con Búsqueda Dispersa. Tanto los algoritmos exactos, como los algoritmos heurísticos, mejoran los resultados obtenidos por los métodos existentes en el estado del arte, sobre los conjuntos de instancias evaluados.es
dc.language.isospaes
dc.publisherUniversidad Rey Juan Carloses
dc.subjectRobótica e Informática Industriales
dc.titleEl problema de la minimización de la anchura de corte en ordenaciones lineales: Resolución exacta y heurísticaes
dc.typeinfo:eu-repo/semantics/doctoralThesises
dc.rights.accessRightsinfo:eu-repo/semantics/openAccesses
dc.subject.unesco1203.04 Inteligencia Artificiales
dc.subject.unesco1203.17 Informáticaes
dc.description.departamentoCiencias de la Computaciónes


Files in this item

This item appears in the following Collection(s)

Show simple item record

Los ítems de digital-BURJC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario