Inferencia de restricciones

En la satisfacción de restricciones , la inferencia de restricciones es una relación entre las restricciones y sus consecuencias. Un conjunto de restricciones${\displaystyle D}$implica una restricción${\displaystyle C}$si cada solución a${\displaystyle D}$también es una solución para${\displaystyle C}$. En otras palabras, si${\displaystyle V}$es una valoración de las variables en los alcances de las restricciones en${\displaystyle D}$y todas las restricciones en${\displaystyle D}$están satisfechos por${\displaystyle V}$, entonces${\displaystyle V}$también satisface la restricción${\displaystyle C}$.

Algunas operaciones sobre restricciones producen una nueva restricción como consecuencia de ellas. La composición de restricciones opera sobre un par de restricciones binarias.${\displaystyle ((x,y),R)}$y${\displaystyle ((y,z),S)}$con una variable común. La composición de tales dos restricciones es la restricción${\displaystyle ((x,z),Q)}$que se satisface con cada evaluación de las dos variables no compartidas para la cual existe un valor de la variable compartida.${\displaystyle y}$de tal manera que la evaluación de estas tres variables satisfaga las dos restricciones originales.${\displaystyle ((x,y),R)}$y${\displaystyle ((y,z),S)}$.

La proyección de restricciones limita los efectos de una restricción a algunas de sus variables. Dada una restricción${\displaystyle (t,R)}$su proyección a un subconjunto${\displaystyle t'}$de sus variables es la restricción${\displaystyle (t',R')}$que se satisface mediante una evaluación si esta evaluación puede extenderse a las demás variables de tal manera que la restricción original${\displaystyle (t,R)}$está satisfecho.

La composición extendida es similar en principio a la composición, pero permite un número arbitrario de restricciones posiblemente no binarias; la restricción generada se aplica a un subconjunto arbitrario de las variables de las restricciones originales. Restricciones dadas${\displaystyle C_{1},\ldots ,C_{m}}$y una lista${\displaystyle A}$de sus variables, la composición extendida de ellas es la restricción${\displaystyle (A,R)}$donde una evaluación de${\displaystyle A}$satisface esta restricción si se puede extender a las otras variables de modo que${\displaystyle C_{1},\ldots ,C_{m}}$Todos están satisfechos.

• Problema de satisfacción de restricciones

• Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann.ISBN 1-55860-890-7
• Apt, Krzysztof (2003). Principios de programación con restricciones . Cambridge University Press.ISBN 0-521-82583-0
• Marriott, Kim; Peter J. Stuckey (1998). Programación con restricciones: Una introducción . MIT Press.ISBN 0-262-13341-5