En los algoritmos de retroceso , mirar hacia adelante 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 de la anticipación son elegir una variable para evaluar a continuación y elegir el orden de los valores que se le asignarán.
En un problema general de satisfacción de restricciones , 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 valores posibles; para cada valor el algoritmo se ejecuta recursivamente . La mirada hacia adelante se utiliza para comprobar los efectos de elegir una determinada variable para evaluarla o para decidir el orden de los valores que se le darán.
La técnica más sencilla para evaluar el efecto de una asignación específica a una variable se denomina comprobación directa . [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 de la variable considerada; luego considera todas las demás variables que aún no están asignadas y verifica si existe una evaluación que sea consistente con la solución parcial extendida. De manera más general, la verificación directa determina los valores que son consistentes con la asignación extendida.
Una técnica de anticipación que puede consumir más tiempo pero que puede producir mejores resultados se basa en la consistencia del arco . Es decir, dada una solución parcial extendida con un valor para una nueva variable, impone la coherencia del arco para todas las variables no asignadas. En otras palabras, para cualquier variable no asignada, se eliminan los valores que no se pueden extender consistentemente a otra variable. La diferencia entre la verificación directa y la coherencia del arco es que la primera solo verifica la coherencia de una única variable no asignada a la vez, mientras que la segunda también verifica la coherencia mutua de pares de variables no asignadas. La forma más común de utilizar la anticipación para resolver problemas de satisfacción de restricciones es el algoritmo de mantenimiento de coherencia de arco (MAC) . [2]
Otros dos métodos que implican la consistencia del arco son la anticipación total y parcial. Hacen cumplir la coherencia del arco, pero no para cada par de variables. En particular, la vista completa considera cada par de variables no asignadas y aplica la coherencia del arco entre ellas. Esto es diferente a imponer la coherencia del arco global, lo que posiblemente requiera reconsiderar un par de variables más de una vez. En cambio, una vez que la visión completa ha impuesto la coherencia del arco entre un par de variables, el par ya no se considera. La anticipación parcial es similar, pero se considera un orden determinado de variables y la coherencia del arco solo se aplica una vez por cada par con .
La mirada hacia adelante basada en la coherencia del arco también se puede ampliar para trabajar con coherencia de ruta y coherencia i general o coherencia de arco relacional.
Los resultados de la anticipación se utilizan para decidir la siguiente variable a evaluar y el orden de los valores a asignar a esta variable. En particular, para cualquier variable y valor no asignado, la anticipación estima los efectos de establecer esa variable en ese valor.
La elección de la siguiente variable y la elección del siguiente valor para darle son complementarias, en el sentido de que el valor generalmente se elige de tal manera que se encuentre una solución (si la hay) lo más rápido posible, mientras que la siguiente variable generalmente es elegido de tal manera que la insatisfacibilidad (si la solución parcial actual es insatisfactoria) se demuestre 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 verificando solo la satisfacibilidad o insatisfacibilidad de los pares variable/valor. En particular, la siguiente variable que se elige es la que tiene un número mínimo de valores que sean consistentes con la solución parcial actual. A su vez, la coherencia se puede evaluar simplemente comprobando la coherencia parcial o utilizando cualquiera de las técnicas de anticipación consideradas y analizadas anteriormente.
Los siguientes son tres métodos para ordenar los valores que se asignarán tentativamente a una variable:
Los experimentos demostraron que estas técnicas son útiles para problemas grandes, especialmente los de conflictos mínimos. [ cita necesaria ]
La aleatorización también se utiliza a veces para elegir una variable o valor. Por ejemplo, si dos variables son igualmente preferidas según alguna medida, la elección puede hacerse de forma aleatoria.
