Tema
Satisfacción de restricciones
- IA clásica
- Nivel intermedio
Un problema de satisfacción de restricciones se define por un conjunto de variables, un dominio de valores para cada una y un conjunto de restricciones, y se resuelve asignando un valor a cada variable sin violar ninguna restricción.
Nombre en inglés
Constraint satisfaction problems
Intuición
Al describir el problema como variables y restricciones en lugar de como estados opacos, el algoritmo puede mirar dentro del estado y descartar valores imposibles antes de probarlos. El retroceso cronológico se vuelve viable gracias a tres ayudas, que son elegir primero la variable con menos valores legales, elegir el valor que menos opciones quita a las vecinas y propagar las restricciones para vaciar dominios cuanto antes.
Fórmula
arco (X_i, X_j) consistente si para todo a en D_i existe b en D_j con (a, b) permitido. AC-3 cuesta O(e d^3)
Ejemplo resuelto
Tres regiones vecinas entre sí, A, B y C, se colorean con rojo, verde y azul sin que dos vecinas compartan color. Si A se fija en rojo, la propagación quita el rojo de los dominios de B y de C, que quedan con dos valores cada uno. Al elegir B en verde, la propagación deja a C con un solo valor, el azul, de modo que la solución sale sin ningún retroceso. Con una cuarta región D vecina solo de A, su dominio conserva dos valores y la regla de mínimos valores restantes la deja para el final.
Errores frecuentes
- Confundir consistencia de arco con solución, ya que un problema puede quedar arco consistente y seguir sin tener ninguna asignación completa válida.
- Aplicar la regla de mínimos valores restantes al revés eligiendo la variable con más valores legales, lo que retrasa el fallo en lugar de adelantarlo y multiplica el retroceso.
- Comprobar hacia adelante solo los vecinos inmediatos y suponer que eso detecta todos los callejones sin salida, cuando la propagación completa alcanza vecinos a dos o más saltos.
Ejercicio
Dos variables X e Y tienen dominio {1, 2, 3} y la restricción X < Y. Aplica consistencia de arco y escribe los dominios resultantes.
Ver la solución
Para el arco que va de X a Y se busca, por cada valor de X, algún valor de Y mayor. El 1 y el 2 lo tienen, pero el 3 no encuentra ningún Y mayor que 3, de modo que el 3 sale del dominio de X. Para el arco que va de Y a X se busca, por cada valor de Y, algún X menor. El 2 y el 3 lo tienen, pero el 1 no, de modo que el 1 sale del dominio de Y. Los dominios quedan reducidos y ninguno se vacía, luego el problema sigue siendo consistente.
Respuesta: X en {1, 2} e Y en {2, 3}.