Diferencia entre revisiones de «CSP»
(→RESUMEN) |
|||
| Línea 9: | Línea 9: | ||
== RESUMEN == | == RESUMEN == | ||
| − | |||
| − | |||
En nuestro día a día tratamos de resolver diferentes actividades que presentan ciertas condiciones. | 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 especificaciones que se han de cumplir. Se | + | La tarea de generar un horario para la universidad consta de una serie de especificaciones que se han de cumplir. Se pensará 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 conflicto o necesitar de otras restricciones previas. | + | |
| + | A esto lo conoceremos como restricciones, que pueden entrar en conflicto o necesitar de otras restricciones previas. Como puede pasar durante la generación del horario, existen diferentes alternativas que pueden llevar a satisfacer más a unas restricciones que a otras, por ello es importante tener un buen rango de opciones que nos permita encontrar la óptima. Este problema lo podemos resolver fácilmente mediante la programación de restricciones (PR), la cual permite describir y solucionar problemas combinatorios y de optimización. | ||
| + | |||
| + | 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, planificaciones, diagnósticos, 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ón de restricciones (Constraint Satisfaction Problems | ||
| + | - CSP), donde en primer lugar realizaríamos un modelado del problema para después pasar a su resolución usando técnicas CSP. | ||
| + | |||
| + | En este trabajo aprenderemos las distintas etapas por las que pasa un problema de este tipo, desde su planteamiento hasta su resolución. | ||
| − | + | "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) | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | "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) | + | |
Revisión de 13:23 29 abr 2019
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
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 especificaciones que se han de cumplir. Se pensará 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 conflicto o necesitar de otras restricciones previas. Como puede pasar durante la generación del horario, existen diferentes alternativas que pueden llevar a satisfacer más a unas restricciones que a otras, por ello es importante tener un buen rango de opciones que nos permita encontrar la óptima. Este problema lo podemos resolver fácilmente mediante la programación de restricciones (PR), la cual permite describir y solucionar problemas combinatorios y de optimización.
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, planificaciones, diagnósticos, 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ón de restricciones (Constraint Satisfaction Problems - CSP), donde en primer lugar realizaríamos un modelado del problema para después pasar a su resolución usando técnicas CSP.
En este trabajo aprenderemos las distintas etapas por las que pasa un problema de este tipo, desde su planteamiento hasta su resolución.
"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)
