Backjumping
Mientras que el backtracking siempre remonta un nivel en el diagrama de árbol cuando todos los valores para una variable
La asignación parcial no es siempre necesaria para probar que ningún valor de
En particular, un prefijo de la asignación parcial puede tener la misma propiedad, esto es, que existe un índice
no pueda ser extendida para formar una solución con cualquier valor de
Si esto ocurre, se llama un salto seguro (safe jump).
Establecer si un salto es seguro no es siempre factible, ya que los saltos seguros están definidos en aras de crear conjuntos de soluciones, las cuales el algoritmo está intentando encontrar.
En práctica, los algoritmos de backjumping utilizan el índice más bajo para probar eficientemente si un salto es seguro.
La condición más sencilla en la que el backjumping es posible es cuando todos los valores de una variable han sido probados sin adentrarse en niveles inferiores.
recibe el nombre de leaf dead end (callejón sin salida).
ha sido probado y resultado inconsistente sin la necesidad de ramificar sobre otra variable.
Un salto seguro puede ser encontrado con una simple evaluación, para cada valor
, el algoritmo comprueba la consistencia de las evaluaciones siguientes: El índice más pequeño (el más bajo del listado) para las cuales las evaluaciones son inconsistentes sería un salto seguro si
En el momento en que cada variable puede tomar más de un valor, el índice máximo que sale del control para cada valor es un salto seguro, y es el punto donde el algoritmo de Gaschnig salta.
El algoritmo anterior sólo salta hacia atrás cuando los valores de una variable pueden aparecer inconsistentes con la solución parcial actual sin bifurcaciones más lejanas.
En otras palabras, permite hacer un backjump sólo en nodos del diagrama de árbol.
para no ser parte de una solución con la evaluación parcial actual
En particular, el algoritmo "sabe" que ninguna solución existe desde este punto porque vuelve a este nodo en lugar de parar después de haber encontrado una solución.
Este regreso se debe a un número de callejones sin salida, puntos donde el algoritmo ha probado una solución parcialmente inconsistente.
Con el fin de hacer un salto hacia atrás más lejano, el algoritmo tiene que tener en cuenta que la imposibilidad de encontrar las soluciones se debe a estos callejones sin salida.
En particular, los saltos seguros son índices de prefijos que todavía hacen estos callejones sin salida para ser soluciones parciales inconsistentes.
han sido probados, el algoritmo puede saltar hacia atrás hasta una variable
Esta parte del diagrama, por tanto, puede ser ignorado cuando se considere un posible backjump de
Este hecho puede ser explotado coleccionando, en cada nodo, un conjunto de variables previamente asignadas cuya evaluación es suficiente para probar que no existe una solución en el subnivel con raíz en el nodo.
Este conjunto está construido durante la ejecución del algoritmo.
han sido probados, este conjunto contiene los índices de las variables cuyas evaluaciones prueban que ninguna solución puede ser encontrada visitando el subnivel asociado en
Como resultado, el algoritmo puede saltar hacia atrás al índice más alto del conjunto.
El hecho de que los nodos saltados por backjumping puedan ser ignorados cuando se considere un salto hacia atrás más lejano puede ser explotado por el algoritmo siguiente.
Puesto que los conjuntos de variables son sólo enviados cuando retroceden de nodos, los conjuntos recolectados en los nodos saltados por backjumping son automáticamente ignorados.
Mientras la restricción violada escogida en cada hoja no afecte a la satisfacción del salto resultante, la elección de las limitaciones de los índices más altos posibles aumenta la altura del salto.
En otras palabras, excluyendo variables comunes, las restricciones más bajas tienen preferencia.
