Backjumping

En algoritmos de backtracking, el backjumping es una técnica que reduce espacio de búsqueda, y por tanto, aumenta la eficacia de esta. Mientras que el backtracking siempre remonta un nivel en el diagrama de árbol cuando todos los valores para una variable $x_{1},\ldots ,x_{n}$ han sido probados,el backjumping puede remontar más niveles. En este artículo, se utiliza un orden fijo de evaluación de variables, pero las mismas consideraciones se aplican para un orden dinámico de evaluación.

Un diagrama de árbol utilizando el backtracking.
Un salto hacia atrás: el nodo gris no ha sido visitado.

Definición[editar]

Cuando el backtracking ha probado todos los valores para una variable sin encontrar solución, reconsidera la última variable asignada previamente, cambiando su valor o retrocediendo más si no hay otros valores para ser probados. Si $x_{1}=a_{1},\ldots ,x_{k}=a_{k}$ es la asignación parcial actual y todos los valores para $x_{k+1}$ han sido probados sin encontrar una solución, el backtracking concluye en que ninguna solución $x_{1}=a_{1},\ldots ,x_{k}=a_{k}$ existe. El algoritmo entonces "remonta" a $x_{k}$ , cambiando el valor de $x_{k}$ si es posible, retrocediendo otra vez en caso contrario.

La asignación parcial no es siempre necesaria para probar que ningún valor de $x_{k+1}$ lleva a una solución. En particular, un prefijo de la asignación parcial puede tener la misma propiedad, esto es, que existe un índice $j<k$ tal que $x_{1},\ldots ,x_{j}=a_{1},\ldots ,a_{j}$ no puede ser extendido para formar una solución con cualquier valor para $x_{k+1}$ . Si el algoritmo puede probar este hecho, directamente puede considerar un valor diferente para $x_{j}$ en vez de reconsiderar $x_{k}$ como haría normalmente.


Un ejemplo en el que la asignación actual para $x_{1}x_{2}x_{3}x_{4}$ ha sido probada erróneamente con cada posible valor de $x_{5}$ . El backtracking va hacia atrás hasta $x_{4}$ tratando de asignarle un nuevo valor.	En lugar de realizar el backtracking, el algoritmo hace una lectura más elaborada, probando que las evaluaciones $x_{1}x_{2}x_{5}=211$ , $x_{1}x_{5}=22$ , y $x_{1}x_{2}x_{5}=213$ no son parte de una solución.	Como resultado, la evaluación actual de $x_{1}x_{2}$ no es parte de ninguna solución, y el algoritmo puede, directamente saltar hacia atrás hasta $x_{2}$ , intentándolo con un valor diferente.

La eficiencia de un algoritmo de backjump depende de cuánto es capaz de "saltar hacia atrás". Idealmente, el algoritmo podría saltar de $x_{k+1}$ a cualquier variable $x_{j}$ para que la asignación actual a $x_{1},\ldots ,x_{j}$ no pueda ser extendida para formar una solución con cualquier valor de $x_{k+1}$ . 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. Diferentes algoritmos utilizan métodos diferentes para determinar si un salto es seguro. Estos métodos tienen coste diferente, pero un coste más alto de encontrar un salto seguro mayor puede ser sustituido por una cantidad reducida de búsqueda debido a la eliminación de partes del diagrama de árbol.

Backjumping en nodos de hoja[editar]

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. En constraint satisfaction (satisfacción de restricciones), una evaluación parcial es compatible si y sólo si satisface todos las restricciones que implican las variables asignadas. De cualquier otro modo, serían inconsistentes. Puede darse el caso de que una solución parcial compatible no pueda ser extendida a una solución completa compatible porque algunas variables no asignadas no pueden ser asignadas sin violar otras restricciones.

La condición en la cual todos los valores de una variable $x_{k+1}$ dada son inconsistentes con la solución parcial actual $x_{1},\ldots ,x_{k}=a_{1},\ldots ,a_{k}$ recibe el nombre de leaf dead end (callejón sin salida). Esto pasa exactamente cuando la variable $x_{k+1}$ es una hoja del diagrama de árbol (la cual corresponde a nodos, dejándola sólo como descendientes en las figuras de este artículo).

