En los algoritmos de retroceso , el salto hacia atrás es una técnica que reduce el espacio de búsqueda , lo que aumenta la eficiencia. Si bien el retroceso siempre sube un nivel en el árbol de búsqueda cuando se han probado todos los valores de una variable, el salto hacia atrás puede subir más niveles. En este artículo, se utiliza un orden fijo de evaluación de las variables, pero se aplican las mismas consideraciones a un orden dinámico de evaluación.
Siempre que el retroceso haya probado todos los valores de una variable sin encontrar ninguna solución, reconsiderará la última de las variables asignadas previamente, cambiando su valor o retrocediendo nuevamente si no se deben probar otros valores. Si es la asignación parcial actual y se han probado todos los valores de sin encontrar una solución, el retroceso concluye que no existe ninguna solución que se extienda. Luego, el algoritmo "sube" a , cambiando el valor de si es posible, retrocediendo nuevamente en caso contrario.
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 se puede extender para formar una solución con cualquier valor para . Si el algoritmo puede demostrar este hecho, puede considerar directamente un valor diferente para en lugar de reconsiderarlo como lo haría normalmente.
La eficiencia de un algoritmo de salto hacia atrás depende de qué tan alto es capaz de saltar hacia atrás. Idealmente, el algoritmo podría saltar de a cualquier variable que sea tal que la asignación actual a no pueda extenderse para formar una solución con cualquier valor de . Si este es el caso, se denomina salto seguro .
No siempre es posible determinar si un salto es seguro, ya que los saltos seguros se definen en términos del conjunto de soluciones, que es lo que el algoritmo intenta encontrar. En la práctica, los algoritmos de salto hacia atrás utilizan el índice más bajo que pueden demostrar de manera eficiente que es un salto seguro. Diferentes algoritmos utilizan diferentes métodos para determinar si un salto es seguro. Estos métodos tienen diferentes costos, pero un costo más alto de encontrar un salto seguro más alto puede compensarse con una cantidad reducida de búsqueda debido a que se saltan partes del árbol de búsqueda.
La condición más simple en la que es posible realizar un salto hacia atrás es cuando se ha demostrado que todos los valores de una variable son inconsistentes sin necesidad de realizar más ramificaciones. En el caso de 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. Podría 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 pueden no 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 de hoja . Esto sucede exactamente cuando la variable 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 salto hacia atrás de John Gaschnig realiza un salto hacia atrás solo en los puntos muertos de las hojas. En otras palabras, funciona de manera diferente al retroceso solo cuando se han probado todos los valores posibles de y han resultado inconsistentes sin necesidad de ramificar sobre otra variable.
Se puede encontrar un salto seguro simplemente evaluando, para cada valor , el prefijo más corto de incompatible con . En otras palabras, si es un valor posible para , el algoritmo verifica 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 fuera el único valor posible para . Dado que cada variable normalmente puede tomar más de un valor, el índice máximo que surge de la comprobación para cada valor es un salto seguro y es el punto donde salta el algoritmo de John Gaschnig.
En la práctica, el algoritmo puede comprobar las evaluaciones anteriores al mismo tiempo que comprueba la consistencia de .
El algoritmo anterior solo realiza un salto hacia atrás cuando se puede demostrar que los valores de una variable son inconsistentes con la solución parcial actual sin necesidad de realizar más ramificaciones. En otras palabras, permite un salto hacia atrás solo en los nodos de hoja del árbol de búsqueda.
Un nodo interno del árbol de búsqueda representa una asignación de una variable que es 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 los nodos internos como en los nodos hoja. De hecho, si se realizan algunas evaluaciones de ramificación requeridas, es 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 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 particular, el algoritmo "sabe" que no existe ninguna solución a partir de este punto porque vuelve a este nodo en lugar de detenerse después de haber encontrado una solución.
Este retorno se debe a una serie de callejones sin salida, puntos en los que el algoritmo ha demostrado que una solución parcial es inconsistente. Para poder realizar más saltos hacia atrá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 hacen que estos callejones sin salida sigan siendo soluciones parciales inconsistentes.
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 .
Debido a la cantidad potencialmente alta de nodos que se encuentran en el subárbol de , la información necesaria para realizar un salto hacia atrás de forma segura 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.
La segunda simplificación es que los nodos en el subárbol de que se han saltado mediante un salto hacia atrás se pueden ignorar mientras se busca un salto hacia atrás para . Más precisamente, todos los nodos saltados 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.
De hecho, si un algoritmo descendió del nodo a a través de una ruta pero retrocedió en su camino, entonces podría haber retrocedido directamente de a en su lugar. De hecho, 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 había sido un error. Por lo tanto, esta parte del árbol de búsqueda se puede ignorar al considerar un posible retroceso desde o desde uno de sus ancestros.
Este hecho puede aprovecharse recopilando, en cada nodo, un conjunto de variables previamente asignadas cuya evaluación sea suficiente para demostrar que no existe solución en el subárbol con raíz en el nodo. Este conjunto se construye durante la ejecución del algoritmo. Al retroceder desde un nodo, a este conjunto se le quita la variable del nodo y se lo recopila en el conjunto del destino del backtracking o del backjumping. Dado que los nodos que se saltan del backjumping nunca se retroceden, sus conjuntos se ignoran automáticamente.
La razón de ser de los saltos hacia atrás basados en grafos es que se puede encontrar un salto seguro comprobando cuáles de las variables están en una restricción con las variables que están instanciadas en los nodos hoja. Para cada nodo hoja y cada variable de índice que está instanciada allí, los índices menores o iguales a cuya variable está en una restricción con se pueden usar para encontrar saltos seguros. En particular, cuando se han probado todos los valores para , este conjunto contiene los índices de las variables cuyas evaluaciones permiten demostrar que no se puede encontrar una solución visitando el subárbol con raíz en . Como resultado, el algoritmo puede realizar un salto hacia atrás al índice más alto de este conjunto.
El hecho de que los nodos saltados por el salto hacia atrás se puedan ignorar al considerar un salto hacia atrás adicional se puede explotar con el siguiente algoritmo. Al retroceder desde un nodo hoja, se crea el conjunto de variables que están en restricción con él y se "envía de vuelta" a su padre, o ancestro en caso de salto hacia atrás. En cada nodo interno, se mantiene un conjunto de variables. Cada vez que se recibe un conjunto de variables de uno de sus hijos o descendientes, sus variables se agregan al conjunto mantenido. Al retroceder o retroceder más desde el nodo, la variable del nodo se elimina de este conjunto y el conjunto se envía al nodo que es el destino del retroceso o salto hacia atrás. Este algoritmo funciona porque el conjunto mantenido en un nodo recopila todas las variables que son relevantes para demostrar la insatisfacción en las hojas que son descendientes de este nodo. Dado que los conjuntos de variables solo se envían cuando se retrocede desde los nodos, los conjuntos recopilados en los nodos saltados por el salto hacia atrás se ignoran automáticamente.
Un algoritmo de salto hacia atrás aún más refinado, que a veces puede lograr saltos hacia atrás más grandes, se basa en verificar no solo la presencia común de dos variables en la misma restricción, sino también si la restricción realmente causó la inconsistencia. En particular, este algoritmo recopila una de las restricciones violadas en cada hoja. En cada nodo, el índice más alto de una variable que se encuentra en una de las restricciones recopiladas en las hojas es un salto seguro.
Si bien la restricción violada elegida en cada hoja no afecta la seguridad del salto resultante, la elección de restricciones de los índices más altos posibles aumenta la altura del salto. Por esta razón, el salto hacia atrás basado en conflictos ordena las restricciones de tal manera que las restricciones sobre variables de índices más bajos sean preferidas sobre las restricciones sobre variables de índices más altos.
Formalmente, una restricción es preferible a otra si el índice más alto de una variable en pero no en es menor que el índice más alto de una variable en pero no en . En otras palabras, excluyendo las variables comunes, se prefiere la restricción que tiene todos los índices más bajos.
En un nodo hoja, el algoritmo elige el índice más bajo que sea incoherente con la última variable evaluada en la hoja. Entre las restricciones que se violan en esta evaluación, elige la más preferida y recopila todos sus índices menores que . De esta manera, cuando el algoritmo vuelve a la variable , el índice recopilado más bajo identifica un salto seguro.
En la práctica, este algoritmo se simplifica al reunir todos los índices en un único conjunto, en lugar de crear un conjunto para cada valor de . En particular, el algoritmo reúne, en cada nodo, todos los conjuntos procedentes de sus descendientes que no se han saltado mediante el salto hacia atrás. Al retroceder desde este nodo, se elimina la variable del nodo de este conjunto y se reúne en el destino del retroceso o salto hacia atrás.
El salto hacia atrás dirigido por conflictos fue propuesto para los problemas de satisfacción de restricciones por Patrick Prosser en su artículo fundamental de 1993.
