Ricerca backjumping
La ricerca backjumping è una tecnica di ricerca CSP. Nel momento in cui l'algoritmo fallisce un tentativo di ricerca, non torna alla variabile immediatamente precedente ( backtracking ) bensì all'ultima variabile conflittuale. Le variabili di un problema CSP possono essere legate tra loro da vincoli binari o meno. Ad esempio, nel seguente problema a cinque variabili ( A, B, C, D, E ) è necessario rispettare dei vincoli binari di diseguaglianza. Il valore della variabile A deve essere diverso da quello della variabile B, quello della variabile B deve essere diverso dalla variabile C, ecc. La variabile D ( nodo ) è, invece, indipendente da tutte le altre. Il dominio di ciascuna variabile è composto da tre valori { 1, 2, 3 }. Il grafo dei vincoli è rappresentato nel seguente modo:
Per risolvere il problema l'algoritmo deve procedere alle operazioni di assegnazione dei valori alle variabili, fin quando non trova la combinazione di valori in grado di rispettare tutti i vincoli binari del problema. Ipotizziamo di aver seguito un processo di assegnazione sequenziale che ci conduce alla seguente situazione:
Non è possibile procedere a nessuna assegnazione alla variabile E poiché ogni valore del dominio { 1, 2, 3 } viola un vincolo nei confronti delle variabili A, B, C. Il processo di assegnazione è fallito. Un algoritmo di ricerca backtracking farebbe un salto indietro all'ultima variabile assegnata ( D ) per provare a cambiare il suo valore. Tuttavia, si tratta di un'operazione inutile poiché il valore della variabile D non influisce sui vincoli delle altre variabili ( A, B, C, E ). Ad esempio, possiamo assegnare alla variabile D il valore 2 o 3 ma, in ogni caso, l'assegnazione alla variabile E violerebbe un vincolo del problema. Dopo aver constatato il fallimento delle assegnazioni della variabile D, l'algoritmo sarebbe costretto a un ulteriore backtracking alla variabile C. Utilizzando la ricerca backtracking l'algoritmo effettua 17 tentativi e 2 backtracking prima di giungere a una soluzione.
L'algoritmo di ricerca backjumping si basa, invece, su una tecnica di ricerca più efficiente rispetto al backtracking. Quando l'algoritmo constata il fallimento di assegnazione della variabile E, evita di analizzare le diverse combinazioni della variabile D, facendo direttamente un "salto all'indietro" fino all'ultima variabile conflittuale ( variabile C ). In questo caso l'algoritmo effettua circa 8 tentativi(1) e un solo backjumping dalla variabile E alla variabile C. L'albero di ricerca è il seguente.
L'algoritmo di ricerca backjumping non ha modificato l'assegnazione di valore dell'ultima variabile cronologica ( D ), passando direttamente ad analizzare le possibili varianti di assegnazione dell'ultima variabile conflittuale ( C ). In conclusione, il backjumping è una sorta di backtracking strategico o backtracking intelligente.
Ordine di assegnazione dei valori.L'algoritmo backjumping potrebbe impiegare qualche operazione di assegnazione in più rispetto agli otto tentativi indicati nell'esempio precedente. Tutto dipende dal criterio dell'ordine di assegnazione del valori alla variabile C e alla variabile E. Ad esempio, seguendo un criterio progressivo di assegnazione dei valori, l'algoritmo backjumping impiegherebbe 10 tentativi anziché 8. In ogni caso, il numero dei tentativi è inferiore ai 17 tentativi effettuati dall'algoritmo backtracking. Per semplificare l'esposizione nell'esempio precedente è rappresentato il migliore ordine di assegnazione possibile dei valori.
