Problema de satisfacción de restricciones

Problemas de satisfacción de restricciones (CSP) por sus siglas en inglés, son problemas matemáticos definido como un conjunto de objetos tal que su estado debe satisfacer un número de restricciones o limitaciones. Los CSP representa las entidades de un problema como una colección homogénea finita de restricciones sobre variables, las que son resueltas por métodos de satisfacción de restricciones. Los CSP son el tema de una intensa investigación en Inteligencia Artificial e Investigación de operaciones, dado que la generalidad en su formulación provee un principio básico para analizar y resolver problemas de distintos tipos. Los CSP a menudo muestran gran complejidad, requiriendo una combinación de métodos heurísticos y búsqueda combinatoria para ser resueltos en un tiempo razonable. El Problema de satisfacibilidad booleana (SAT), el Satisfiability Modulo Theories (SMT) y answer set programming (ASP) pueden ser a grandes rasgos modelados como una forma de problema de satisfacción de restricciones.

Ejemplos de problemas sencillos que pueden ser modelados como problema de satisfacción de restricciones.

• Problema de las ocho reinas
• Teorema de los cuatro colores Problema de coloración de mapas
• Sudoku, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato y muchos otros puzzles

De forma general, problemas de restricciones pueden ser más difíciles, y pueden no ser expresables en alguno de estos sistemas simples.

Ejemplos de la vida real son Planeamiento y Asignación de recursos.

Definición formal

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 a el 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.

Resolución de CSP

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.

Retroceso cronológico 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.

Aspectos teóricos de CSP

Problemas de decisión

CSPs son estudiados también en Teoría de la complejidad computacional. Una pregunta importante es si para cada conjunto de relaciones, el conjunto de todos los CSPs que pueden ser representado usando solo las relaciones escogidas de ese conjunto están en P o NP-completo. Si el teorema Dicotomía es verdadero, entonces CSPs provee uno de los subconjuntos más grandes conocidos de NP los que evitan problemas NP-intermedio, cuya existencia fue demostrada por el teorema de Ladner bajo la suposición que P ≠ NP. El teorema de Schaefer sobre dicotomía maneja el caso cuando todas las relaciones disponibles son operadores booleanos, eso es para dominio de tamaño 2. El problema de dicotomía de Schaefer fue recientemente generalizado clases grandes de relaciones.

Todo CSP pude ser también considerado como un problema de conjunción de preguntas.^[1]​

Problemas de funciones

Una situación similar existe entre las clases funcionales FP y #P. Por una generalización del teorema de Ladner, también hay problemas que no son FP ni #P-completo tan grande como FP ≠ #P. Como en el caso de decisión, un problema en el #CSP es definido por un conjunto de relaciones. Cada problema toma una fórmula booleana como entrada y la tarea es computar el número de asignaciones que satisfacen las restricciones. Esto puede ser generalizado usando tamaño de dominios grandes y fijar un peso asignación que satisface y computando la suma de estos pesos. Es conocido que cualquier problema complejo con peso #CSP está en FP o #P-hard.

Variantes de CSP

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.

CSP dinámicos

Los CSP dinámicos^[3]​ (DCSP) son usados cuando la formulación original de un problema es alterado de alguna forma, típicamente porque el conjunto de restricciones a considerar cambia por el entorno.^[4]​ los DCSP son vistos como una secuencia de CSP estáticos, cada uno es una transformación del anterior en el que variables y restricciones pueden ser adicionadas (restriction) o eliminadas (relaxation). La información encontrada en la formulación inicial del problema puede ser usada para refinar los siguientes. El método de solución puede ser clasificado acorde a la forma en que la información es transferida:

• Oracles: las soluciones encontradas de los anteriores CSP en la secuencia son usadas como heurísticas para guiar la resolución del actual CSP.
• Local repair: cada CSP es calculado comenzando desde la solución parcial del CSP anterior y reparando las inconsistencias con búsqueda local.
• Constraint recording: nuevas restricciones son definidas en cada estado de la búsqueda para representar el conocimiento de inconsistencia de grupo de las decisiones. Esas restricciones son llevadas hacia el nuevo CSP.

CSP flexible

Los CSP clásicos tratan las restricciones como fuertes, significan que son inviolables (cada solución las debe satisfacer por completo) e inflexible (en este sentido las restricciones deben ser completamente cumplidas o por el contrario son completamente violadas). Los CSP flexibles relajan estas suposiciones, relajan parcialmente las restricciones y permiten a la solución no cumplir con exactamente todas las restricciones. Algunos tipos de CSP flexible incluyen:

• MAX-CSP, donde un número de restricciones son permitidas que se violen, y la calidad de la solución es medida por el número de restricciones cumplidas.
• Weighted CSP, un MAX-CSP en el cual cada restricción violada es penalizada acorde a una preferencia predefinida. Es preferida la solución con menos penalizaciones.
• Fuzzy CSP modela las restricciones como relaciones de Lógica difusa en las cuales el cumplimiento de una restricción es una función continua de los valores de las variables, yendo desde completamente cumplidas hasta completamente violadas.

Véase también

• Programación declarativa
• Programación con restricciones

Referencias

1. Kolaitis, Phokion G.; Vardi, Moshe Y. (2000). «Conjunctive-Query Containment and Constraint Satisfaction». Journal of Computer and System Sciences 61 (2): 302-332. doi:10.1006/jcss.2000.1713. 
2. Plantilla:Cite hdl
3. Dechter, R. and Dechter, A., Belief Maintenance in Dynamic Constraint Networks In Proc. of AAAI-88, 37-42. [1] el 17 de noviembre de 2012 en Wayback Machine.
4. Solution reuse in dynamic constraint satisfaction problems, Thomas Schiex

Bibliografía

• 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).

Enlaces externos

• 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.
• Forced Satisfiable CSP Benchmarks of Model RB
• , Ian Miguel - slides.
• - Dissertation by Guido Tack giving a good survey of theory and implementation issues

•   Datos: Q1128326