CSP

TRABAJO FIN DE GRADO Grado en Ingeniería Informática

Sistemas de Restricciones: Fundamentos y Aplicaciones.

Autor: Álvaro Martín Boza Tutor: Gonzalo A. Aranda Corral

RESUMEN

Resumen En nuestro día a día tratamos de resolver diferentes actividades que presentan ciertas condiciones. La tarea de generar un horario para la universidad consta de una serie de especi�- caciones que se han de cumplir. Se pensar�a en distintos aspectos como que, por ejemplo, un mismo profesor no puede estar presente en dos aulas a la vez. A esto lo conoceremos como restricciones, que pueden entrar en con icto o necesitar de otras restricciones previas. Como puede pasar durante la generaci�on del horario, existen diferentes alternativas que pueden llevar a satisfacer m�as a unas restricciones que a otras, por ello es importante tener un buen rango de opciones que nos permita encontrar la �optima. Este problema lo podemos resolver f�acilmente mediante la programaci�on de restricciones (PR), la cual permite describir y solucionar problemas combinatorios y de optimizaci�on. La idea principal es resolver un problema sujeto a unas restricciones en el dominio del problema y encontrar distintas soluciones que satisfagan todas las restricciones y optimicen el resultado. Podemos encontrar aplicaciones de esta metodolog��a en distintos campos donde se realicen tomas de decisiones, plani�caciones, diagn�osticos, problemas de empaquetamiento, criptograf��as, razonamiento temporal, etc. Estos problemas suelen tener una complejidad bastante alta, normalmente de tipo NP [1]. Sin embargo, esto no impide que los podamos llevar a cabo como problemas de satisfacci�on de restricciones (Constraint Satisfaction Problems - CSP), donde en primer lugar realizar��amos un modelado del problema para despu�es pasar a su resoluci�on usando t�ecnicas CSP. En este trabajo aprenderemos las distintas etapas por las que pasa un problema de este tipo, desde su planteamiento hasta su resoluci�on. "Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it" (E. Freuder)