Problemas de Satisfacción de Restricciones

Un problema de satisfacción de restricciones busca una asignación de valores a un conjunto de variables que satisfaga simultáneamente todas las restricciones entre ellas, proporcionando una representación uniforme para muchos problemas combinatorios.

Definition

Un problema de satisfacción de restricciones consiste en un conjunto de variables, un dominio de valores posibles para cada una, y un conjunto de restricciones que especifican combinaciones de valores permitidas; una solución es una asignación completa que no viola ninguna restricción.

Scope

Este tema cubre el formalismo del problema de satisfacción de restricciones (CSP) (variables, dominios, restricciones) y los algoritmos que lo resuelven: búsqueda con retroceso (backtracking search) con heurísticas de ordenación de variables y valores, propagación de restricciones y técnicas de consistencia (consistencia de nodo, arco y camino, como el algoritmo AC-3), y la explotación de la estructura del problema (CSPs con estructura de árbol, condicionamiento de conjuntos de corte). Se conecta con la búsqueda local para CSPs y con la práctica más amplia de la programación con restricciones. Las formulaciones de optimización continua y basadas en el aprendizaje de problemas similares están fuera del alcance aquí.

Core questions

• ¿Cómo se plantean uniformemente diversos problemas (programación, coloración de mapas, rompecabezas) como variables, dominios y restricciones?
• ¿Cómo la propagación de restricciones poda valores antes y durante la búsqueda para reducir el retroceso?
• ¿Qué heurísticas de ordenación de variables y valores hacen eficiente la búsqueda con retroceso?
• ¿Cómo se puede explotar la estructura del grafo de restricciones (por ejemplo, ser en forma de árbol) para una resolución eficiente?

Key concepts

• variables, dominios, restricciones
• grafo de restricciones
• búsqueda con retroceso (backtracking search)
• verificación hacia adelante (forward checking)
• consistencia de arco y AC-3
• heurística de valores mínimos restantes
• propagación de restricciones
• CSPs con estructura de árbol y condicionamiento de conjuntos de corte

Key theories

Consistencia de arco y propagación de restricciones

Un CSP es consistente en arco cuando cada valor de cada variable tiene un compañero consistente en cada variable vecina; algoritmos como AC-3 imponen esto eliminando repetidamente valores no soportados, a menudo reduciendo drásticamente los dominios antes o durante la búsqueda.

Búsqueda con retroceso con heurísticas

Los CSPs se resuelven mediante asignación en profundidad con retroceso, lo que se hace práctico mediante heurísticas como elegir la variable más restringida (valores mínimos restantes), el valor menos restrictivo, y mediante la intercalación de verificación hacia adelante o propagación para detectar callejones sin salida tempranamente.

Explotación de la estructura

Cuando el grafo de restricciones es un árbol, un CSP puede resolverse en tiempo lineal con respecto al número de variables, y las estructuras casi arbóreas pueden reducirse a este caso mediante el condicionamiento de conjuntos de corte o la descomposición en árbol.

Clinical relevance

Las técnicas de CSP son el motor detrás de la programación y elaboración de horarios, la asignación de recursos, la configuración de productos, la verificación de hardware y software, y los solucionadores de rompecabezas como el Sudoku; los lenguajes de programación con restricciones y los solucionadores construidos sobre estas ideas se utilizan ampliamente en la planificación industrial y la investigación operativa.

History

Las redes de restricciones surgieron en la década de 1970 a partir del trabajo sobre etiquetado de escenas y consistencia relacional, con el artículo de Mackworth de 1977 formalizando la consistencia de nodo, arco y camino. A lo largo de las décadas de 1980 y 1990, el campo maduró hasta convertirse en la programación con restricciones, consolidada en el Handbook of Constraint Programming de 2006, y sigue siendo un tema estándar de la IA.

Key figures

• Alan K. Mackworth
• Rina Dechter
• Eugene C. Freuder
• Ugo Montanari

Seminal works

• mackworth1977
• dechter2003
• rossi2006

Frequently asked questions

¿En qué se diferencia un problema de satisfacción de restricciones de un problema de búsqueda general?

Un problema de búsqueda general trata los estados como cajas negras, pero un CSP expone la estructura interna de un estado como una asignación a variables sujeta a restricciones. Esta estructura permite a los solucionadores de CSP utilizar la propagación de restricciones y las heurísticas de ordenación que la búsqueda genérica no puede explotar.

¿Qué hace la consistencia de arco?

La consistencia de arco elimina valores del dominio de una variable que no tienen un valor compatible en una variable vecina, dada la restricción entre ellas. Imponerla antes y durante la búsqueda poda el espacio de búsqueda y a veces puede resolver un problema directamente sin retroceso.