salto hacia atrás

En programación con restricciones y 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 utiliza un orden fijo de evaluación de variables , pero las mismas consideraciones se aplican a un orden de evaluación dinámico.${\displaystyle x_{1},\ldots ,x_{n}}$

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

Cuando el retroceso ha 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. Si es la asignación parcial actual y se han probado todos los valores para sin encontrar una solución, el retroceso concluye que no existe ninguna solución que extienda. El algoritmo entonces "sube" a , cambiando el valor de si es posible, retrocediendo de nuevo en caso contrario.${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$${\displaystyle x_{k+1}}$${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$${\displaystyle x_{k}}$${\displaystyle x_{k}}$

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

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

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

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 inconsistentes con la solución parcial actual se denomina callejón sin salida . Esto ocurre precisamente cuando la variable es una hoja del árbol de búsqueda (que corresponde a los nodos que solo tienen hojas como hijos en las figuras de este artículo).${\displaystyle x_{k+1}}$${\displaystyle x_{1},\ldots ,x_{k}=a_{1},\ldots ,a_{k}}$${\displaystyle x_{k+1}}$

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 se ha probado cada valor posible y ha resultado inconsistente sin necesidad de ramificar sobre otra variable.${\displaystyle x_{k+1}}$

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

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 fuera el único valor posible para . Dado que cada variable generalmente puede tomar más de un valor, el índice máximo que resulta de la verificación para cada valor es un salto seguro, y es el punto donde salta el algoritmo de John Gaschnig.${\displaystyle x_{k+1}=a_{k+1}}$${\displaystyle x_{k+1}}$

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.

No es posible realizar saltos hacia atrás en nodos internos como en los nodos hoja. De hecho, si se requieren algunas evaluaciones de ramificación, es porque son consistentes con la asignación actual. Por lo tanto, la búsqueda de un prefijo que sea inconsistente con estos valores de la última variable no tiene éxito.${\displaystyle x_{k+1}}$

En estos casos, lo que demuestra que una evaluación no forma parte de una solución con la evaluación parcial actual es la 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.${\displaystyle x_{k+1}=a_{k+1}}$${\displaystyle x_{1},\ldots ,x_{k}}$

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 , después de probar todos sus valores posibles, debido a los tres puntos cruzados de inconsistencia.${\displaystyle x_{k+1}}$
• 
  El segundo punto sigue siendo inconsistente incluso si los valores de y se eliminan de su evaluación parcial (nótese que los valores de una variable están en sus hijos).${\displaystyle x_{k-1}}$${\displaystyle x_{k}}$
• 
  Las demás evaluaciones inconsistentes siguen siendo así incluso sin , , y${\displaystyle x_{k-2}}$${\displaystyle x_{k-1}}$${\displaystyle x_{k}}$
• 
  El algoritmo puede retroceder ya que estas son las variables más bajas que mantienen todas las inconsistencias. Se probará un nuevo valor para .${\displaystyle x_{k-2}}$${\displaystyle x_{k-2}}$

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

Simplificaciones

Debido a la cantidad potencialmente alta de nodos que hay en el subárbol de , la información que es necesaria para retroceder de forma segura desde 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 funciona con un salto que no es el salto seguro más alto posible.${\displaystyle x_{k+1}}$${\displaystyle x_{k+1}}$

La segunda simplificación consiste en que los nodos del subárbol que se han omitido mediante un salto hacia atrás pueden ignorarse al buscar un salto hacia atrás para . Más precisamente, todos los nodos omitidos mediante un salto hacia atrás desde el nodo hasta el nodo son irrelevantes para el subárbol con raíz en , y también son irrelevantes sus otros subárboles.${\displaystyle x_{l}}$${\displaystyle x_{l}}$${\displaystyle x_{m}}$${\displaystyle x_{l}}$${\displaystyle x_{m}}$

De hecho, si un algoritmo descendiera del nodo a través de una ruta pero retrocediera en su camino, podría haber ido directamente de a en su lugar. En efecto, el retroceso indica que los nodos entre y son irrelevantes para el subárbol con raíz en . En otras palabras, un retroceso 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 retroceso desde o desde uno de sus ancestros.${\displaystyle x_{l}}$${\displaystyle x_{m}}$${\displaystyle x_{l}}$${\displaystyle x_{m}}$${\displaystyle x_{l}}$${\displaystyle x_{m}}$${\displaystyle x_{m}}$${\displaystyle x_{l}}$

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)