Conjunto de objetos cuyo estado debe satisfacer límites.
Los problemas de satisfacción de restricciones ( CSP ) son cuestiones matemáticas definidas como un conjunto de objetos cuyo estado debe satisfacer una serie de restricciones o limitaciones . Los CSP representan las entidades de un problema como una colección homogénea de restricciones finitas sobre variables , que se resuelve mediante métodos de satisfacción de restricciones . Los CSP son objeto de investigación tanto en inteligencia artificial como en investigación de operaciones , ya que la regularidad en su formulación proporciona una base común para analizar y resolver problemas de muchas familias aparentemente no relacionadas. Los CSP suelen presentar una gran complejidad y requieren una combinación de heurísticas y métodos de búsqueda combinatoria para resolverse en un tiempo razonable. La programación de restricciones (CP) es el campo de investigación que se centra específicamente en abordar este tipo de problemas. [1] [2] Además, el problema booleano de satisfacibilidad (SAT), las teorías del módulo de satisfacibilidad (SMT), la programación entera mixta (MIP) y la programación de conjuntos de respuestas (ASP) son campos de investigación que se centran en la resolución de formas particulares de la problema de satisfacción de restricciones.
Ejemplos de problemas que se pueden modelar como un problema de satisfacción de restricciones incluyen:
Estos suelen contar con tutoriales de solucionadores de CP , ASP, SAT booleano y SMT. En el caso general, los problemas de restricciones pueden ser mucho más difíciles y pueden no ser expresables en algunos de estos sistemas más simples. Los ejemplos de la "vida real" incluyen planificación automatizada , [6] [7] desambiguación léxica , [8] [9] musicología , [10] configuración de productos [11] y asignación de recursos . [12]
La existencia de una solución para un CSP puede verse como un problema de decisión . Esto se puede decidir encontrando una solución, o no logrando encontrar una solución después de una búsqueda exhaustiva ( los algoritmos estocásticos normalmente nunca llegan a una conclusión exhaustiva, mientras que las búsquedas dirigidas a menudo sí lo hacen, en problemas suficientemente pequeños). En algunos casos, se puede saber de antemano que el CSP tiene soluciones, mediante algún otro proceso de inferencia matemática.
Definición formal
Formalmente, un problema de satisfacción de restricciones se define como un triple , donde [13]![{\displaystyle \langle X,D,C\rangle }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
es un conjunto de variables,
es un conjunto de sus respectivos dominios de valores, y
es un conjunto de restricciones.
Cada variable puede tomar los valores en el dominio no vacío . Cada restricción es a su vez un par , donde es un subconjunto de variables y es una relación aria en el correspondiente subconjunto de dominios . Una evaluación de las variables es una función de un subconjunto de variables a un conjunto particular de valores en el subconjunto de dominios correspondiente. Una evaluación satisface una restricción si los valores asignados a las variables satisfacen la relación .![{\displaystyle X_{i}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ Displaystyle D_ {i}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle C_{j}\en C}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \langle t_{j},R_{j}\rangle }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle t_{j}\subseteq X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle k}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R_{j}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle k}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle D_{j}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle v}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \langle t_{j},R_{j}\rangle }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle t_{j}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R_{j}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Una evaluación es consistente si no viola ninguna de las restricciones. Una evaluación está completa si incluye todas las variables. Una evaluación es una solución si es consistente y completa; Se dice que tal evaluación resuelve el problema de satisfacción de restricciones.
Solución
Los problemas de satisfacción de restricciones en dominios finitos normalmente se resuelven mediante una forma de búsqueda . Las técnicas más utilizadas son variantes de retroceso , propagación de restricciones y búsqueda local . Estas técnicas también suelen combinarse, como en el método VLNS , y la investigación actual involucra otras tecnologías como la programación lineal . [14]
El retroceso es un algoritmo recursivo. Mantiene una asignación parcial de las variables. Inicialmente, todas las variables están desasignadas. En cada paso, se elige una variable y se le asignan todos los valores posibles por turno. Para cada valor, se verifica la coherencia de la asignación parcial con las restricciones; en caso de coherencia, se realiza una llamada recursiva . Cuando se han probado todos los valores, el algoritmo retrocede. En este algoritmo básico de retroceso, la coherencia se define como la satisfacción de todas las restricciones cuyas variables están asignadas. Existen varias variantes de retroceso. El backmarking mejora la eficiencia a la hora de comprobar la coherencia. El salto hacia atrás permite guardar parte de la búsqueda retrocediendo "más de una variable" en algunos casos. El aprendizaje de restricciones infiere y guarda nuevas restricciones que pueden usarse posteriormente para evitar parte de la búsqueda. La anticipación también se utiliza a menudo para retroceder para intentar prever los efectos de elegir una variable o un valor, determinando así a veces de antemano cuándo un subproblema es satisfactorio o insatisfactorio.
Las técnicas de propagación de restricciones son métodos utilizados para modificar un problema de satisfacción de restricciones. Más precisamente, son métodos que imponen una forma de consistencia local , que son condiciones relacionadas con la consistencia de un grupo de variables y/o restricciones. La propagación de restricciones tiene varios usos. En primer lugar, convierte un problema en uno equivalente pero que suele ser más sencillo de resolver. En segundo lugar, puede demostrar la satisfacibilidad o insatisfacción de los problemas. No se garantiza que esto suceda en general; sin embargo, siempre ocurre con algunas formas de propagación de restricciones y/o con ciertos tipos de problemas. Las formas de consistencia local más conocidas y utilizadas son la consistencia de arco , la consistencia de hiperarco y la consistencia de ruta . El método de propagación de restricciones más popular es el algoritmo AC-3 , que impone la coherencia del arco.
Los métodos de búsqueda local son algoritmos de satisfacibilidad incompletos. Pueden encontrar una solución a un problema, pero pueden fracasar incluso si el problema es satisfactoria. Funcionan mejorando iterativamente una asignación completa sobre las variables. En cada paso, se cambia el valor de una pequeña cantidad de variables, con el objetivo general de aumentar la cantidad de restricciones satisfechas por esta asignación. El algoritmo de conflictos mínimos es un algoritmo de búsqueda local específico para CSP y se basa en ese principio. En la práctica, la búsqueda local parece funcionar bien cuando estos cambios también se ven afectados por elecciones aleatorias. Se ha desarrollado una integración de la búsqueda con la búsqueda local, lo que ha dado lugar a algoritmos híbridos .
Aspectos teóricos
Complejidad computacional
Los CSP también se estudian en teoría de la complejidad computacional , teoría de modelos finitos y álgebra universal . Resultó que las preguntas sobre la complejidad de los CSP se traducen en importantes preguntas algebraicas universales sobre las álgebras subyacentes. Este enfoque se conoce como enfoque algebraico de los CSP. [15]
Dado que cada problema de decisión computacional es equivalente en tiempo polinomial a un CSP con una plantilla infinita, [16] los CSP generales pueden tener una complejidad arbitraria. En particular, también existen CSP dentro de la clase de problemas NP-intermedios , cuya existencia fue demostrada por Ladner , bajo el supuesto de que P ≠ NP .
Sin embargo, una gran clase de CSP que surgen de aplicaciones naturales satisfacen una dicotomía de complejidad, lo que significa que cada CSP dentro de esa clase está en P o NP-completo . Por lo tanto, estos CSP proporcionan uno de los subconjuntos más grandes conocidos de NP que evita problemas intermedios de NP . Schaefer demostró por primera vez una dicotomía de complejidad para los CSP booleanos, es decir, CSP en un dominio de 2 elementos y donde todas las relaciones disponibles son operadores booleanos . Este resultado se ha generalizado para varias clases de CSP, en particular para todos los CSP en dominios finitos. Esta conjetura de dicotomía de dominio finito fue formulada por primera vez por Tomás Feder y Moshe Vardi, [17] y finalmente probada de forma independiente por Andrei Bulatov [18] y Dmitriy Zhuk en 2017. [19]
Otras clases para las que se ha confirmado una dicotomía de complejidad son
- todas las reducciones de primer orden de , [20]
![{\displaystyle (\mathbb {Q},<)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- todas las reducciones de primer orden del gráfico aleatorio contable , [21]
- todos los reductos de primer orden del modelo compañero de la clase de todas las relaciones C, [22]
- todos los reductos de primer orden del poset homogéneo universal , [23]
- todas las reducciones de primer orden de gráficos no dirigidos homogéneos, [24]
- todos los reductos de primer orden de todas las estructuras unarias, [25]
- todos los CSP en la clase de complejidad MMSNP. [26]
La mayoría de las clases de CSP que se sabe que son manejables son aquellas en las que el hipergráfico de restricciones tiene un ancho de árbol limitado , [27] o en las que las restricciones tienen una forma arbitraria pero existen polimorfismos ecuacionalmente no triviales del conjunto de relaciones de restricciones. [28]
Se ha formulado una conjetura de dicotomía de dominio infinito [29] para todos los CSP de reductos de estructuras homogéneas finitamente acotadas, afirmando que el CSP de dicha estructura está en P si y sólo si su clon de polimorfismo es ecuacionalmente no trivial, y NP- difícil de lo contrario.
La complejidad de estos CSP de dominio infinito, así como de otras generalizaciones (CSP valorados, CSP cuantificados, CSP prometidos) sigue siendo un área de investigación activa. [30] [1][2]
Cada CSP también puede considerarse como un problema de contención de consultas conjuntivas . [31]
Problemas de función
Existe una situación similar entre las clases funcionales FP y #P . Por una generalización del teorema de Ladner , tampoco hay problemas ni en FP ni en #P-completo siempre que FP ≠ #P. Como en el caso de la decisión, un problema en el #CSP se define por un conjunto de relaciones. Cada problema toma una fórmula booleana como entrada y la tarea es calcular el número de tareas satisfactorias. Esto se puede generalizar aún más utilizando tamaños de dominio más grandes y asignando un peso a cada asignación satisfactoria y calculando la suma de estos pesos. Se sabe que cualquier problema #CSP ponderado complejo está en FP o #P-hard. [32]
Variantes
El modelo clásico de problema de satisfacción de restricciones define un modelo de restricciones estáticas e inflexibles. Este modelo rígido es una deficiencia que dificulta representar los problemas fácilmente. [33] Se han propuesto varias modificaciones de la definición básica de CSP para adaptar el modelo a una amplia variedad de problemas.
CSP dinámicos
Los CSP dinámicos [34] ( DCSP ) son útiles cuando la formulación original de un problema se altera de alguna manera, generalmente porque el conjunto de restricciones a considerar evoluciona debido al entorno. [35] Los DCSP se ven como una secuencia de CSP estáticos, cada uno de los cuales es una transformación del anterior en el que se pueden agregar variables y restricciones (restricción) o eliminar (relajación). La información encontrada en las formulaciones iniciales del problema se puede utilizar para perfeccionar las siguientes. El método de resolución se puede clasificar según la forma en que se transfiere la información:
- Oráculos : las soluciones encontradas para los CSP anteriores en la secuencia se utilizan como heurísticas para guiar la resolución del CSP actual desde cero.
- Reparación local: cada CSP se calcula partiendo de la solución parcial del anterior y reparando las restricciones inconsistentes con búsqueda local .
- Registro de restricciones: se definen nuevas restricciones en cada etapa de la búsqueda para representar el aprendizaje de un grupo de decisiones inconsistentes. Esas limitaciones se trasladan a los nuevos problemas de CSP.
CSP flexibles
Los CSP clásicos tratan las restricciones como duras, lo que significa que son imperativas (cada solución debe satisfacerlas todas) e inflexibles (en el sentido de que deben satisfacerse completamente o, de lo contrario, serán violadas por completo). Los CSP flexibles relajan esos supuestos, relajando parcialmente las restricciones y permitiendo que la solución no las cumpla todas. Esto es similar a las preferencias en la planificación basada en preferencias . Algunos tipos de CSP flexibles incluyen:
- MAX-CSP, donde se permite violar una serie de restricciones y la calidad de una solución se mide por la cantidad de restricciones satisfechas.
- CSP ponderado , un MAX-CSP en el que cada violación de una restricción se pondera según una preferencia predefinida. Por lo tanto, se prefiere satisfacer la restricción con más peso.
- Las restricciones del modelo CSP difuso son relaciones difusas en las que la satisfacción de una restricción es una función continua de los valores de sus variables, desde completamente satisfecha hasta completamente violada.
CSP descentralizados
En los DCSP [36] se considera que cada variable de restricción tiene una ubicación geográfica separada. Se imponen fuertes restricciones al intercambio de información entre variables, lo que requiere el uso de algoritmos completamente distribuidos para resolver el problema de satisfacción de restricciones.
Ver también
Referencias
- ^ Lecoutre, Christophe (2013). Redes de restricciones: técnicas y algoritmos . Wiley. pag. 26.ISBN 978-1-118-61791-5.
- ^ "Restricciones: incluida la opción de publicar en acceso abierto". springer.com . Consultado el 3 de octubre de 2019 .
- ^ Chandra, Satish y otros. "Inferencia de tipos para compilación estática de JavaScript". Avisos ACM SIGPLAN 51.10 (2016): 410-429.
- ^ Jim, Trevor y Jens Palsberg. "Inferencia de tipos en sistemas de tipos recursivos con subtipificación". Disponible en la página web de los autores (1999).
- ^ Farhi, Eduardo; Aram W Harrow (2016). "Supremacía cuántica a través del algoritmo de optimización cuántica aproximada". arXiv : 1602.07674 [cuántico-ph].
- ^ Malik Ghallab; Dana Nau; Paolo Traverso (21 de mayo de 2004). Planificación automatizada: teoría y práctica. Elsevier. págs.1–. ISBN 978-0-08-049051-9.
- ^ Satisfacción de restricciones dinámicas y flexibles y su aplicación a la planificación de la IA, archivado el 6 de febrero de 2009 en Wayback Machine Ian Miguel - diapositivas.
- ^ Demetriou, George C. "Desambiguación léxica mediante manejo de restricciones en Prolog (CHIP)". Actas de la sexta conferencia sobre el capítulo europeo de la Asociación de Lingüística Computacional. Asociación de Lingüística Computacional, 1993.
- ^ MacDonald, Maryellen C. y Mark S. Seidenberg. "Relatos de satisfacción de restricciones de comprensión léxica y de oraciones". Manual de psicolingüística (segunda edición). 2006. 581–611.
- ^ Mauricio Toro, Carlos Agón, Camilo Rueda, Gerard Assayag. "GELISP: UN MARCO PARA REPRESENTAR PROBLEMAS DE SATISFACCIÓN DE RESTRICCIONES MUSICALES Y ESTRATEGIAS DE BÚSQUEDA". Revista de Tecnología de la Información Teórica y Aplicada 86 (2). 2016. 327–331.
- ^ Aplicación del enfoque de satisfacción de restricciones para resolver problemas de configuración de productos con reglas de configuración basadas en cardinalidad , Dong Yang & Ming Dong, Journal of Intelligent Manufacturing volumen 24, páginas 99-111 (2013)
- ^ Modi, Pragnesh Jay y col. "Un enfoque dinámico de satisfacción de restricciones distribuidas para la asignación de recursos". Conferencia internacional sobre principios y práctica de la programación de restricciones. Springer, Berlín, Heidelberg, 2001.
- ^ Estuardo Jonathan Russell; Peter Norvig (2010). Inteligencia artificial: un enfoque moderno . Prentice Hall. pag. Capítulo 6. ISBN 9780136042594.
- ^ Milán, Michela ; Van Hentenryck, Pascal, eds. (2011). Optimización híbrida: los diez años de CPAIOR . Conferencia internacional sobre integración de técnicas de IA y OR en programación de restricciones para problemas de optimización combinatoria. Nueva York: Springer. ISBN 9781441916440. OCLC 695387020.
- ^ Barto, Líbor; Brady, Zaratustra; Bulatov, Andrei; Kozik, Marcin; Zhuk, Dmitriy (15 de mayo de 2024). "Unificación de los tres enfoques algebraicos del CSP mediante álgebras mínimas de Taylor". Teóricos . 3 : 11361. arXiv : 2104.11808 . doi :10.46298/teórico.24.14. ISSN 2751-4838.
- ^ Bodirsky, Manuel; Grohe, Martín (2008). "No dicotomías en la complejidad de la satisfacción de restricciones". En Aceto, Luca; Damgard, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). Autómatas, Lenguajes y Programación . Apuntes de conferencias sobre informática. vol. 5126. Berlín, Heidelberg: Springer. págs. 184-196. doi :10.1007/978-3-540-70583-3_16. ISBN 978-3-540-70583-3.
- ^ Feder, Tomás; Vardi, Moshe Y. (1998). "La estructura computacional del SNP monádico monótono y la satisfacción de restricciones: un estudio a través del registro de datos y la teoría de grupos". Revista SIAM de Computación . 28 (1): 57–104. doi :10.1137/S0097539794266766. ISSN 0097-5397.
- ^ Bulatov, Andrei (2017). "Un teorema de dicotomía para CSP no uniformes". Actas del 58.º Simposio anual del IEEE sobre fundamentos de la informática, FOCS 2017 . Sociedad de Computación IEEE. págs. 319–330. arXiv : 1703.03021 . doi :10.1109/FOCS.2017.37. ISBN 978-1-5386-3464-6.
- ^ Zhuk, Dmitriy (2020). "Una prueba de la conjetura de la dicotomía CSP". Revista de la ACM . 67 (5): 1–78. arXiv : 1704.01914 . doi :10.1145/3402029.
- ^ Bodirsky, Manuel; Kara, enero (8 de febrero de 2010). "La complejidad de los problemas de satisfacción de restricciones temporales". J. ACM . 57 (2): 9:1–9:41. doi :10.1145/1667053.1667058. ISSN 0004-5411.
- ^ Bodirsky, Manuel; Pinsker, Michael (2011). "Teorema de Schaefer para gráficas". Actas del 43º Simposio Anual sobre Teoría de la Computación (STOC '11) . Asociación de Maquinaria de Computación . págs. 655–664. arXiv : 1011.2894 . doi :10.1145/1993636.1993724. ISBN 978-1-4503-0691-1. S2CID 47097319.
- ^ Bodirsky, Manuel; Jonsson, Peter; Pham, Trung Van (2 de agosto de 2017). "La complejidad de los problemas de satisfacción de las restricciones de filogenia". Transmisión ACM. Computadora. Lógica . 18 (3): 23:1–23:42. arXiv : 1503.07310 . doi :10.1145/3105907. ISSN 1529-3785.
- ^ Kompatscher, Michael; Pham, Trung Van (2017). "Una dicotomía de complejidad para la satisfacción de la restricción Poset". DROPS-IDN/V2/Document/10.4230/LIPIcs.STACS.2017.47 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi : 10.4230/LIPIcs.STACS.2017.47 .
- ^ Bodirsky, Manuel; Martín, Bernabé; Pinsker, Michael; Pongrácz, András (enero de 2019). "Problemas de satisfacción de restricciones para reducciones de gráficos homogéneos". Revista SIAM de Computación . 48 (4): 1224-1264. arXiv : 1602.05819 . doi :10.1137/16M1082974. ISSN 0097-5397.
- ^ Bodirsky, Manuel; Mottet, Antoine (20 de mayo de 2018), "Una dicotomía para reducciones de primer orden de estructuras unarias", Métodos lógicos en informática , 14 (2), arXiv : 1601.04520 , doi :10.23638/LMCS-14(2:13 )2018
- ^ Bodirsky, Manuel; Madelaine, Florent; Mottet, Antoine (9 de julio de 2018). "Una prueba algebraica universal de la dicotomía de complejidad para SNP monótonos monádicos". Actas del 33º Simposio anual ACM/IEEE sobre lógica en informática . LICS '18. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 105-114. arXiv : 1802.03255 . doi :10.1145/3209108.3209156. ISBN 978-1-4503-5583-4.
- ^ Barto, Líbor; Kozik, Marcin (1 de enero de 2014). "Problemas de satisfacción de restricciones que se pueden resolver mediante métodos de coherencia locales". J. ACM . 61 (1): 3:1–3:19. doi :10.1145/2556646. ISSN 0004-5411.
- ^ Bodirsky, Manuel (2021). Complejidad de la satisfacción de restricciones de dominio infinito. Apuntes de conferencias sobre lógica. Cambridge: Prensa de la Universidad de Cambridge. ISBN 978-1-107-04284-1.
- ^ Bodirsky, Manuel; Pinsker, Michael; Pongrácz, András (marzo de 2021). "Homomorfismos de clones proyectivos". La revista de lógica simbólica . 86 (1): 148-161. arXiv : 1409.4601 . doi :10.1017/jsl.2019.23. ISSN 0022-4812.
- ^ Pinsker, Michael (31 de marzo de 2022). "Desafíos actuales en la satisfacción de las restricciones de dominio infinito: dilemas de la oveja infinita". arXiv : 2203.17182 [cs.LO].
- ^ Kolaítis, Phokion G.; Vardi, Moshe Y. (2000). "Contención de consultas conjuntivas y satisfacción de restricciones". Revista de Ciencias de la Computación y de Sistemas . 61 (2): 302–332. doi : 10.1006/jcss.2000.1713 .
- ^ Cai, Jin-Yi; Chen, Xi (2012). "Complejidad de contar CSP con pesos complejos". Actas del cuadragésimo cuarto simposio anual de ACM sobre teoría de la computación (STOC '12) . págs. 909–920. arXiv : 1111.2384 . doi :10.1145/2213977.2214059. ISBN 978-1-4503-1245-5. S2CID 53245129.
- ^ Miguel, Ian (julio de 2001). Satisfacción de restricciones dinámicas y flexibles y su aplicación a la planificación de la IA (tesis doctoral). Escuela de Informática de la Universidad de Edimburgo . CiteSeerX 10.1.1.9.6733 . hdl : 1842/326.
- ^ Dechter, R. y Dechter, A., Mantenimiento de creencias en redes de restricciones dinámicas Archivado el 17 de noviembre de 2012 en Wayback Machine en Proc. de AAAI-88, 37–42.
- ^ Reutilización de soluciones en problemas de satisfacción de restricciones dinámicas, Thomas Schiex
- ^ Duffy, KR; Leith, DJ (agosto de 2013), "Satisfacción de restricciones descentralizadas", IEEE/ACM Transactions on Networking, 21(4) , vol. 21, págs. 1298–1308, arXiv : 1103.3240 , doi : 10.1109/TNET.2012.2222923, S2CID 11504393
Lectura adicional
- Una introducción rápida al cumplimiento de restricciones en YouTube
- Manuel Bodirsky (2021). "Complejidad de la satisfacción de restricciones de dominio infinito" . Prensa de la Universidad de Cambridge. https://doi.org/10.1017/9781107337534
- Steven Minton; Andy Philips; Mark D. Johnston; Philip Laird (1993). "Minimizar los conflictos: un método de reparación heurística para problemas de programación y satisfacción de restricciones". Revista de investigación en inteligencia artificial . 58 (1–3): 161–205. CiteSeerX 10.1.1.308.6637 . doi :10.1016/0004-3702(92)90007-k. S2CID 14830518.
- Tsang, Eduardo (1993). Fundamentos de la satisfacción de restricciones. Prensa académica. ISBN 0-12-701610-4
- Chen, Hubie (diciembre de 2009). "Un encuentro de lógica, complejidad y álgebra". Encuestas de Computación ACM . 42 (1): 1–32. arXiv : cs/0611018 . doi :10.1145/1592451.1592453. S2CID 11975818.
- Dechter, Rina (2003). Procesamiento de restricciones. Morgan Kaufman. ISBN 1-55860-890-7
- Apto, Krzysztof (2003). Principios de programación de restricciones . Prensa de la Universidad de Cambridge. ISBN 9780521825832. ISBN 0-521-82583-0
- Lecoutre, Christophe (2009). Redes de restricciones: técnicas y algoritmos. ISTE/Wiley. ISBN 978-1-84821-106-3
- Tomás Feder, Satisfacción de restricciones: una perspectiva personal, manuscrito.
- Archivo de restricciones
- Puntos de referencia de CSP satisfactorios forzados del modelo RB Archivado el 25 de enero de 2021 en Wayback Machine.
- Puntos de referencia: representación XML de instancias de CSP
- XCSP3: un formato basado en XML diseñado para representar instancias de CSP
- Propagación de restricciones: disertación de Guido Tack que ofrece un buen estudio de la teoría y las cuestiones de implementación.