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  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.

Definición

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  es la asignación parcial actual y todos los valores para  han sido probados sin encontrar una solución, el backtracking concluye en que ninguna solución  existe. El algoritmo entonces "remonta" a , cambiando el valor de  si es posible, retrocediendo otra vez en caso contrario.

La asignación parcial no es siempre necesaria para probar que ningún valor de  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  tal que  no puede ser extendido para formar una solución con cualquier valor para . Si el algoritmo puede probar este hecho, directamente puede considerar un valor diferente para  en vez de reconsiderar  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  a cualquier variable  para que la asignación actual a  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. 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 

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  dada son inconsistentes con la solución parcial actual  recibe el nombre de leaf dead end (callejón sin salida). Esto pasa exactamente cuando la variable  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  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 prefijo más corto de  inconsistente con . En otras palabras, si  es un valor posible para , 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  fuese el único valor posible para . 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 .

Backjumping en nodos internos 

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  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  para no ser parte de una solución con la evaluación parcial actual  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  han sido probados, el algoritmo puede saltar hacia atrás hasta una variable  siempre y cuando la evaluación de verdad actual de  es inconsistente con todas las evaluaciones de verdad de  en los nodos de la hoja que es descendientes del nodo .

Simplificaciones 

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

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

Backjumping basado en gráficos 

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

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  prevalece sobre otra  si el índice más alto de una variable en  pero no en  es más bajo que el índice más alto de una variable en  pero no en . 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  ya que  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 . De este modo, cuando el algoritmo vuelve a la variable , 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 . 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.

Véase también 
 Aprendizaje de restricciones

Bibliografía 
  
  9(3). 

Algoritmos de búsqueda

Enlaces externos