Backjumping

En algoritmes de backtracking, el backjumping és una tècnica que reduïx espai de busca, i per tant, aumenta l'eficàcia d'esta. Mentres que el backtracking sempre remonta un nivell en el diagrama d'arbre quan tots els valors per a una variable $x_1,\dots ,x_n$ han segut provats,el backjumping pot remontar més nivells. En este artícul, s'utilisa un orde fix d'evaluació de variables, pero les mateixes consideracions s'apliquen per a un orde dinàmic d'evaluació.

• Un diagrama d'arbre utilisant el backtracking.
  Un diagrama d'arbre utilisant el backtracking.
• Un bot cap a arrere: el nodo gris no ha segut visitat.
  Un bot cap a arrere: el nodo gris no ha segut visitat.

Definició

Quan el backtracking ha provat tots els valors per a una variable sense trobar solució, reconsidera l'última variable assignada prèviament, canviant el seu valor o retrocedint més si no hi ha atres valors per a ser provats. Si $x_1=a_1,\dots ,x_k=a_k$ és l'assignació parcial actual i tots els valors per a $x_{k+1}$ han segut provats sense trobar una solució, el backtracking conclou que cap solució $x_1=a_1,\dots ,x_k=a_k$ existix. L'algoritme llavors "remonta" a $x_k$, canviant el valor de $x_k$ si és possible, retrocedint una atra volta en cas contrari.

L'assignació parcial no és sempre necessària per a provar que cap valor de $x_{k+1}$ du a una solució. En particular, un prefix de l'assignació parcial pot tindre la mateixa propietat, açò és, que existix un índex $j<k$ tal que $x_1,\dots ,x_j=a_1,\dots ,a_j$ no pot ser estés per a formar una solució en qualsevol valor per a $x_{k+1}$. Si l'algoritme pot provar este fet, directament pot considerar un valor diferent per a $x_j$ en lloc de reconsiderar $x_k$ com faria normalment.

Archiu:Backjump-variables-1.svg	Archiu:Backjump-variables-2.svg	Archiu:Backjump-variables-3.svg
Un eixemple en el que l'assignació actual per a $x_1{x}_2{x}_3{x}_4$ ha segut provada erròneament en cada possible valor de $x_5$. El backtracking va cap a arrere fins a $x_4$ tractant d'assignar-li un nou valor.	En lloc de realisar el backtracking, l'algoritme fa una llectura més elaborada, provant que les evaluacions $x_1{x}_2{x}_5=211$, $x_1{x}_5=22$, i $x_1{x}_2{x}_5=213$ no són part d'una solució.	Com a resultat, l'evaluació actual de $x_1{x}_2$ no és part de cap solució, i l'algoritme pot, directament botar cap a arrere fins a $x_2$, intentant-ho en un valor diferent.

L'eficiència d'un algoritme de backjump depén de quànt és capaç de "botar cap a arrere". Idealment, l'algoritme podria botar de $x_{k+1}$ a qualsevol variable $x_j$ per a que l'assignació actual a $x_1,\dots ,x_j$ no puga ser estesa per a formar una solució en qualsevol valor de $x_{k+1}$. Si açò ocorre, es diu un bot segur (safe jump).

Establir si un bot és segur no és sempre factible, ya que els bots segurs estan definits en benefici de crear conjunts de solucions, les quals l'algoritme està intentant trobar. En pràctica, els algoritmes de backjumping utilisen l'índex més baix per a provar eficientemente si un bot és segur. Diferents algoritmes utilisen métodos diferents per a determinar si un bot és segur. Estos métodos tenen cost diferent, pero un cost més alt de trobar un bot segur major pot ser substituït per una cantitat reduïda de busca per l'eliminació de parts del diagrama d'arbre.

Backjumping en nodos de full

La condició més senzilla en la que el backjumping és possible és quan tots els valors d'una variable han segut provats sense adinsar-se en nivells inferiors. En constraint satisfaction (satisfacció de restriccions), una evaluació parcial és compatible si i només si satisfà tots les restriccions que impliquen les variables assignades. De qualsevol atre modo, serien inconsistentes. Pot donar-se el cas de que una solució parcial compatible no puga ser estesa a una solució completa compatible perque algunes variables no assignades no poden ser assignades sense violar atres restriccions.

La condició en la qual tots els valors d'una variable $x_{k+1}$ donada són inconsistentes en la solució parcial actual $x_1,\dots ,x_k=a_1,\dots ,a_k$ rep el nom de leaf dead end (atzucac). Açò passa exactament quan la variable $x_{k+1}$ és una full del diagrama d'arbre (la qual correspon a nodos, deixant-la només com a descendents en les figures d'este artícul).

L'algoritme del backjumping de Gaschnig fa un bot cap a arrere només en situacions del tipo leaf dead end. En atres paraules, treballa de manera diferent a quan cada valor possible de $x_{k+1}$ ha segut provat i resultat inconsistente sense la necessitat de ramificar sobre una atra variable.

Un bot segur pot ser trobat en una simple evaluació, per a cada valor $a_{k+1}$, el prefix més curt de $x_1,\dots ,x_k=a_1,\dots ,a_k$ inconsistente en $x_{k+1}=a_{k+1}$. En atres paraules, si $a_{k+1}$ és un valor possible per a $x_{k+1}$, l'algoritme comprova la consistència de les evaluacions següents:

$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}$

L'índex més chicotet (el més baix del llistat) para les quals les evaluacions són inconsistentes seria un bot segur si $x_{k+1}=a_{k+1}$ anara l'únic valor possible per a $x_{k+1}$. En el moment en que cada variable pot prendre més d'un valor, l'índex màxim que ix del control per a cada valor és un bot segur, i és el punt a on l'algoritme de Gaschnig bota.

En pràctica, l'algoritme pot comprovar les evaluacions de nivells superiors al mateix temps que està comprovant la consistència de $x_{k+1}=a_{k+1}$.

Vore també

• Aprenentage de restriccions

Bibliografia

• Rina Dechter (2003). Processament de restriccions, Morgan Kaufmann. ISBN 1-55860-890-7.
• Patrick Prosser(1993).Inteligència computacional 9(3).Consultat el 25 de febrer de 2017. 9(3).