Guiada Por Datos

Tema 3.6.1

!! Algoritmos look-ahead: Forward Checking

Los algoritmos look-back tratan de reforzar el comportamiento de Bactracking mediante un comportamiento mas inteligente cuando se encuentran en situaciones sin salida. Sin embargo, todos ellos todavía llevan a cabo la comprobación de la consistencia solamente hacia atrás, ignorando las futuras variables. Los algoritmos Look-ahead hacen una comprobación hacia adelante en cada etapa de la búsqueda, es decir, ellos llevan a cabo las comprobaciones para obtener las inconsistencias de las variables futuras involucradas además de las variables actual y pasadas. De esa manera, las situaciones sin salida se pueden identificar antes y además los valores inconsistentes se pueden descubrir y podar para las variables futuras

Si el dominio de una variable futura se queda vacío, la instanciacion de la variable actual se deshace y se prueba con un nuevo valor. Si ningún valor es consistente, entonces se lleva a cabo el backtracking cronológico. FC garantiza que, en cada etapa, la solución parcial actual es consistente con cada valor de cada variable futura. A continuación presentamos el pseudoscódigo de forward checking.

Proceso Forward-checking

1. Seleccionar xi.

2. Instanciar xi← ai: ai Є Di..

3. Razonar hacia adelante (check-forward): Eliminar de los dominios de las variables, aun no instanciadas con un valor, aquellos valores inconsistente con respecto a la instanciacion xi← ai, de acuerdo al conjunto de restricciones.

4. Si quedan valores posibles en los dominios de todas las variables por instanciar, entonces: • Si i < n, incrementar i, e ir al paso (1). • Si i = n, salir con la solución.

5. Si existe una variable por instanciar, sin valores posibles en su dominio, entonces retractar los efectos de la asignacion xi← ai: • Si quedan valores por intentar en Di, ir al paso (2). • Si no quedan valores: • Si i > 1, decrementar i y volver al paso (2). • Si i = 1, salir sin solución.

Minimal forward checking (MFC) es una versión de FC que retrasa llevar a cabo todo la comprobación de la consistencia de FC hasta que es absolutamente necesario. En vez de comprobar hacia adelante la asignación actual contra todas las variables futuras, MFC solo comprueba si la asignación actual causa una limpieza de dominios. Para hacer esto es suficiente comprobar la asignación actual con los valores de cada variable futura hasta que se encuentra una que es consistente. Después, si el algoritmo ha retrocedido, vuelve atrás y lleva a cabo las comprobaciones ’perdidas’. Claramente, MFC siempre lleva a cabo a lo sumo el mismo número de comprobaciones que FC. Resultados experimentales han demostrado que la ganancia no supera el 10 %.

Autor: Ponce González Jesús Antonio
E-mail: listoa@hotmail.com
its pto. vta. 1ro b isc