En los algoritmos de retroceso de la satisfacción por restricciones , el aprendizaje por restricciones es una técnica para mejorar la eficiencia. Funciona registrando nuevas restricciones cada vez que se encuentra una inconsistencia. Esta nueva restricción puede reducir el espacio de búsqueda , ya que las evaluaciones parciales futuras pueden resultar inconsistentes sin una búsqueda adicional. El aprendizaje de cláusulas es el nombre de esta técnica cuando se aplica a la satisfacibilidad proposicional .
Definición
Los algoritmos de retroceso funcionan eligiendo una variable no asignada y resuelven recursivamente los problemas obtenidos asignando un valor a esta variable. Siempre que la solución parcial actual se encuentra inconsistente, el algoritmo vuelve a la variable asignada previamente, como se esperaba por recursividad. Un algoritmo de aprendizaje de restricciones se diferencia porque intenta registrar cierta información, antes de retroceder, en forma de una nueva restricción. Esto puede reducir la búsqueda adicional porque la búsqueda posterior puede encontrar otra solución parcial que sea inconsistente con esta nueva restricción. Si el algoritmo ha aprendido la nueva restricción, retrocederá desde esta solución, mientras que el algoritmo de retroceso original haría una búsqueda posterior.
Si la solución parcial es inconsistente, la instancia del problema implica la restricción que establece que no puede ser verdad para todos al mismo tiempo. Sin embargo, registrar esta restricción no es útil, ya que esta solución parcial no se volverá a encontrar debido a la forma en que se produce el retroceso.
Por otro lado, si un subconjunto de esta evaluación es inconsistente, la restricción correspondiente puede ser útil en la búsqueda posterior, ya que el mismo subconjunto de la evaluación parcial puede ocurrir nuevamente en la búsqueda. Por ejemplo, el algoritmo puede encontrar una evaluación que amplíe el subconjuntode la evaluación parcial anterior. Si este subconjunto es inconsistente y el algoritmo ha almacenado este hecho en forma de restricción, no se necesitan más búsquedas para concluir que la nueva evaluación parcial no se puede extender para formar una solución.
La búsqueda ha llegado a un callejón sin salida. | La inconsistencia puede ser causada por los valores de y solo. Este hecho se puede almacenar en una nueva restricción. | Si el algoritmo alcanza los mismos valores de y de nuevo, la nueva restricción bloquea la búsqueda. |
Eficiencia del aprendizaje por restricciones
La eficiencia del algoritmo de aprendizaje por restricciones se equilibra entre dos factores. Por un lado, cuanto más a menudo se infringe una restricción registrada, más a menudo se evita el retroceso de búsquedas inútiles. Los subconjuntos pequeños inconsistentes de la solución parcial actual suelen ser mejores que los grandes, ya que corresponden a restricciones que son más fáciles de violar. Por otro lado, encontrar un pequeño subconjunto inconsistente de la evaluación parcial actual puede requerir tiempo, y el beneficio puede no ser compensado por la subsiguiente reducción del tiempo de búsqueda.
Sin embargo, el tamaño no es la única característica de las limitaciones aprendidas a tener en cuenta. De hecho, una pequeña restricción puede ser inútil en un estado particular del espacio de búsqueda porque los valores que la violan no se volverán a encontrar. En tales casos, puede ser preferible una restricción mayor cuyos valores infractores sean más similares a la asignación parcial actual.
Existen varias técnicas de aprendizaje de restricciones, que difieren en el rigor de las restricciones registradas y el costo de encontrarlas.
Aprendizaje basado en gráficos
Si el algoritmo prueba todos los valores de ser inconsistente con , entonces esta evaluación fue consistente, ya que de lo contrario el algoritmo no habría evaluado en absoluto; como resultado, las restricciones violadas por un valor de Juntos con todos contienen .
Como resultado, una evaluación inconsistente es la restricción de la evaluación de la verdad de a las variables que están en una restricción con , siempre que esta restricción no contenga ninguna variable sin asignar.
Las limitaciones de aprendizaje que representan estas evaluaciones parciales se denominan aprendizaje basado en gráficos. Utiliza la misma lógica del backjumping basado en gráficos . Estos métodos se denominan "basados en gráficos" porque se basan en pares de variables que se encuentran en la misma restricción, que se puede encontrar en el gráfico asociado al problema de satisfacción de la restricción.
Aprendizaje Jumpback
El aprendizaje con Jumpback se basa en almacenar como restricciones las asignaciones inconsistentes que se encontrarían con el backjumping basado en conflictos . Siempre que una asignación parcial se encuentra inconsistente, este algoritmo selecciona la restricción violada que es mínima de acuerdo con un orden basado en el orden de instanciación de las variables. La evaluación restringida de las variables que están en esta restricción es inconsistente y generalmente es más corta que la evaluación completa. El aprendizaje por salto almacena este hecho como una nueva restricción.
El orden de las restricciones se basa en el orden de asignación de la variable. En particular, la restricción menor de dos es aquella cuya última variable no común se ha instanciado primero. Cuando se alcanza una asignación inconsistente, el aprendizaje por salto selecciona la restricción violada que es mínima de acuerdo con este orden y restringe la asignación actual a sus variables. Se almacena la restricción que expresa la inconsistencia de esta asignación.
Mantenimiento de restricciones
Los algoritmos de aprendizaje de restricciones difieren no solo en la elección de la restricción correspondiente a una evaluación parcial inconsistente dada, sino también en la elección de qué restricción mantienen y cuáles descartan.
En general, aprender todas las inconsistencias en forma de restricciones y mantenerlas indefinidamente puede agotar la memoria disponible y aumentar el costo de verificar la consistencia de las evaluaciones parciales. Estos problemas se pueden resolver almacenando solo algunas restricciones aprendidas o descartando ocasionalmente las restricciones.
El aprendizaje acotado solo almacena restricciones si la evaluación parcial inconsistente que representan es menor que un número de restricción dado. El aprendizaje limitado por la relevancia descarta las restricciones (o no las almacena en absoluto) que se consideran no relevantes dado el punto actual del espacio de búsqueda; en particular, descarta o no almacena todas las restricciones que representan evaluaciones parciales inconsistentes que difieren de la evaluación parcial actual en no más de un número fijo dado de variables.
Ver también
Referencias
- Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann.ISBN 1-55860-890-7