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 ${displaystyle 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.

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 ${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}}$ han sido probados sin encontrar una solución, el backtracking concluye en que ninguna solución ${displaystyle x_{1}=a_{1},ldots ,x_{k}=a_{k}}$ existe. El algoritmo entonces "remonta" a ${displaystyle x_{k}}$, cambiando el valor de ${displaystyle 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 ${displaystyle 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 ${displaystyle j<k}$ tal que ${displaystyle x_{1},ldots ,x_{j}=a_{1},ldots ,a_{j}}$ no puede ser extendido para formar una solución con cualquier valor para ${displaystyle x_{k+1}}$. Si el algoritmo puede probar este hecho, directamente puede considerar un valor diferente para ${displaystyle x_{j}}$ en vez de reconsiderar ${displaystyle x_{k}}$ como haría normalmente.

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 ${displaystyle x_{k+1}}$ a cualquier variable ${displaystyle x_{j}}$ para que la asignación actual a ${displaystyle x_{1},ldots ,x_{j}}$ no pueda ser extendida para formar una solución con cualquier valor de ${displaystyle 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.

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 ${displaystyle x_{k+1}}$ dada son inconsistentes con la solución parcial actual ${displaystyle 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 ${displaystyle 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 ${displaystyle 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 ${displaystyle a_{k+1}}$, el prefijo más corto de ${displaystyle x_{1},ldots ,x_{k}=a_{1},ldots ,a_{k}}$ inconsistente 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 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 ${displaystyle x_{k+1}=a_{k+1}}$ fuese el único valor posible para ${displaystyle 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 ${displaystyle x_{k+1}=a_{k+1}}$.

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 ${displaystyle 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 ${displaystyle x_{k+1}=a_{k+1}}$ para no ser parte de una solución con la evaluación parcial actual ${displaystyle 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 otras palabras, cuando todos los valores de ${displaystyle x_{k+1}}$ han sido probados, el algoritmo puede saltar hacia atrás hasta una variable ${displaystyle x_{k+1}}$ siempre y cuando la evaluación de 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 de la hoja que es descendientes del nodo ${displaystyle x_{k+1}}$.

Debido al número potencialmente alto de nodos que hay en el subnivel de ${displaystyle x_{k+1}}$, la información desde la que es necesaria hacer el salto seguro de ${displaystyle 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 ${displaystyle x_{l}}$ que han sido evitados por un salto hacia atrás pueden ser ignorados mientras se busca un salto hacia atrás para ${displaystyle x_{l}}$. Más precisamente, todos los nodos evitados por un backjump desde un nodo ${displaystyle x_{m}}$ hasta otro nodo ${displaystyle x_{l}}$ son irrelevantes al subnivel asociado en ${displaystyle x_{m}}$, y también irrelevante es su otro subniveles.

De hecho, si un algoritmo desciende desde un nodo ${displaystyle x_{l}}$ hasta ${displaystyle x_{m}}$ hacia una trayectoria pero salta hacia atrás en el camino de origen, entonces puede haber ido directamente desde ${displaystyle x_{l}}$ a ${displaystyle x_{m}}$. De hecho, el backjump indica que los nodos entre ${displaystyle x_{l}}$ y ${displaystyle x_{m}}$ son irrelevantes al subnivel asociado en ${displaystyle 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 ${displaystyle x_{l}}$ o de uno de sus niveles superiores.

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.

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 ${displaystyle x_{1},ldots ,x_{k}}$ están en restricción con las variables ${displaystyle x_{k+1},x_{k+2},...}$ que están instanciadas en nodos de hoja. Para cada nodo de hoja y cada variable ${displaystyle x_{i}}$ de índice ${displaystyle i>k}$ que esté instanciado allí, los índices menores que o iguales a ${displaystyle k}$ cuyas variables están en restricción con ${displaystyle x_{i}}$ pueden encontrar saltos seguros. En particular, cuando todos los valores para ${displaystyle 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 ${displaystyle 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.

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 ${displaystyle C}$ prevalece sobre otra ${displaystyle D}$ si el índice más alto de una variable en ${displaystyle C}$ pero no en ${displaystyle D}$ es más bajo que el índice más alto de una variable en ${displaystyle D}$ pero no en ${displaystyle 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 ${displaystyle i}$ ya que ${displaystyle 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 ${displaystyle k+1}$. De este modo, cuando el algoritmo vuelve a la variable ${displaystyle 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 ${displaystyle 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.

---