Redes neuronales como heurísticas para resolver problemas NP-completos

Abstract

Los problemas NP-completos representan uno de los desafíos más significativos en el campo de la informática. Estos problemas son de gran importancia en la vida real, ya que abarcan una amplia gama de aplicaciones prácticas, desde la planificación de rutas en sistemas de navegación hasta la optimización de distintos tipos de recursos. En este proyecto, se aborda la resolución de problemas NP-completos utilizando redes neuronales, explorando un enfoque innovador a través de la inteligencia artificial, cuya tendencia actual se encuentra en auge. Mediante la aplicación de redes neuronales, que han demostrado ser eficaces en tareas de optimización y reconocimiento de patrones, se busca desarrollar una herramienta heurística que ofrezca nuevas vías para abordar estos retos computacionales, o ayuden a los métodos actuales. El proyecto se estructura en dos enfoques principales: el uso de redes neuronales para mejorar soluciones subóptimas iniciales y el entrenamiento de modelos de red neuronal para aprender directamente a resolver problemas NP-completos utilizando únicamente la instancia del problema. A través de estos métodos, se espera no solo generar soluciones prometedoras, sino también analizar la complejidad inherente a los problemas NP-completos y cómo las técnicas de aprendizaje automático pueden ser aplicadas para manejar esta complejidad de manera efectiva.NP-complete problems represent one of the most significant challenges in the field of computer science. These problems are of great importance in real life, encompassing a wide range of practical applications, from route planning in navigation systems to the optimization of different types of resources. In this project, we address the resolution of NP-complete problems using neural networks, exploring an innovative approach through artificial intelligence, which is currently a growing trend. Through the application of neural networks, which have proven to be effective in optimization tasks and pattern recognition, we aim to develop a heuristic tool that provides new ways to address these computational challenges, or help current methods. The project is structured in two main approaches: the use of neural networks to improve initial suboptimal solutions and the training of neural network models to directly learn to solve NP-complete problems using only the problem instance. Through these methods, we seek not only to generate promising solutions, but also to analyze the inherent complexity of NP-complete problems and how machine learning techniques can be applied to manage this complexity effectively.