El algoritmo del backjumping de Gaschnig hace un salto hacia atrás sólo en situaciones del tipo leaf dead end. En otras palabras, trabaja de manera diferente a cuando cada valor posible de $x_{k+1}$ 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 $a_{k+1}$ , el prefijo más corto de $x_{1},\ldots ,x_{k}=a_{1},\ldots ,a_{k}$ inconsistente con $x_{k+1}=a_{k+1}$ . En otras palabras, si $a_{k+1}$ es un valor posible para $x_{k+1}$ , el algoritmo comprueba la consistencia de las evaluaciones siguientes:

$x_{1}=a_{1}$	...	$x_{k-1}=a_{k-1}$	$x_{k}=a_{k}$	$x_{k+1}=a_{k+1}$
$x_{1}=a_{1}$	...	$x_{k-1}=a_{k-1}$		$x_{k+1}=a_{k+1}$
...
$x_{1}=a_{1}$				$x_{k+1}=a_{k+1}$

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 $x_{k+1}=a_{k+1}$ fuese el único valor posible para $x_{k+1}$ . 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.

En práctica, el algoritmo puede comprobar las evaluaciones de niveles superiores al mismo tiempo que está comprobando la consistencia de $x_{k+1}=a_{k+1}$ .

Backjumping en nodos internos[editar]

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.

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

El backjumping en los nodos internos no pueden realizarse en los nodos de las hojas. De hecho, si algunas evaluaciones de $x_{k+1}$ requieren una bifurcación, es porque son compatibles con la asignación actual. Como resultado, buscar un prefijo que es inconsistente con estos valores de la última variable no obtiene resultado.

En tales casos, lo que resultó una evaluación $x_{k+1}=a_{k+1}$ para no ser parte de una solución con la evaluación parcial actual $x_{1},\ldots ,x_{k}$ es la búsqueda recursiva. 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.


En este ejemplo, el algoritmo vuelve hasta $x_{k+1}$ después de intentar todos sus posibles valores, debido a los tres puntos de inconsecuencia cruzados.	El segundo punto permanece inconsistente incluso si los valores de $x_{k+1}$ y $x_{k}$ son eliminados de su evaluación parcial (tenga en cuenta que los valores de una variable están en sus descendientes).	La otra evaluación inconsistente permanece así incluso sin $x_{k-2}$ , $x_{k-1}$ , y $x_{k}$ .	El algoritmo puede saltar hacia atrás hasta $x_{k-2}$ ya que se trata de la variable más baja que mantiene todas las incoherencias. Se probará con un nuevo valor de $x_{k-2}$ .

En otras palabras, cuando todos los valores de $x_{k+1}$ han sido probados, el algoritmo puede saltar hacia atrás hasta una variable $x_{k+1}$ siempre y cuando la evaluación de verdad actual de $x_{1},\ldots ,x_{i}$ es inconsistente con todas las evaluaciones de verdad de $x_{k+1},x_{k+2},...$ en los nodos de la hoja que es descendientes del nodo $x_{k+1}$ .

Simplificaciones[editar]

Mientras se busca un posible backjump para $x_{k+1}$ o uno sus niveles superiores, todos los nodos en el área sombreada pueden ser ignorados.

Debido al número potencialmente alto de nodos que hay en el subnivel de $x_{k+1}$ , la información desde la que es necesaria hacer el salto seguro de $x_{k+1}$ está recogido durante la visita de su subnivel. Encontrar un salto seguro puede ser simple por dos consideraciones. La primera es que el algoritmo necesita un salto seguro, pero también funciona sin que sea el salto seguro más alto posible.

La segunda simplificación es que los nodos en el subnivel de $x_{l}$ que han sido evitados por un salto hacia atrás pueden ser ignorados mientras se busca un salto hacia atrás para $x_{l}$ . Más precisamente, todos los nodos evitados por un backjump desde un nodo $x_{m}$ hasta otro nodo $x_{l}$ son irrelevantes al subnivel asociado en $x_{m}$ , y también irrelevante es su otro subniveles.

