Un problema que satisface restricciones (PSR) es un tipo especial de problema en el cual los estados se definen mediante los valores de un conjunto de variables, y la prueba de meta especifica un conjunto de restricciones que los valores deben satisfacer. Cada variable tiene un dominio que puede ser discreto o continuo. El estado del problema es definido por una asignación de valores a algunas o todas las variables. La solución de un PSR especifica valores para todas las variables de manera tal que se satisfagan las restricciones.
Definir el problema.
Las condiciones de inicio/meta.
Reglas como conjunto de IF... THEN....
Y estrategias para el control de la aplicación de las reglas.
Prueba de meta: ahora hay restricciones en los valores que pueden tener las variables (deben satisfacerse en la meta). La Prueba de meta es una serie de restricciones a las variables que hay que satisfacer.
Búsqueda
Primero en Profundidad:
sirve bastante bien pues la profundidad coincide con n, el número de
variables - pero se pierde tiempo porque como es ciega
no aplica inteligencia.
Búsqueda
por Backtracking (Reversiva):
aplica inteligencia pues verifica a lo largo de la ruta el test de meta y
apenas hay un error, vuelve atrás y retoma otra bifurcación. Aplica el
test después de cada asignación de una variable, en lugar de solo hacerlo
al final de las asignaciones.
Verificación
anticipada (Forward checking): a medida que los operadores les van asignando valores a las
variables, se va llevando una prolija constancia del saldo de los sitios que
no son tabú, con vistas a las asignaciones faltantes. Si ese saldo es cero,
enseguida se revierte.
Consistencia
de arcos:
aplica sistemáticamente un sistema de borrado de sitios que pasan a
ser tabú al asignar un valor a una variable.
Propagación de Restricciones: es una consecuencia de la consistencia de arcos - a medida que se van borrando valores, como éstos estaban basados en otros valores, lo que era congruente se volverá incongruente.
Casi
todas las búsquedas anteriores eran irrestrictas a excepción de 8 reinas
que era búsqueda por repetidos. Por lo que si hay restricciones no hay que
buscar en tantos lados que son un tabú.
Aparecen
nuevas propiedades estructurales.
Estado
- aplicando el algoritmo de uso general, de entrada ninguna variable estará
asignada. El primer valor asignado lo será por los operadores que elegirán
algún valor posible.
