Satisfacción de Restricciones

Un problema de satisfacción de restricciones (CSP) es un modelo formal que se define con tres elementos: un conjunto de variables, un dominio de valores posibles para cada variable, y un conjunto de restricciones que limitan qué combinaciones de valores están permitidas. Una solución es una asignación de un valor a cada variable, tomado de su dominio, que satisface todas las restricciones a la vez.

Ejemplos

Muchos problemas dispares comparten esa estructura, y por eso se pueden resolver con los mismos algoritmos. En el coloreado de un mapa, las variables son las regiones, el dominio son los colores y la restricción es que dos regiones vecinas no tengan el mismo color. El Sudoku, el problema de las N reinas o la elaboración de horarios son también problemas de satisfacción de restricciones.

Cómo se resuelven

El algoritmo base es la búsqueda con retroceso (backtracking): asigna valores a las variables uno a uno y, cuando una asignación parcial viola una restricción, deshace la última y prueba otra. Se combina con la propagación de restricciones, que poda valores imposibles antes de seguir; la técnica clásica es la consistencia de arco (el algoritmo AC-3). Y con heurísticas de ordenación, como elegir primero la variable con menos valores legales restantes, o el valor que menos limita a las demás.

Satisfacción frente a optimización

Conviene distinguir dos metas. Un CSP de satisfacción busca cualquier asignación que cumpla todas las restricciones, o determinar que no existe: todas las soluciones válidas valen igual. Un problema de optimización con restricciones añade una función objetivo y busca la mejor solución según ella. Y cuando las restricciones no pueden cumplirse todas a la vez, la variante MAX-CSP busca la asignación que satisface el mayor número posible.