En la investigación de operaciones e inteligencia artificial , la satisfacción de restricciones es el proceso de encontrar una solución a un conjunto de restricciones que imponen condiciones que las variables deben satisfacer . [1] Por lo tanto, una solución es un conjunto de valores para las variables que satisface todas las restricciones, es decir, un punto en la región factible .
Las técnicas utilizadas en la satisfacción de restricciones dependen del tipo de restricciones que se consideren. A menudo se utilizan restricciones en un dominio finito , hasta el punto de que los problemas de satisfacción de restricciones se identifican típicamente con problemas basados en restricciones en un dominio finito. Por lo general, estos problemas se resuelven mediante la búsqueda , en particular una forma de retroceso o búsqueda local . Propagación de restricciones¿Se utilizan otros métodos en estos problemas? la mayoría de ellos están incompletos en general, es decir, pueden resolver el problema o resultar insatisfactorio, pero no siempre. Los métodos de propagación de restricciones también se utilizan junto con la búsqueda para simplificar la resolución de un problema determinado. Otros tipos de restricciones considerados son los números reales o racionales; La resolución de problemas sobre estas restricciones se realiza mediante la eliminación de variables o el algoritmo simplex .
La satisfacción por restricciones se originó en el campo de la inteligencia artificial en la década de 1970 (ver, por ejemplo, ( Laurière 1978 )). Durante las décadas de 1980 y 1990, se desarrolló la integración de restricciones en un lenguaje de programación . Los lenguajes que se utilizan a menudo para la programación de restricciones son Prolog y C ++ .
Problema de satisfacción de restricciones
Como se definió originalmente en inteligencia artificial, las restricciones enumeran los posibles valores que un conjunto de variables puede tomar en un mundo dado. Un mundo posible es una asignación total de valores a variables que representan una forma en que el mundo (real o imaginario) podría ser. [2] De manera informal, un dominio finito es un conjunto finito de elementos arbitrarios. Un problema de satisfacción de restricciones en dicho dominio contiene un conjunto de variables cuyos valores solo pueden tomarse del dominio, y un conjunto de restricciones, cada restricción especifica los valores permitidos para un grupo de variables. Una solución a este problema es una evaluación de las variables que satisfaga todas las restricciones. En otras palabras, una solución es una forma de asignar un valor a cada variable de tal manera que todas las restricciones sean satisfechas por estos valores.
En algunas circunstancias, pueden existir requisitos adicionales: uno puede estar interesado no solo en la solución (y en la forma más rápida o más eficiente desde el punto de vista computacional para alcanzarla) sino en cómo se alcanzó; por ejemplo, uno puede querer la solución "más simple" ("más simple" en un sentido lógico, no computacional, que debe definirse con precisión). Este suele ser el caso en juegos de lógica como el Sudoku.
En la práctica, las restricciones a menudo se expresan en forma compacta, en lugar de enumerar todos los valores de las variables que satisfarían la restricción. Una de las restricciones más utilizadas es la (obvia) que establece que los valores de las variables afectadas deben ser todas diferentes.
Los problemas que se pueden expresar como problemas de satisfacción de restricciones son el rompecabezas de las ocho reinas , el problema de resolución de Sudoku y muchos otros acertijos de lógica, el problema de satisfacibilidad booleano , problemas de programación , problemas de estimación de errores acotados y varios problemas en gráficos como el problema de coloración de gráficos .
Aunque por lo general no se incluyen en la definición anterior de un problema de satisfacción de restricciones, las ecuaciones aritméticas y las desigualdades limitan los valores de las variables que contienen y, por lo tanto, pueden considerarse una forma de restricciones. Su dominio es el conjunto de números (enteros, racionales o reales), que es infinito: por lo tanto, las relaciones de estas restricciones también pueden ser infinitas; por ejemplo,tiene un número infinito de pares de valores satisfactorios. Las ecuaciones aritméticas y las desigualdades a menudo no se consideran dentro de la definición de un "problema de satisfacción de restricciones", que se limita a dominios finitos. Sin embargo, se utilizan a menudo en la programación de restricciones .
Se puede demostrar que las desigualdades o ecuaciones aritméticas presentes en algunos tipos de acertijos de lógica finita como Futoshiki o Kakuro (también conocidos como Sumas cruzadas) pueden tratarse como restricciones no aritméticas (ver Satisfacción de restricciones basadas en patrones y Acertijos de lógica [ 3] ).
Resolviendo
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 se utilizan en problemas con restricciones no lineales .
La eliminación de variables y el algoritmo simplex se utilizan para resolver ecuaciones y desigualdades lineales y polinomiales , y problemas que contienen variables con dominio infinito. Por lo general, se resuelven como problemas de optimización en los que la función optimizada es el número de restricciones violadas.
Complejidad
Resolver un problema de satisfacción de restricciones en un dominio finito es un problema NP completo con respecto al tamaño del dominio. La investigación ha mostrado una serie de subcampos manejables , algunos limitando las relaciones de restricción permitidas, algunos requiriendo los alcances de las restricciones para formar un árbol, posiblemente en una versión reformulada del problema. La investigación también ha establecido una relación entre el problema de la satisfacción de restricciones y problemas en otras áreas, como la teoría de modelos finitos .
Programación de restricciones
La programación de restricciones es el uso de restricciones como lenguaje de programación para codificar y resolver problemas. Esto se hace a menudo incorporando restricciones en un lenguaje de programación , que se llama lenguaje anfitrión. La programación de restricciones se originó a partir de una formalización de igualdad de términos en Prolog II , lo que condujo a un marco general para incorporar restricciones en un lenguaje de programación lógico . Los lenguajes de host más comunes son Prolog , C ++ y Java , pero también se han utilizado otros lenguajes.
Programación lógica de restricciones
Un programa de lógica de restricción es un programa de lógica que contiene restricciones en los cuerpos de las cláusulas. Como ejemplo, la cláusula A(X):-X>0,B(X)
es una cláusula que contiene la restricción X>0
en el cuerpo. Las restricciones también pueden estar presentes en el objetivo. Las restricciones en el objetivo y en las cláusulas utilizadas para probar el objetivo se acumulan en un conjunto llamado almacenamiento de restricciones . Este conjunto contiene las restricciones que el intérprete ha asumido que son satisfactorias para poder continuar con la evaluación. Como resultado, si este conjunto se detecta como insatisfactorio, el intérprete retrocede. Las ecuaciones de términos, tal como se utilizan en la programación lógica, se consideran una forma particular de restricciones que se pueden simplificar mediante la unificación . Como resultado, el almacenamiento de restricciones puede considerarse una extensión del concepto de sustitución que se usa en la programación lógica regular. Los tipos más comunes de restricciones que se utilizan en la programación lógica de restricciones son las restricciones sobre números enteros / racionales / reales y las restricciones sobre dominios finitos.
También se han desarrollado lenguajes de programación de lógica de restricciones concurrentes . Se diferencian significativamente de la programación lógica de restricciones no concurrentes en que están dirigidas a programar procesos concurrentes que pueden no terminar. Las reglas de manejo de restricciones pueden verse como una forma de programación lógica de restricciones concurrentes, pero a veces también se usan dentro de un lenguaje de programación lógica de restricciones no concurrentes. Permiten reescribir restricciones o inferir nuevas basadas en la verdad de las condiciones.
Conjuntos de herramientas de satisfacción de restricciones
Los kits de herramientas de satisfacción de restricciones son bibliotecas de software para lenguajes de programación imperativos que se utilizan para codificar y resolver un problema de satisfacción de restricciones.
- Solucionador de restricciones de casuario , un proyecto de código abierto para satisfacer las restricciones (accesible desde C, Java, Python y otros lenguajes).
- Comet , un lenguaje de programación comercial y un juego de herramientas
- Gecode , un kit de herramientas portátil de código abierto escrito en C ++ desarrollado como una implementación de alta eficiencia y calidad de producción de un trasfondo teórico completo.
- Gelisp , un contenedor portátil de código abierto de Gecode para Lisp . [4] http://gelisp.sourceforge.net/
- IBM ILOG CP Optimizer : Bibliotecas C ++, Python , Java, .NET (propietarias, gratuitas para uso académico ). [5] Sucesor de ILOG Solver / Scheduler, que fue considerado el líder del mercado en software de programación de restricciones comerciales en 2006 [6]
- JaCoP , un solucionador de restricciones de Java de código abierto.
- OptaPlanner , otro solucionador de restricciones de Java de código abierto.
- Koalog , un solucionador de restricciones comercial basado en Java.
- logilab-constraint , un solucionador de restricciones de código abierto escrito en Python puro con algoritmos de propagación de restricciones.
- Minion , un solucionador de restricciones de código abierto escrito en C ++, con un lenguaje pequeño con el propósito de especificar modelos / problemas.
- ZDC, un programa de código abierto desarrollado en el Proyecto de satisfacción de restricciones asistido por computadora para modelar y resolver problemas de satisfacción de restricciones.
Otros lenguajes de programación de restricciones
Los kits de herramientas de restricciones son una forma de incorporar restricciones en un lenguaje de programación imperativo . Sin embargo, solo se utilizan como bibliotecas externas para codificar y resolver problemas. Un enfoque en el que las restricciones se integran en un lenguaje de programación imperativo se adopta en el lenguaje de programación Kaleidoscope .
Las restricciones también se han incorporado en los lenguajes de programación funcionales .
Ver también
- Problema de satisfacción de restricciones
- Restricción (matemáticas)
- Solución candidata
- Problema de satisfacibilidad booleano
- Teoría de la decisión
- Teorías del módulo de satisfacción
- Configuración basada en conocimientos
Referencias
- ^ Edward Tsang (13 de mayo de 2014). Fundamentos de la satisfacción de restricciones: el texto clásico . BoD - Libros a pedido. ISBN 978-3-7357-2366-6.
- ^ "4.1.1 Variables y mundos‣ 4.1 Posibles mundos, variables y restricciones ‣ Capítulo 4 Razonamiento con restricciones ‣ Inteligencia artificial: Fundamentos de los agentes computacionales, 2ª edición" .
- ^ (en inglés)Berthier, Denis (20 de noviembre de 2012). "Satisfacción de restricciones basadas en patrones y acertijos lógicos" . Editores Lulu . ISBN 978-1-291-20339-4. Archivado desde el original el 12 de enero de 2013 . Consultado el 24 de octubre de 2012 .
- ^ 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.
- ^ Laborie P, Rogerie J, Shaw P, Vilim P (2018). "Optimizador de IBM ILOG CP para la programación". Restricciones . 23 (2): 210–250. doi : 10.1007 / s10601-018-9281-x . S2CID 4360357 .
- ^ Francesca Rossi ; Peter Van Beek; Toby Walsh (2006). Manual de programación de restricciones . Elsevier. pag. 157. ISBN 978-0-444-52726-4.
- Apt, Krzysztof (2003). Principios de la programación de restricciones . Prensa de la Universidad de Cambridge. ISBN 978-0-521-82583-2.
- Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann. ISBN 978-1-55860-890-0.
- Dincbas, M .; Simonis, H .; Van Hentenryck, P. (1990). "Resolución de grandes problemas combinatorios en programación lógica". Revista de programación lógica . 8 (1–2): 75–93. doi : 10.1016 / 0743-1066 (90) 90052-7 .
- Freuder, Eugene; Mackworth, Alan, eds. (1994). Razonamiento basado en restricciones . Prensa del MIT. ISBN 978-0-262-56075-7.
- Frühwirth, Thom; Slim Abdennadher (2003). Fundamentos de la programación de restricciones . Saltador. ISBN 978-3-540-67623-2.
- Guesguen, Hans; Hertzberg Joachim (1992). Una perspectiva del razonamiento basado en restricciones . Saltador. ISBN 978-3-540-55510-0.
- Jaffar, Joxan; Michael J. Maher (1994). "Programación lógica de restricciones: una encuesta". Revista de programación lógica . 19/20: 503–581. doi : 10.1016 / 0743-1066 (94) 90033-7 .
- Laurière, Jean-Louis (1978). "Un lenguaje y un programa para plantear y resolver problemas combinatorios". Inteligencia artificial . 10 (1): 29-127. doi : 10.1016 / 0004-3702 (78) 90029-2 .
- Lecoutre, Christophe (2009). Redes de restricción: técnicas y algoritmos . ISTE / Wiley. ISBN 978-1-84821-106-3.
- Marriott, Kim; Peter J. Stuckey (1998). Programación con restricciones: una introducción . Prensa del MIT. ISBN 978-0-262-13341-8.
- Rossi, Francesca; Peter van Beek; Toby Walsh, eds. (2006). Manual de programación de restricciones . Elsevier. ISBN 978-0-444-52726-4. Archivado desde el original el 4 de octubre de 2012 . Consultado el 13 de octubre de 2006 .
- Tsang, Edward (1993). Fundamentos de la satisfacción de restricciones . Prensa académica. ISBN 978-0-12-701610-8.
- Van Hentenryck, Pascal (1989). Satisfacción de restricciones en la programación lógica . Prensa del MIT. ISBN 978-0-262-08181-8.
- Rashidi, Hassan .; Tsang, Edward. (2012). "Nuevos modelos de satisfacción de limitaciones para problemas de optimización en terminales de contenedores" . Revista de Modelado Matemático Aplicado . 37 (6): 3601–34. doi : 10.1016 / j.apm.2012.07.042 .
enlaces externos
- Tutorial de CSP
Videos
- Conferencia sobre satisfacción con las restricciones a cargo del Dr. Madhu Sharma (3:47)
- Introducción a los problemas de satisfacción con las restricciones por Edward Tsang (7:34)
- Problemas de satisfacción de restricciones por Wheeler Ruml (9:18)
- Conferencia sobre problemas de satisfacción con las restricciones del Instituto Indio de Tecnología de Madrás (51:59)
- Conferencia sobre CSP (1:16:39)
- Conferencia sobre problemas de satisfacción con las restricciones a cargo de Berkeley AI (1:17:38)
- Curso de posgrado en IA 5: Satisfacción de restricciones por el profesor Mausam (1:34:29)