salto hacia atrás

En la programación con restricciones y la resolución de problemas SAT , el retroceso (también conocido como retroceso no cronológico ^{[ 1 ]} o retroceso inteligente ^{[ 2 ]} ) es una mejora para los algoritmos de retroceso que reduce el espacio de búsqueda . Mientras que el retroceso siempre sube un nivel en el árbol de búsqueda cuando se han probado todos los valores de una variable, el retroceso puede subir más niveles. En este artículo, se establece un orden fijo de evaluación de variables.${\displaystyle x_{1},\ldots ,x_{n}}$Se utiliza, pero las mismas consideraciones se aplican a un orden de evaluación dinámico.

• 
  Un árbol de búsqueda visitado mediante retroceso regular.
• 
  Un salto hacia atrás: el nodo gris no se visita.

Siempre que el retroceso haya probado todos los valores para una variable sin encontrar ninguna solución, reconsidera la última de las variables asignadas previamente, cambiando su valor o retrocediendo aún más si no hay otros valores que probar.${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$es la asignación parcial actual y todos los valores para${\displaystyle x_{k+1}}$Se han intentado sin encontrar una solución, retrocediendo se concluye que no hay ninguna solución que extienda ${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$existe. El algoritmo luego "sube" a${\displaystyle x_{k}}$, cambiando${\displaystyle x_{k}}$valor de si es posible, retrocediendo de nuevo en caso contrario.

La asignación parcial no siempre es necesaria en su totalidad para probar que ningún valor de${\displaystyle x_{k+1}}$conduce a una solución. En particular, un prefijo de la asignación parcial puede tener la misma propiedad, es decir, existe un índice.${\displaystyle j<k}$de tal manera que${\displaystyle x_{1},\ldots ,x_{j}=a_{1},\ldots ,a_{j}}$no se puede extender para formar una solución con cualquier valor para${\displaystyle x_{k+1}}$. Si el algoritmo puede demostrar este hecho, puede considerar directamente un valor diferente para${\displaystyle x_{j}}$en lugar de reconsiderar${\displaystyle x_{k}}$como lo haría normalmente.

• 
  Un ejemplo en el que la asignación actual a${\displaystyle x_{1}x_{2}x_{3}x_{4}}$Se ha intentado sin éxito con todos los valores posibles de${\displaystyle x_{5}}$. El retroceso nos lleva de vuelta a${\displaystyle x_{4}}$, intentando asignarle un nuevo valor.
• 
  En lugar de retroceder, el algoritmo realiza una elaboración adicional, demostrando que las evaluaciones${\displaystyle x_{1}x_{2}x_{5}=211}$,${\displaystyle x_{1}x_{2}x_{5}=212}$, y${\displaystyle x_{1}x_{2}x_{5}=213}$no forman parte de ninguna solución.
• 
  Como resultado, la evaluación actual de${\displaystyle x_{1}x_{2}}$no forma parte de ninguna solución, y el algoritmo puede retroceder directamente a${\displaystyle x_{2}}$, probando un nuevo valor para ello.

La eficiencia de un algoritmo de retroceso depende de cuán alto sea capaz de retroceder. Idealmente, el algoritmo podría saltar desde${\displaystyle x_{k+1}}$a cualquier variable${\displaystyle x_{j}}$es tal que la asignación actual a${\displaystyle x_{1},\ldots ,x_{j}}$no se puede extender para formar una solución con ningún valor de${\displaystyle x_{k+1}}$Si este es el caso,${\displaystyle j}$Se denomina salto seguro .

Determinar si un salto es seguro no siempre es factible, ya que los saltos seguros se definen en términos del conjunto de soluciones, que es precisamente lo que el algoritmo intenta encontrar. En la práctica, los algoritmos de retroceso utilizan el índice más bajo que pueden demostrar eficientemente que corresponde a un salto seguro. Los distintos algoritmos emplean diferentes métodos para determinar la seguridad de un salto. Estos métodos tienen distintos costes, pero un mayor coste para encontrar un salto seguro de mayor nivel puede compensarse con una menor cantidad de búsqueda debido a la omisión de partes del árbol de búsqueda.

La condición más simple en la que es posible el retroceso es cuando se ha demostrado que todos los valores de una variable son inconsistentes sin ramificaciones adicionales. En la satisfacción de restricciones , una evaluación parcial es consistente si y solo si satisface todas las restricciones que involucran a las variables asignadas, e inconsistente en caso contrario. Puede darse el caso de que una solución parcial consistente no pueda extenderse a una solución completa consistente porque algunas de las variables no asignadas no pueden asignarse sin violar otras restricciones.

La condición en la que todos los valores de una variable dada son iguales${\displaystyle x_{k+1}}$son incompatibles con la solución parcial actual${\displaystyle x_{1},\ldots ,x_{k}=a_{1},\ldots ,a_{k}}$Se denomina callejón sin salida de hoja . Esto ocurre exactamente cuando la variable${\displaystyle x_{k+1}}$es una hoja del árbol de búsqueda (que corresponde a los nodos que tienen solo hojas como hijos en las figuras de este artículo).

El algoritmo de retroceso de John Gaschnig realiza un retroceso solo en los callejones sin salida de las hojas. ^{[ 3 ]} En otras palabras, funciona de manera diferente al retroceso solo cuando cada valor posible de${\displaystyle x_{k+1}}$Se ha probado y ha dado como resultado inconsistente sin necesidad de ramificar sobre otra variable.

Se puede encontrar un salto seguro simplemente evaluando, para cada valor${\displaystyle a_{k+1}}$, el prefijo más corto de${\displaystyle x_{1},\ldots ,x_{k}=a_{1},\ldots ,a_{k}}$incompatible con${\displaystyle x_{k+1}=a_{k+1}}$. En otras palabras, si${\displaystyle a_{k+1}}$es un valor posible para${\displaystyle x_{k+1}}$El algoritmo comprueba la coherencia de las siguientes evaluaciones:

El índice más pequeño (el más bajo de la lista) para el cual las evaluaciones son inconsistentes sería un salto seguro si${\displaystyle x_{k+1}=a_{k+1}}$eran el único valor posible para${\displaystyle x_{k+1}}$Dado que cada variable suele poder tomar más de un valor, el índice máximo que resulta de la comprobación de cada valor es un salto seguro, y es el punto donde salta el algoritmo de John Gaschnig.

En la práctica, el algoritmo puede verificar las evaluaciones anteriores al mismo tiempo que verifica la consistencia de${\displaystyle x_{k+1}=a_{k+1}}$.

El algoritmo anterior solo retrocede cuando se puede demostrar que los valores de una variable son inconsistentes con la solución parcial actual sin ramificaciones adicionales. En otras palabras, solo permite retroceder en los nodos hoja del árbol de búsqueda.

Un nodo interno del árbol de búsqueda representa una asignación de variable consistente con las anteriores. Si ninguna solución extiende esta asignación, el algoritmo anterior siempre retrocede: en este caso no se realiza ningún salto hacia atrás.

El backjumping en nodos internos no se puede realizar como en los nodos hoja. De hecho, si algunas evaluaciones de${\displaystyle x_{k+1}}$Se requiere ramificación porque son consistentes con la asignación actual. Como resultado, la búsqueda de un prefijo que sea inconsistente con estos valores de la última variable no tiene éxito.

En tales casos, lo que demostró una evaluación${\displaystyle x_{k+1}=a_{k+1}}$no formar parte de una solución con la evaluación parcial actual${\displaystyle x_{1},\ldots ,x_{k}}$Se trata de una búsqueda recursiva . En concreto, el algoritmo "sabe" que no existe ninguna solución a partir de este punto porque regresa a este nodo en lugar de detenerse tras haber encontrado una solución.

Este retorno se debe a varios callejones sin salida , puntos donde el algoritmo ha demostrado que una solución parcial es inconsistente. Para retroceder aún más, el algoritmo debe tener en cuenta que la imposibilidad de encontrar soluciones se debe a estos callejones sin salida. En particular, los saltos seguros son índices de prefijos que aún hacen que estos callejones sin salida sean soluciones parciales inconsistentes.

• 
  En este ejemplo, el algoritmo vuelve a${\displaystyle x_{k+1}}$, después de probar todos sus valores posibles, debido a los tres puntos cruzados de inconsistencia.
• 
  El segundo punto sigue siendo inconsistente incluso si los valores de${\displaystyle x_{k-1}}$y${\displaystyle x_{k}}$se eliminan de su evaluación parcial (tenga en cuenta que los valores de una variable están en sus hijos)
• 
  Las otras evaluaciones inconsistentes siguen siendo así incluso sin${\displaystyle x_{k-2}}$,${\displaystyle x_{k-1}}$, y${\displaystyle x_{k}}$
• 
  El algoritmo puede retroceder a${\displaystyle x_{k-2}}$ya que esta es la variable más baja que mantiene todas las inconsistencias. Un nuevo valor para${\displaystyle x_{k-2}}$Se intentará.

En otras palabras, cuando todos los valores de${\displaystyle x_{k+1}}$Se han intentado, el algoritmo puede retroceder a una variable anterior.${\displaystyle x_{i}}$siempre que la evaluación de la verdad actual de${\displaystyle x_{1},\ldots ,x_{i}}$es inconsistente con todas las evaluaciones de verdad de${\displaystyle x_{k+1},x_{k+2},...}$en los nodos hoja que son descendientes del nodo${\displaystyle x_{k+1}}$.

Simplificaciones

Debido al número potencialmente alto de nodos que se encuentran en el subárbol de${\displaystyle x_{k+1}}$, la información que es necesaria para retroceder de forma segura desde${\displaystyle x_{k+1}}$se recopila durante la visita a su subárbol. Encontrar un salto seguro se puede simplificar mediante dos consideraciones. La primera es que el algoritmo necesita un salto seguro, pero aún así funciona con un salto que no es el salto seguro más alto posible.

La segunda simplificación es que los nodos en el subárbol de${\displaystyle x_{l}}$que se hayan omitido mediante un salto hacia atrás pueden ignorarse mientras se busca un salto hacia atrás para${\displaystyle x_{l}}$. Más precisamente, todos los nodos omitidos mediante un salto hacia atrás desde el nodo${\displaystyle x_{m}}$hasta el nodo${\displaystyle x_{l}}$son irrelevantes para el subárbol enraizado en${\displaystyle x_{m}}$y también son irrelevantes sus otros subárboles.

De hecho, si un algoritmo se cayó del nodo${\displaystyle x_{l}}$a${\displaystyle x_{m}}$a través de un camino pero retrocede en su camino de regreso, entonces podría haber ido directamente desde${\displaystyle x_{l}}$a${\displaystyle x_{m}}$en cambio. De hecho, el salto hacia atrás indica que los nodos entre${\displaystyle x_{l}}$y${\displaystyle x_{m}}$son irrelevantes para el subárbol enraizado en${\displaystyle x_{m}}$En otras palabras, un backjump indica que la visita a una región del árbol de búsqueda fue un error. Por lo tanto, esta parte del árbol de búsqueda puede ignorarse al considerar un posible backjump desde${\displaystyle x_{l}}$o de uno de sus antepasados.

Este hecho puede aprovecharse recopilando, en cada nodo, un conjunto de variables previamente asignadas cuya evaluación basta para demostrar que no existe solución en el subárbol con raíz en dicho nodo. Este conjunto se construye durante la ejecución del algoritmo. Al retroceder desde un nodo, se elimina la variable de este conjunto y se agrega al conjunto del destino del retroceso o salto hacia atrás. Dado que los nodos que se omiten en el salto hacia atrás nunca se retrocede, sus conjuntos se ignoran automáticamente.

• Retroceder
• Aprendizaje con restricciones
• Aprendizaje de cláusulas basado en conflictos
• Anticipación (retroceso)
• GRASP (solucionador SAT)