De hecho, si un algoritmo desciende desde un nodo $x_{l}$ hasta $x_{m}$ hacia una trayectoria pero salta hacia atrás en el camino de origen, entonces puede haber ido directamente desde $x_{l}$ a $x_{m}$ . De hecho, el backjump indica que los nodos entre $x_{l}$ y $x_{m}$ son irrelevantes al subnivel asociado en $x_{m}$ .En otras palabras, un backjump indica que la visita de una región del diagrama de árbol ha sido un error. Esta parte del diagrama, por tanto, puede ser ignorado cuando se considere un posible backjump de $x_{l}$ o de uno de sus niveles superiores.

Variables cuyos valores son suficientes para probar en el subnivel asociado que un nodo está recogido en el nodo y enviado (después de sacar la variable de este) al nodo de encima cuando está volviendo.

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. Cuando retrocede de un nodo, de este conjunto es eliminada la variable del nodo y recolectada en el conjunto de destino del backtracking o backjumping. Puesto que nunca se retrocede desde los nodos ignorados, sus conjuntos son ignoradas de forma automática.

Backjumping basado en gráficos[editar]

La razón fundamental de que el backjumping esté basado en gráficos es que un salto seguro puede ser encontrado comprobando cuáles de las variables $x_{1},\ldots ,x_{k}$ están en restricción con las variables $x_{k+1},x_{k+2},...$ que están instanciadas en nodos de hoja. Para cada nodo de hoja y cada variable $x_{i}$ de índice $i>k$ que esté instanciado allí, los índices menores que o iguales a $k$ cuyas variables están en restricción con $x_{i}$ pueden encontrar saltos seguros. En particular, cuando todos los valores para $x_{k+1}$ 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 $x_{k+1}$ . 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. Cuándo se retira de un nodo de hoja, el conjunto de variables con las que tiene una restricción está creado y "devuelto" a su padre, o nivel superior en caso de backjumping. En cada nodo interno, un conjunto de variables está mantenido. Cada vez que un conjunto de variables ha sido recibido por uno de sus descendiente, sus variables están añadidas al conjunto mantenido. Cuando el backjumping va más allá del nodo, la variable del nodo se saca de este conjunto, y el conjunto es enviado al nodo de destino del backjumping. Estos algoritmos funcionan porque el conjunto mantenido en un nodo recoge todas las variables pertinentes para probar en las hojas que son descendiente de estos nodos. 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.

Backjumping basado en el conflicto[editar]

Un algoritmo de backjumping aún más refinado, a veces capaz de conseguir saltos más grandes, está basado en no solo comprobar la presencia común de dos variables en la misma restricción sino también en si la restricción causa una incongruencia. En particular, este algoritmo recoge una de las restricciones violadas en cada hoja. En cada nodo, el índice más alto de un variable que está en uno de las restricciones recogidas en las hojas es un salto seguro.

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. Por esta razón, el backjumping basado en conflicto ordena restricciones de tal manera que las restricciones las variables de índices más bajos se prefieran sobre las restricciones sobre las variables de índice más altos.

Formalmente, una restricción $C$ prevalece sobre otra $D$ si el índice más alto de una variable en $C$ pero no en $D$ es más bajo que el índice más alto de una variable en $D$ pero no en $C$ . En otras palabras, excluyendo variables comunes, las restricciones más bajas tienen preferencia.

En un nodo de hoja, el algoritmo escoge el índice más bajo $i$ ya que $x_{1},\ldots ,x_{i}$ es inconsistente con la última variable evaluada en la hoja. Entre las restricciones que son violadas en esta evaluación, escoge la preferente, y recoge todos sus índices de menores que $k+1$ . De este modo, cuando el algoritmo vuelve a la variable $x_{k+1}$ , el índice recogido más bajo identifica un salto seguro.

En práctica, este algoritmo se simplifica recogiendo todos los índices en un conjunto, en vez de crear un conjunto para cada valor de $k$ . En particular, el algoritmo recoge en cada nodo todos los conjuntos que vienen de sus descendientes que no ha sido saltados por backjumping.

El backjumping basado por conflicto estuvo propuesto para Problemas de satisfacción de restricciones por Patrick Prosser en su periódico semanal de 1993.