Un problema de satisfacción de restricciones permite escribir un problema de forma resumida
en tres conjuntos importantes: las variables del problema, los valores posibles que puede
tomar cada una de las variables y las restricciones sobre cada variable. Si un problema se
logra formular con estos tres conjuntos, se le puede referir como un problema de satisfacción
de restricciones.
Existe una forma de solucionar una variedad de problemas con un acercamiento distinto a la
búsqueda en un espacio de estados donde estos mismos pueden ser evaluados por heurísticas
de un dominio específico y probados para ver si son estados finales u objetivos. Esta forma
utiliza una representación factorizada por cada estado: un conjunto de variables y cada una
con un valor. Un problema descrito de esta forma es llamado “problema de satisfacción de
restricciones”.
Desarrollo.
Los algoritmos de búsqueda de los problemas de satisfacción de restricciones aprovechan la
estructura de estados y heurísticas de propósito general más que heurística de problemas
específicos para habilitar la solución de problemas complejos. La idea principal es eliminar
gran porciones del espacio de búsqueda de una vez identificando combinaciones de
variable/valor que no respetan las restricciones.
Un problema de satisfacción de restricciones consiste de tres componentes: X, D y C.
X: conjunto de variables X1
, …, Xn
.
D: conjunto de dominios D1
, …, Dn
, para cada variable.
C: conjunto de restricciones que especifican la combinación de valores permitidas.
Cada dominio Di consiste de un conjunto de valores permitidos, {v1
, …, vk}, para cada
variable Xi
. Cada restricción Ci consiste de un par alcance/relación donde alcance es una
tupla de variables que toman parte en la restricción y relación es la conexión que define los
valores que esas variables pueden tomar. Una conexión puede ser presentada como una lista
explícita de todas las tuplas de valores que satisfacen la restricción o como una relación
abstracta que soporta dos operaciones: probar que una tupla es miento de una relación y
enumerar los miembros de una relación. Por ejemplo: si una variable X1 y X2
tienen dominio
{A, B}, entonces la restricción que indica que las dos variables deben tener valores diferentes
puede ser escrita como: <(X1
, X2), X1 ≠ X2>.
Se podría utilizar como ejemplo un puzzle de Sudoku. Es posible utilizar el algoritmo de
satisfacción de restricciones para encontrar su solución. De forma textual:
X: todos y cada uno de las cajas desde A1
, … A9
, B1
, … B9
, C1
, …, I9
.
D: todos los posibles valores que puede tomar cada variable: {1, 2, 3, 4, 5, 6, 7, 8, 9}
C: Los valores en cada fila, columna y cuadro de 3x3 no se pueden repetir.
Cada estado en un problema de satisfacción de restricciones puede ser definido por una
asignación de valores a algunas o todas las variables. Se habla de una asignación constante o
legal si dicha asignación no irrespeta ninguna de las restricciones. Una asignación completa
sucede cuando cada variable es asignada y la solución es consistente y completa. Una
asignación parcial es aquella que solo asigna valores a alguna de las variables.
Conclusión.
Los problemas de satisfacción de restricciones representan un estado en el que cada conjunto
de pares variables/valor y representa las condiciones de una solución por un conjunto de
restricciones sobre las variables. Muchos problemas importantes del mundo real pueden ser
descritos como problemas de este tipo. Por ejemplo, el problema de las n reinas donde, en un
tablero de ajedrez, la idea es colocar la máxima cantidad de reinas sin que estas se ataquen.
En otras palabras, no puede haber más de una reina en una misma fila, columna o diagonal. O
bien un problema de coloración de mapas en el que, dado un mapa y cierta cantidad de
colores, se deben colorear todas las regiones sin que dos regiones vecinas tengan el mismo
color.
Fuentes.
Russell, S. S., & Norvig, P. (1995). Artificial Intelligence: A Modern Approach. Prentice
Hall, Englewood Cliffs, NJ.