Aprendizaje de restricciones

En los algoritmos de seguimiento de satisfacción de restricciones , el aprendizaje de 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 es posible que futuras evaluaciones parciales resulten 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 .

Los algoritmos de retroceso funcionan eligiendo una variable no asignada y resuelven recursivamente los problemas obtenidos al asignar un valor a esta variable. Siempre que se encuentre que la solución parcial actual es inconsistente, el algoritmo vuelve a la variable asignada previamente, como se espera por la recursión. 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 posterior 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á a partir de esta solución, mientras que el algoritmo de retroceso original realizarí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 cierta para todos al mismo tiempo. Sin embargo, registrar esta restricción no es útil, ya que esta solución parcial no se encontrará nuevamente debido a la forma en que se realiza el retroceso. ${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$${\displaystyle x_{i}=a_{i}}$${\displaystyle i\in [1,k]}$

Por otra parte, 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 aparecer nuevamente en la búsqueda. Por ejemplo, el algoritmo puede encontrar una evaluación que extienda el subconjunto de la evaluación parcial anterior. Si este subconjunto es inconsistente y el algoritmo ha almacenado este hecho en forma de restricción, no se necesita una búsqueda adicional para concluir que la nueva evaluación parcial no se puede extender para formar una solución. ${\displaystyle x_{2}=a_{2},x_{5}=a_{5},x_{k-1}=a_{k-1}}$

La ganancia de eficiencia del aprendizaje de restricciones se equilibra entre dos factores. Por un lado, cuanto más a menudo se viola una restricción registrada, más a menudo el retroceso evita realizar búsquedas inútiles. Los subconjuntos pequeños e 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 subconjunto pequeño e inconsistente de la evaluación parcial actual puede requerir tiempo, y el beneficio puede no verse compensado por la reducción posterior del tiempo de búsqueda.

Sin embargo, el tamaño no es la única característica de las restricciones aprendidas que se debe tener en cuenta. De hecho, una restricción pequeña puede ser inútil en un estado particular del espacio de búsqueda porque los valores que la violan no se encontrarán nuevamente. En tales casos, puede ser preferible una restricción mayor cuyos valores violatorios sean más similares a la asignación parcial actual.

Existen varias técnicas de aprendizaje de restricciones, que difieren en la rigurosidad de las restricciones registradas y el costo de encontrarlas.

Si el algoritmo demuestra que todos los valores de son inconsistentes 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 junto con todos contienen . $estilo de visualización x_{k+1}}$${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$$estilo de visualización x_{k+1}}$$estilo de visualización x_{k+1}}$${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$$estilo de visualización x_{k+1}}$

Como resultado, una evaluación inconsistente es la restricción de la evaluación de verdad de a las variables que están en una restricción con , siempre que esta restricción no contenga ninguna variable no asignada. ${\displaystyle x_{1},\ldots ,x_{k}}$$estilo de visualización x_{k+1}}$

El aprendizaje de restricciones que representan estas evaluaciones parciales se denomina aprendizaje basado en gráficos. Utiliza el mismo fundamento del backjumping basado en gráficos . Estos métodos se denominan "basados ​​en gráficos" porque se basan en pares de variables en la misma restricción, que se pueden encontrar a partir del gráfico asociado al problema de satisfacción de la restricción.

El aprendizaje retroactivo se basa en almacenar como restricciones las asignaciones inconsistentes que se encontrarían mediante un salto hacia atrás basado en conflictos . Siempre que se encuentra una asignación parcial inconsistente, este algoritmo selecciona la restricción violada que sea 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 suele ser más corta que la evaluación completa. El aprendizaje retroactivo almacena este hecho como una nueva restricción.

El orden de las restricciones se basa en el orden de asignación de las variables. En particular, la restricción menor de dos es aquella cuya última variable no común se haya instanciado primero. Cuando se alcanza una asignación inconsistente, el aprendizaje retroactivo selecciona la restricción violada que sea mínima de acuerdo con este orden y restringe la asignación actual a sus variables. La restricción que expresa la inconsistencia de esta asignación se almacena.

Los algoritmos de aprendizaje de restricciones difieren no sólo 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é restricciones conservan 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 restricciones ocasionalmente.

El aprendizaje limitado 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 relevancia descarta 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.

• Mirar hacia adelante (retroceder)
• Salto hacia atrás

• Dechter, Rina (2003). Procesamiento de restricciones. Morgan Kaufmann. ISBN  1-55860-890-7