En los algoritmos de retroceso , "look-ahead" es el término genérico para un subprocedimiento que intenta prever los efectos de elegir una variable de ramificación para evaluar uno de sus valores. Los dos objetivos principales del "look-ahead" son elegir una variable para evaluar a continuación y elegir el orden de los valores que se le asignarán.
En un problema de satisfacción de restricciones generales , cada variable puede tomar un valor en un dominio. Por lo tanto, un algoritmo de retroceso elige iterativamente una variable y prueba cada uno de sus posibles valores; para cada valor, el algoritmo se ejecuta de forma recursiva . La anticipación se utiliza para verificar los efectos de elegir una variable dada para evaluar o para decidir el orden de los valores que se le asignarán.
La técnica más simple para evaluar el efecto de una asignación específica a una variable se denomina verificación hacia adelante . [1] Dada la solución parcial actual y una asignación candidata para evaluar, verifica si otra variable puede tomar un valor consistente. En otras palabras, primero extiende la solución parcial actual con el valor tentativo para la variable considerada; luego considera todas las demás variables que aún no están asignadas y verifica si existe una evaluación de que sea consistente con la solución parcial extendida. De manera más general, la verificación hacia adelante determina los valores para que son consistentes con la asignación extendida.
Una técnica de anticipación que puede requerir más tiempo pero que puede producir mejores resultados se basa en la consistencia de arco . Es decir, dada una solución parcial extendida con un valor para una nueva variable, aplica la consistencia de arco para todas las variables no asignadas. En otras palabras, para cualquier variable no asignada, se eliminan los valores que no se pueden extender de manera consistente a otra variable. La diferencia entre la verificación hacia adelante y la consistencia de arco es que la primera solo verifica la consistencia de una sola variable no asignada a la vez, mientras que la segunda también verifica pares de variables no asignadas para verificar su consistencia mutua. La forma más común de usar la anticipación para resolver problemas de satisfacción de restricciones es el algoritmo de mantenimiento de la consistencia de arco (MAC) . [2]
Otros dos métodos que implican la consistencia de arco son la mirada anticipada completa y parcial. Estos métodos imponen la consistencia de arco, pero no para cada par de variables. En particular, la mirada anticipada completa considera cada par de variables no asignadas y hace cumplir la consistencia de arco entre ellas. Esto es diferente a la imposición de la consistencia de arco global, que posiblemente requiera que un par de variables se reconsidere más de una vez. En cambio, una vez que la mirada anticipada completa ha impuesto la consistencia de arco entre un par de variables, el par ya no se considera. La mirada anticipada parcial es similar, pero se considera un orden dado de variables y la consistencia de arco solo se impone una vez para cada par con .
La mirada hacia adelante basada en la consistencia del arco también se puede ampliar para trabajar con la consistencia de ruta y la i-consistencia general o la consistencia del arco relacional.
Los resultados de la previsión se utilizan para decidir la siguiente variable que se evaluará y el orden de los valores que se le asignarán. En particular, para cualquier variable y valor no asignado, la previsión estima los efectos de asignarle ese valor a esa variable.
La elección de la siguiente variable y la elección del siguiente valor que se le dará son complementarias, en el sentido de que el valor se elige típicamente de tal manera que se encuentre una solución (si la hay) lo más rápido posible, mientras que la siguiente variable se elige típicamente de tal manera que se demuestre la insatisfacbilidad (si la solución parcial actual es insatisfacible) lo más rápido posible.
La elección de la siguiente variable a evaluar es particularmente importante, ya que puede producir diferencias exponenciales en el tiempo de ejecución. Para demostrar la insatisfacción lo más rápido posible, las variables que dejan pocas alternativas después de ser asignadas son las preferidas. Esta idea se puede implementar comprobando solo la satisfacibilidad o insatisfacción de pares variable/valor. En particular, la siguiente variable que se elige es la que tiene un número mínimo de valores que son consistentes con la solución parcial actual. A su vez, la consistencia se puede evaluar simplemente comprobando la consistencia parcial o utilizando cualquiera de las técnicas de anticipación consideradas que se analizaron anteriormente.
Los siguientes son tres métodos para ordenar los valores que se asignarán tentativamente a una variable:
Los experimentos han demostrado que estas técnicas son útiles para problemas de gran magnitud, especialmente aquellos con mínimos conflictos. [ cita requerida ]
La aleatorización también se utiliza a veces para elegir una variable o un valor. Por ejemplo, si dos variables tienen la misma preferencia según alguna medida, la elección puede hacerse de forma aleatoria.
