Problema de satisfacción de restricciones

Formalmente, un problema de satisfacción de restricción es definido como un triplo ${\displaystyle \langle X,D,C\rangle }$, donde ${\displaystyle X}$ es un conjunto de variables, ${\displaystyle D}$ es el dominio de valores, y ${\displaystyle C}$ es un conjunto de restricciones. Toda restricción ${\displaystyle c\in C}$ es un par ${\displaystyle \langle t,R\rangle }$ (usualmente representado como una matriz), donde ${\displaystyle t}$ es una ${\displaystyle n}$-Tupla de variables y ${\displaystyle R}$ es una relación ${\displaystyle n}$-aria en ${\displaystyle D}$. Una evaluación de las variables es una función del conjunto de variables al dominio de valores, ${\displaystyle v:X\rightarrow D}$. Una evaluación ${\displaystyle v}$ satisfice una restricción ${\displaystyle \langle (x_{1},\ldots ,x_{n}),R\rangle }$ si ${\displaystyle (v(x_{1}),\ldots ,v(x_{n}))\in R}$. Una solución es una evaluación que satisfice todas las restricciones.

Los problemas de satisfacción de restricciones en un dominio finito son resueltos típicamente usando una forma de algoritmo de búsqueda. Las técnicas más usadas son variantes de búsqueda con retroceso cronológico (backtracking), propagación de restricciones, y búsqueda local.

Vuelta atrás es un algoritmo recursivo. Mantiene una asignación parcial de las variables. Inicialmente, todas las variables están sin asignar. En cada paso, una variable es seleccionada, y todos los posibles valores son asignados a la variable por turnos. Por cada valor, la consistencia de la asignación parcial es chequeada con respecto a las restricciones; en caso de consistencia, un llamado recursivo es hecho. Cuando todos los valores fueron probados, el algoritmo hace backtracking. En este algoritmo básico con retroceso cronológico, la consistencia es definida como la satisfacción de todas las restricciones donde las variables estén asignadas. Existen algunas variantes de backtracking. Backmarking mejora la eficiencia del chequeo de consistencia. Backjumping permite guardar parte de la búsqueda por backtracking "más de una variable" en algunos casos. Aprendizaje por restricciones infiere y guarda nuevas restricciones que pueden ser usadas luego para evitar parte de la búsqueda. Look-ahead es también a menudo usado en backtracking para intentar prever el efecto de seleccionar una variable o un valor, por lo tanto, determinar a veces con anticipación cuándo es satisfasible o insatisfasible un subproblema.

Las técnicas de propagación de restricciones son métodos usados para modificar un problema de satisfacción de restricciones. Más específico, son métodos que fuerzan una forma de consistencia local, que son condiciones relacionadas con la consistencia de un grupo de variables y/o restricciones. Propagación de restricción tiene varios usos. Primero, cambia el problema en otro que es equivalente pero usualmente más simple de resolver. Segundo, puede probar la satisfacibilidad o la insatisfacibilidad de problemas. En general no hay garantía de que esto ocurra; sin embargo, siempre ocurre para algunas formas de propagación de restricción y/o para algunos tipos de problemas específicos. Las formas más conocidas y usadas de consistencia local son consistencia de arco, consistencia de híper arco, y consistencia de camino. El método de propagación de restricción más popular es el algoritmo AC-3, el cual asegura consistencia de arco.

Los métodos de búsqueda local son algoritmos de satisfacibilidad incompleta. Ellos pueden encontrar una solución al problema, pero pueden no encontrarle incluso si el problema es satisfasible. Ellos trabajan mejorando iterativamente una asignación completa de las variables. En cada paso, un grupo pequeño de variables les son cambiados los valores, con el objetivo fundamental de incrementar el número de restricciones que satisfacen la actual asignación. El algoritmo de Min-Conflictos es específico de búsqueda local para CSPs basado en ese principio. En la práctica, búsqueda local parece funcionar bien cuando estos cambios son también afectados por una selección aleatoria.

El modelo clásico de Problema de Satisfacción de Restricciones define un modelo estático, inflexible de restricciones. Este modelo rígido es un defecto que lo hace difícil para representar problemas fácilmente.[2] Varias modificaciones a la definición básica de CSP han sido propuestas para adaptar el modelo a una amplia variedad de problemas.

• Programación declarativa
• Programación con restricciones

• Steven Minton, Andy Philips, Mark D. Johnston, Philip Laird (1993). «Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems» (PDF). Journal of Artificial Intelligence Research 58: 161-205. (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).

• CSP Tutorial

• Tsang, Edward (1993). Foundations of Constraint Satisfaction. Academic Press. ISBN 0-12-701610-4
• Chen, Hubie (December 2009). «A Rendezvous of Logic, Complexity, and Algebra». ACM Computing Surveys (ACM) 42 (1): 1-32. doi:10.1145/1592451.1592453. Open-access 2006 Version
• Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 1-55860-890-7
• Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press. ISBN 0-521-82583-0
• Lecoutre, Christophe (2009). Constraint Networks: Techniques and Algorithms. ISTE/Wiley. ISBN 978-1-84821-106-3
• Tomás Feder, Constraint satisfaction: a personal perspective, manuscript.
• Constraints archive
• Forced Satisfiable CSP Benchmarks of Model RB Archivado el 25 de enero de 2021 en Wayback Machine.
• Benchmarks -- XML representation of CSP instances
• Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning, Ian Miguel - slides.
• Constraint Propagation - Dissertation by Guido Tack giving a good survey of theory and implementation issues