Problema de satisfacción de restricciones

Este artículo necesita citas adicionales para su verificación . Por favor, ayuda a mejorar este artículo mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado. Encuentre fuentes:  "Problema de satisfacción de restricciones"  -  noticias  · periódicos  · libros  · académico  · JSTOR ( noviembre de 2014 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

No confundir con Comunicar procesos secuenciales .

Los problemas de satisfacción de restricciones ( CSP ) son preguntas matemáticas definidas como un conjunto de objetos cuyo estado debe satisfacer una serie de restricciones o limitaciones . Los CSP representan las entidades en 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 operativa , 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 a menudo presentan una alta complejidad, requiriendo que una combinación de métodos de búsqueda combinatoria y heurística se resuelva 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 de satisfacibilidad booleano (SAT), las teorías de módulo de satisfacibilidad (SMT), la programación de enteros mixtos (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 la restricción.

Ejemplos de problemas que pueden modelarse como un problema de satisfacción de restricciones incluyen:

• Inferencia de tipo ^{[3] [4]}
• Rompecabezas de las ocho reinas
• Problema de coloración del mapa
• Sudoku , Crucigramas , Futoshiki , Kakuro (Sumas cruzadas), Numbrix , Hidato y muchos otros acertijos de lógica

A menudo se proporcionan con tutoriales de solucionadores CP , ASP, Boolean SAT y SMT. En el caso general, los problemas de restricción pueden ser mucho más difíciles y es posible que no se puedan expresar en algunos de estos sistemas más simples. Los ejemplos de la "vida real" incluyen planificación automatizada , ^{[5] [6]} desambiguación léxica , ^{[7] [8]} musicología , ^[9] configuración de productos ^[10] y asignación de recursos . ^[11]

La existencia de una solución a un CSP puede verse como un problema de decisión . Esto puede decidirse encontrando una solución o no encontrando 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, es posible que se sepa que el CSP tiene soluciones de antemano, a través de algún otro proceso de inferencia matemática.

Definicion formal

Formalmente, un problema de satisfacción de restricciones se define como un triple , donde ^[12]${\displaystyle \langle X,D,C\rangle }$

• ${\displaystyle X=\{X_{1},\ldots ,X_{n}\}}$ es un conjunto de variables,
• ${\displaystyle D=\{D_{1},\ldots ,D_{n}\}}$ es un conjunto de sus respectivos dominios de valores, y
• ${\displaystyle C=\{C_{1},\ldots ,C_{m}\}}$ es un conjunto de restricciones.

Cada variable puede tomar los valores del dominio no vacío . Cada restricción es a su vez un par , donde es un subconjunto de variables y es una relación -ariana en el subconjunto correspondiente 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 correspondiente de dominios. Una evaluación satisface una restricción si los valores asignados a las variables satisfacen la relación .${\displaystyle X_{i}}$${\displaystyle D_{i}}$${\displaystyle C_{j}\in C}$${\displaystyle \langle t_{j},R_{j}\rangle }$${\displaystyle t_{j}\subset X}$${\displaystyle k}$${\displaystyle R_{j}}$${\displaystyle k}$${\displaystyle D_{j}}$${\displaystyle v}$${\displaystyle \langle t_{j},R_{j}\rangle }$${\displaystyle t_{j}}$${\displaystyle R_{j}}$

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 generalmente se resuelven mediante una forma de búsqueda . Las técnicas más utilizadas son las variantes de retroceso , propagación de restricciones y búsqueda local . Estas técnicas también se combinan a menudo, como en el método VLNS , y la investigación actual involucra otras tecnologías como la programación lineal . ^[13]

El retroceso es un algoritmo recursivo. Mantiene una asignación parcial de las variables. Inicialmente, todas las variables están sin asignar. En cada paso, se elige una variable y, a su vez, se le asignan todos los valores posibles. Para cada valor, se comprueba 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 de retroceso básico, la consistencia se define como la satisfacción de todas las restricciones cuyas variables están todas asignadas. Existen varias variantes de retroceso. El backmarking mejora la eficacia de la comprobación de la coherencia. Salto atráspermite 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 se pueden usar más tarde para evitar parte de la búsqueda. La anticipación también se usa 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 que se utilizan 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 resultar satisfactorio o insatisfactorio de problemas. No se garantiza que esto suceda en general; sin embargo, siempre ocurre para algunas formas de propagación de restricciones y / o para ciertos tipos de problemas. Las formas más conocidas y utilizadas de consistencia local son consistencia de arco , consistencia de hiper-arco y consistencia de trayectoria.. El método de propagación de restricciones más popular es el algoritmo AC-3 , que refuerza la coherencia del arco.

Los métodos de búsqueda locales son algoritmos de satisfacibilidad incompletos. Pueden encontrar una solución a un problema, pero pueden fallar incluso si el problema es satisfactorio. Trabajan mejorando iterativamente una asignación completa sobre las variables. En cada paso, se cambia de valor un pequeño número de variables, con el objetivo general de aumentar el número de restricciones satisfechas por esta asignación. El algoritmo de conflictos mínimos es un algoritmo de búsqueda local específico para los 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 lleva a algoritmos híbridos .

Aspectos teóricos

Problemas de decisión

Los CSP también se estudian en la teoría de la complejidad computacional y la teoría de modelos finitos . Una pregunta importante es si para cada conjunto de relaciones, el conjunto de todos los CSP que se pueden representar utilizando solo relaciones elegidas de ese conjunto está en P o NP-completo . Si tal teorema de dicotomía es cierto, entonces los CSP proporcionan uno de los subconjuntos más grandes conocidos de NP que evita problemas intermedios de NP , cuya existencia fue demostrada por el teorema de Ladner bajo el supuesto de que P ≠ NP . El teorema de la dicotomía de Schaefer maneja el caso cuando todas las relaciones disponibles sonOperadores booleanos , es decir, para el tamaño de dominio 2. El teorema de la dicotomía de Schaefer se generalizó recientemente a una clase más amplia de relaciones. ^[14]

La mayoría de las clases de CSP que se sabe que son tratables son aquellas en las que el hipergrama de restricciones tiene un ancho de árbol limitado (y no hay restricciones en el conjunto de relaciones de restricción), o donde las restricciones tienen una forma arbitraria pero existen polimorfismos esencialmente no unarios ^{[ aclaración necesaria ]} del conjunto de relaciones de restricción.

Cada CSP también puede considerarse como un problema de contención de consultas conjuntivas . ^[15]

Problemas de funcionamiento

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 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 asignaciones satisfactorias. Esto se puede generalizar aún más utilizando tamaños de dominio más grandes y asignando una ponderación a cada asignación satisfactoria y calculando la suma de estas ponderaciones. Se sabe que cualquier problema #CSP ponderado complejo está en FP o # P-hard. ^[dieciséis]

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 la representación de problemas con facilidad. ^[17] 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 ^[18] ( 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. ^{[19] 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 (restricción) o eliminar (relajación) variables y restricciones. La información que se encuentra en las formulaciones iniciales del problema se puede utilizar para refinar las siguientes. El método de resolución se puede clasificar según la forma en que se transfiere la información:

• Oráculos: la solución encontrada para los CSP anteriores en la secuencia se utiliza como heurística 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 limitaciones 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 estrictas, lo que significa que son imperativas (cada solución debe satisfacerlas todas) e inflexibles (en el sentido de que deben satisfacerse por completo o de lo contrario se violan por completo). Los CSP flexibles relajan esas suposiciones, relajando parcialmente las limitaciones 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 el número 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 tanto, se prefiere satisfacer la restricción con más peso.
• Restricciones del modelo CSP difuso como relaciones difusas en las que la satisfacción de una restricción es una función continua de los valores de sus variables, pasando de totalmente satisfechas a totalmente violadas.

CSP descentralizados

En los DCSP ^[20] se piensa 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

• Gráfico compuesto de restricción
• Programación de restricciones
• Programación declarativa
• Optimización restringida (COP)
• Optimización de restricciones distribuidas
• Homomorfismo gráfico
• Conjetura de juegos únicos
• Problema de satisfacción de restricciones ponderadas (WCSP)

Referencias

1. Lecoutre, Christophe (2013). Redes de restricción: técnicas y algoritmos . Wiley. pag. 26. ISBN 978-1-118-61791-5.
2. "Restricciones - incluida la opción de publicar acceso abierto" . springer.com . Consultado el 3 de octubre de 2019 .
3. Chandra, Satish, et al. " Inferencia de tipos para la compilación estática de JavaScript ". Avisos ACM SIGPLAN 51.10 (2016): 410-429.
4. 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).
5. 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.
6. Satisfacción dinámica de restricciones flexibles y su aplicación a la planificación de la IA , archivado el 6 de febrero de 2009 en la Wayback Machine Ian Miguel - diapositivas.
7. Demetriou, George C. " Desambiguación léxica mediante el manejo de restricciones en Prolog (CHIP) ". Actas de la sexta conferencia sobre el capítulo europeo de la Association for Computational Linguistics. Asociación de Lingüística Computacional, 1993.
8. 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.
9. Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. " GELISP: UN MARCO PARA REPRESENTAR PROBLEMAS DE SATISFACCIÓN DE RESTRICCIÓN MUSICAL Y ESTRATEGIAS DE BÚSQUEDA ". Revista de tecnología de la información teórica y aplicada 86 (2). 2016. 327–331.
10. 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)
11. Modi, Pragnesh Jay, et al. " Un enfoque dinámico distribuido de satisfacción de restricciones para la asignación de recursos ". Conferencia Internacional sobre Principios y Práctica de la Programación de Restricciones. Springer, Berlín, Heidelberg, 2001.
12. Stuart Jonathan Russell; Peter Norvig (2010). Inteligencia artificial: un enfoque moderno . Prentice Hall. pag. Capítulo 6. ISBN 9780136042594.
13. Optimización híbrida: los diez años de CPAIOR . Milano, Michela., Van Hentenryck, Pascal., Conferencia Internacional sobre Integración de Técnicas de IA y OR en la Programación de Restricciones para Problemas de Optimización Combinatoria. Nueva York: Springer. 2011. ISBN 9781441916440. OCLC  695387020 .
14. Bodirsky, Manuel; Pinsker, Michael (2011). "Teorema de Schaefer para gráficos". Actas del 43º Simposio Anual de Teoría de la Computación (STOC '11) . Asociación de Maquinaria Informática . págs. 655–664. arXiv : 1011.2894 . Código bibliográfico : 2010arXiv1011.2894B . doi : 10.1145 / 1993636.1993724 . ISBN 978-1-4503-0691-1. S2CID  47097319 .
15. Kolaitis, Phokion G .; Vardi, Moshe Y. (2000). "Contención de consultas conjuntivas y satisfacción de restricciones" . Revista de Ciencias de la Computación y Sistemas . 61 (2): 302–332. doi : 10.1006 / jcss.2000.1713 .
16. 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 .
17. Miguel, Ian (julio de 2001). Satisfacción dinámica de restricciones 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 . 
18. Dechter, R. y Dechter, A., Mantenimiento de creencias en redes de restricciones dinámicas Archivado el 17 de noviembre de 2012 en la Wayback Machine In Proc. de AAAI-88, 37–42.
19. Reutilización de soluciones en problemas de satisfacción de restricciones dinámicas , Thomas Schiex
20. Duffy, KR; Leith, DJ (agosto de 2013), "Descentralized Constraint Satisfaction", IEEE / ACM Transactions on Networking, 21 (4) , 21 , págs. 1298–1308, arXiv : 1103.3240 , doi : 10.1109 / TNET.2012.2222923 , S2CID 11504393 

Otras lecturas

• Una introducción rápida a la satisfacción con las restricciones en YouTube
• Steven Minton; Andy Philips; Mark D. Johnston; Philip Laird (1993). "Minimización de 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 .
• Tsang, Edward (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 Kaufmann. ISBN  1-55860-890-7
• Apt, Krzysztof (2003). Principios de la programación de restricciones . Prensa de la Universidad de Cambridge. ISBN  0-521-82583-0
• Lecoutre, Christophe (2009). Redes de restricción: técnicas y algoritmos . ISTE / Wiley. ISBN  978-1-84821-106-3
• Tomás Feder, Satisfacción con la restricción: una perspectiva personal , manuscrito.
• Archivo de restricciones
• Puntos de referencia de CSP satisfactorios forzados del modelo RB
• 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 una buena revisión de la teoría y los problemas de implementación.