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 el orden de valores que se le asignará.
Satisfacción de la restricció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 posibles valores; para cada valor, el algoritmo se ejecuta de forma recursiva . Mirar hacia adelante se usa para verificar los efectos de elegir una variable dada para evaluar o para decidir el orden de los valores que se le asignan.
Técnicas de anticipación
La técnica más simple para evaluar el efecto de una asignación específica a una variable se llama verificació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 todavía está sin asignar, y comprueba si existe una evaluación de eso es consistente con la solución parcial extendida. De manera más general, la verificación anticipada determina los valores para que sean coherentes con la asignación ampliada.
Una técnica de anticipación que puede llevar más tiempo pero que puede producir mejores resultados se basa en la consistencia del arco . Es decir, dada una solución parcial ampliada 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 pueden extenderse consistentemente a otra variable. La diferencia entre la verificación directa y la consistencia del arco es que la primera solo verifica una sola variable no asignada a la vez para verificar la consistencia, mientras que la segunda también verifica pares de variables no asignadas para verificar la consistencia mutua. 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 coherencia 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 asignadasy refuerza la coherencia del arco entre ellos. Esto es diferente a imponer la coherencia del arco global, que posiblemente requiera que un par de variables se reconsideren más de una vez. En cambio, una vez que la visión completa hacia adelante ha reforzado 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 dado de variables y la consistencia del arco solo se aplica una vez por cada par. con .
La mirada hacia el futuro basada en la consistencia del arco también se puede extender para trabajar con consistencia de ruta y consistencia i general o consistencia de arco relacional.
Uso de mirar hacia adelante
Los resultados de mirar hacia adelante se utilizan para decidir la siguiente variable a evaluar y el orden de valores que se le dará a esta variable. En particular, para cualquier variable y valor no asignados, 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, ya que el valor se elige típicamente de tal manera que se encuentra una solución (si la hay) lo más rápido posible, mientras que la siguiente variable se elige típicamente de tal manera, la insatisfacción (si la solución parcial actual no es satisfactoria) se prueba lo más rápidamente 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 antes posible, las variables que dejan pocas alternativas después de asignadas son las preferidas. Esta idea se puede implementar comprobando solo la satisfacción o insatisfacción de los pares de 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 puede evaluarse simplemente verificando la consistencia parcial o utilizando cualquiera de las técnicas de anticipación consideradas discutidas anteriormente.
Los siguientes son tres métodos para ordenar los valores que se asignarán provisionalmente a una variable:
- min-conflictos: los valores preferidos son aquellos que eliminan los menores valores totales del dominio de las variables no asignadas según se evalúa con anticipación;
- max-domain-size: la preferencia de una variable es inversamente el número de valores en el dominio más pequeño que producen para las variables no asignadas, según lo evaluado por mirar hacia adelante;
- estimar soluciones: los valores preferidos son aquellos que producen el número máximo de soluciones, según se evalúa mirando hacia adelante, asumiendo que todos los valores que quedan en los dominios de las variables no asignadas son consistentes entre sí; en otras palabras, la preferencia por un valor se obtiene multiplicando el tamaño de todos los dominios resultantes de mirar hacia adelante.
Los experimentos demostraron que estas técnicas son útiles para problemas grandes, especialmente los de conflictos mínimos. [ cita requerida ]
La aleatorización también se usa a veces para elegir una variable o un valor. Por ejemplo, si dos variables son igualmente preferidas de acuerdo con alguna medida, la elección se puede hacer al azar.
Referencias
- ^ RM Haralick y GL Elliot (1980), " Aumento de la eficiencia de búsqueda de árboles para problemas de satisfacción de restricciones ". Inteligencia artificial , 14, págs. 263–313.
- ^ Sabin, Daniel y Eugene C. Freuder (1994), " Contradiciendo la sabiduría convencional en la satisfacción de restricciones ". Principios y práctica de la programación de restricciones, págs. 10-20.
- Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann.ISBN 1-55860-890-7
- Ouyang, Ming (1998). "¿Qué tan buenas son las reglas de ramificación en DPLL?". Matemáticas aplicadas discretas . 89 (1-3): 281-286. doi : 10.1016 / S0166-218X (98) 00045-6 .