Diferencia entre revisiones de «CSP»
(→FICHEROS) |
|||
| (No se muestran 9 ediciones intermedias del mismo usuario) | |||
| 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 | + | 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. |
| − | + | ||
| − | mismo profesor no puede estar presente en dos aulas a la vez. A esto lo conoceremos como | + | 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. |
| − | restricciones, que pueden entrar en | + | |
| − | + | 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. | |
| − | puede pasar durante la | + | |
| − | llevar a satisfacer | + | 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 |
| − | rango de opciones que nos permita encontrar la | + | - CSP), donde en primer lugar realizaríamos un modelado del problema para después pasar a su resolución usando técnicas CSP. |
| − | Este problema lo podemos resolver | + | |
| − | (PR), la cual permite describir y solucionar problemas combinatorios y de | + | En este trabajo aprenderemos las distintas etapas por las que pasa un problema de este tipo, desde su planteamiento hasta su resolución. |
| − | 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 | + | "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) |
| − | resultado. Podemos encontrar aplicaciones de esta | + | |
| − | realicen tomas de decisiones, | + | |
| − | + | == FICHEROS == | |
| − | bastante alta, normalmente de tipo NP [1]. Sin embargo, esto no impide que los podamos | + | * Memoria: http://opendatalab.uhu.es/tfgs/csp/memoria.pdf |
| − | llevar a cabo como problemas de | + | ** Problema RCC |
| − | - CSP), donde en primer lugar | + | ** Problema Horarios |
| − | pasar a su | + | |
| − | En este trabajo aprenderemos las distintas etapas por las que pasa un problema de este tipo, | + | |
| − | desde su planteamiento hasta su | + | |
| − | "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) | + | |
Última revisión de 13:32 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[editar]
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)
FICHEROS[editar]
- Memoria: http://opendatalab.uhu.es/tfgs/csp/memoria.pdf
- Problema RCC
- Problema Horarios
