DSpace Repository

Algoritmos exactos y aproximados para calcular descomposiciones arbóreas de grafos

Show simple item record

dc.contributor.author Bernal Sánchez, José Jorge
dc.date.accessioned 2020-07-16T19:12:49Z
dc.date.available 2020-07-16T19:12:49Z
dc.date.created 2019-08-29
dc.date.issued 2020-03-11
dc.identifier.citation Bernal Sánchez, José Jorge. (2019). Algoritmos exactos y aproximados para calcular descomposiciones arbóreas de grafos (Maestría en Ciencias de la Computación). Instituto Politécnico Nacional, Centro de Investigación en Computación, México. es
dc.identifier.uri http://tesis.ipn.mx/handle/123456789/28247
dc.description Tesis (Maestría en Ciencias de la Computación), Instituto Politécnico Nacional, CIC, 2019, 1 archivo PDF, (42 páginas). tesis.ipn.mx es
dc.description.abstract RESUMEN: Cuando nos enfrentamos a problemas NP-difíciles como el de encontrar una cubierta mínima por vértices en un grafo no nos es posible diseñar algoritmos que resuelvan este tipo de problemas de manera óptima para cualquier instancia arbitraria en tiempo polinomial, por lo que es necesario recurrir a otras estrategias. Justamente, esta tesis describe una nueva técnica para desarrollar algoritmos conocida como programación genética dinámica. Esta nueva herramienta se basa en la integración de algoritmos genéticos junto con ideas de programación dinámica que también están relacionados con los conceptos de descomposiciones arbóreas. Así, la programación genética dinámica consiste en aplicar algoritmos genéticos en grafos, pero modificando los operadores que esta clase de meta-heurísticas usa de tal modo que se usen ideas de programación dinámica como la de dividir el grafo en subproblemas independientes, resolver esos problemas y unir las soluciones obtenidas, considerando a su vez como se conectan dichos subproblemas para poder dar una solución óptima al problema original. Los resultados experimentales basados en muestras aleatorias en grafos conocidos como árboles muestran que la programación dinámica genética logra obtener soluciones que son muy cercanas a la solución óptima en este tipo de grafos. Además de árboles esta técnica se ha usado en otro tipo de grafos y los resultados preliminares también muestran que la meta-heurística desarrollada puede dar soluciones cercanas a la óptima. En conclusión, tenemos que la programación genética dinámica puede ayudar a resolver problemas NP-difíciles en grafos, dando soluciones que se aproximan muy de cerca a las soluciones óptimas. ABSTRACT: When we face NP-hard problems such as finding a minimum vertex cover in a graph, it is not possible to design algorithms that solve these types of problems in an optimal way for any arbitrary instance in polynomial time, so it is necessary to find other alternatives. Precisely, this thesis describes a new technique to develop algorithms known as dynamic genetic programming. This new tool is based on the integration of genetic algorithms along with dynamic programming ideas that are also related to the concepts of tree decompositions. Thus, dynamic genetic programming consists in applying genetic algorithms in graphs, but modifying the operators that this kind of meta-heuristics uses in such a way that dynamic programming ideas such as dividing the graph into independent subproblems are used, solving those problems and joining the solutions obtained, considering in turn how these subproblems are connected in order to provide an optimal solution to the original problem. Experimental results based on random samples in graphs known as trees show that dynamic genetic programming achieves solutions that are very close to the optimal solution in this type of graphs. In addition to trees, this technique has been used in other types of graphs and the preliminary results also show that the meta-heuristic developed can give solutions close to the optimal one. In conclusion, we have that dynamic genetic programming can help solve NP-hard problems in graphs, giving solutions that closely approximate the optimal solutions. es
dc.language.iso es es
dc.subject Programación dinámica es
dc.subject Algoritmos genéticos es
dc.subject Algoritmos heurísticos es
dc.title Algoritmos exactos y aproximados para calcular descomposiciones arbóreas de grafos es
dc.contributor.advisor Menchaca Méndez, Ricardo
dc.contributor.advisor Menchaca Méndez, Rolando


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Browse

My Account