Backjumping

È una variante del backtracking

Permette di ridurre la ricerca da fare


Backtracking

L'algoritmo di backtracking, concettualmente:


Backtracking con assegnamento parziale

In pratica, viene mantenuta una assegnazione parziale dei valori delle variabili

Si inizia con nessuna variabile assegnata


Rappresentazione ad albero

È un modo per rappresentare la computazione effettuata

Si definisce a partire dalla definizione ricorsiva dell'algoritmo

Negli archi si mettono le assegnazioni di valori a variabili


Rappresentazione ad albero

Negli archi ci sono gli assegnamenti x=v

Notare la scelta di y da una parte e z dall'altra

Ogni nodo rappresenta una chiamata ricorsiva

Gli archi hanno gli assegnamenti x=v che vengono fatti subito prima di effettuare una chiamata ricorsiva


La X nel disegno

La X nel disegno corrisponde a punti dove l'assegnamento parziale viola qualche vincolo

In questi casi, si ritorna indietro

Violare un vincolo significa:

  1. tutte le variabili del vincolo hanno un valore nell'assegnamento parziale
  2. questi valori non soddisfano un vincolo

Esempi di vincoli violati

Assegnamento x=1, y=0

Vincoli: x<y, x>y, x<z

Quali di questi vincoli sono soddisfatti o violati dall'assegnamento?


Soluzione

Assegnamento x=1, y=0


Albero completo

Ci si ferma quando si arriva ad un assegnamento che soddisfa tutti i vincoli

L'albero viene visitato tutto quando non si trova un tale assegnamento (il problema non ha soluzioni) oppure si cercano tutte le soluzioni

Negli esempi che vediamo, si considerano sottoalberi in cui una soluzione non c'è


Backjumping

Cosa succede se scelgo una variabile che potevo evitare?

Esempio:

ma si poteva fare
(rimane tutto uguale
a parte il nodo evitato):

Nel secondo albero, non devo guardare T3


Cosa si risparmia?

Le parti di albero già visitate ormai le ho attraversate

Se però riesco a non visitare altre parti, risparmio tempo

Come mi accorgo degli errori?


Requisiti

Più "sbagli" trovo, più sottoalberi riesco a non visitare

Ma...

Non posso "fare le prove" (provare a togliere un nodo intermedio e vedere se rimane tutto uguale)

La verifica la devo fare durante la visita, non dopo


Requisiti

    ⇒  

In questo esempio y=b lo scelgo comunque

Però poi "salto" la scelta di w

Passo direttamente a scegliere valori per z

Requisito: i sottoalberi T1 e T2 restano uguali anche se manca w=d nell'assegnamento parziale


Cosa potrebbe cambiare?

Le foglie dei sottoalberi sono punti dove si trova inconsistenza

Togliendo w=d qualche foglia potrebbe non essere più inconsistente

    ⇒  

Questo richederebbe aggiungere figli al nodo che non è più inconsistente

In questo caso, non si può "saltare" w=d perchè richederebbe modificare quello che c'è sotto


Perchè il nome "backjumping"?

Si visita un sottoalbero

Sulla base di questo, si può decidere di "saltare" un nodo nel tornare indietro

    ⇒  

Nella chiamata ricorsiva che corrisponde al nodo più in basso, vale y=b,w=d

Quando si torna su, ci si comporta come se ci fosse invece soltanto y=b

In effetti, non è questo il valore usato nella invocazione ricorsiva che corrisponde al nodo in basso
(che sarebbe w=d, dopo aver scelto y=b)

La scelta di w=d è stata virtualmente eliminata

Nota: se possibile, si possono anche saltare più nodi


Backjumping nelle foglie

Caso più semplice: un nodo in cui tutte le valutazioni nei figli sono inconsistenti

Nei nodi X, c'è inconsistenza della valutazione parziale

Dopo aver provato che z=3 è inconsistente con w=2, si dovrebbe provare nuovo valore per w, in questo caso w=3

L'inconsistenza dei tre valori di z potrebbe valere anche senza il valore di w

O anche senza il valore di y, ecc

In altre parole, i valori di ...,x,z senza y e w potrebbero bastare per le tre inconsistenze

In questo caso, è inutile tentare altri valori per w ed y

Il valore x=1 lo scrivo perchè è "come se" all'andata si fosse scelto solo x=1 e poi i valori per z


Inconsistenza delle foglie

Concettualmente:

Il primo punto dove non c'è più inconsistenza è dove si deve saltare


Backjumping alle foglie, in pratica

L'algoritmo di sopra richiede una serie di verifiche di consistenza

... x=1 y=1 w=2 z=1
... x=1 y=1 w=2 z=2
... x=1 y=1 w=2 z=3
... x=1 y=1 z=1
... x=1 y=1 z=2
... x=1 y=1 z=3
... x=1 z=1
... x=1 z=2
... x=1 z=3

Ci si ferma appena si trova un assegnamento parziale consistente

Riordinamento: si ordinano queste righe per valori di z:

... x=1 y=1 w=2 z=1
... x=1 y=1 z=1
... x=1 z=1
... x=1 y=1 w=2 z=2
... x=1 y=1 z=2
... x=1 z=2
... x=1 y=1 w=2 z=3
... x=1 y=1 z=3
... x=1 z=3

Sono gli stessi assegnamenti parziali, ma ordinati in modo diverso

Vantaggio: posso fare le verifiche quando mi trovo nelle singole foglie


Verifiche nelle foglie

Per esempio, quando sono nella foglia z=1 posso verificare la consistenza di:

... x=1 y=1 w=2 z=1
... x=1 y=1 z=1
... x=1 z=1

Verifiche simili nelle foglie z=2 e z=3


Combinazione

Cerco la più "corta" valutazione parziale che è inconsistene con tutte le valuazioni di z

Considero la più corta che va bene con z=1, poi la più corta che va bene con z=2 e con z=3

Di questo devo prendere la più lunga

Infatti, questa risulta inconsistente con tutti i valori di z


Algoritmo risultante

Nei nodi foglia, dove c'è inconsistenza:

Per risalire:


Nodi non foglia

Rispetto al caso generale:

L'algoritmo visto prima funziona solo quando T2 contiene solo foglie (punti dove si prova subito l'inconsistenza)

L'albero T1 potrebbe però venire saltato comunque

Requisiti: eliminando tutti i valori scelti nel percorso P, tutti le foglie (punti di inconsistenza) di T2 rimangono inconsistenti

La valutazione nell'arco che entra in T1 non va esclusa, mentre quella dell'arco che esce sí


Problema della verifica

Elimiando il percorso P, tutti i nodi di inconsistenza di T2 rimangono tali

Facendo il percorso P+Q oppure J+Q, si deve mantenere l'inconsistenza alla foglia

Lo stesso per P+R rispetto a J+R, e per tutti gli altri nodi di inconsistenza di T2


Come effettuare la verifica

In ogni nodo di inconsistenza, memorizzo un insieme di variabili che effettivamente implicano l'inconsistenza

I genitori dei nodi di inconsistenza uniscono questi insiemi

In generale, ogni nodo unisce gli insiemi dei figli

In questo modo, ogni nodo ha l'unione degli insiemi memorizzati nelle foglie discendenti da esso


Esempio

In questo albero, sono stati omessi i valori ma mostrati insiemi di variabili i cui valori violano almeno un vincolo nelle tre foglie:

I tre nodi di inconsistenza memorizzano questi tre insiemi:

I primi due vengono uniti nel nodo M

Il risultato dell'unione viene unito con il terzo nel nodo N

Nel nodo N, l'unione produce p,x,y,u,w,z

Togliendo le variabili scelte sotto N, ossia w e z, resta p,x,y,u

Dato che u è la variabile più in basso che mantiene le inconsistenze, si può tornare direttamente al nodo sopra u


Variante

Quando unisco degli insiemi in un nodo, posso eliminare tutte le variabili assegnate sotto il nodo

Infatti, cerco un punto a cui saltare al di sopra del nodo

Quindi, le variabili al di sotto non mi interessano


Nodo qualsiasi

Nota:

Ogni nodo costruisce un insieme di variabili che mantengono tutte le inconsistenze al di sotto del nodo

Questo insieme permette di vedere il salto più alto possibile in ogni nodo


Definizione formale

Ogni nodo determina un insieme di variabili che bastano per garantire l'inconsistenza in tutte le foglie che sono sue discendenti

Algoritmo: nelle foglie, determino un insieme di variabili che dimostrano l'inconsistenza

Questi insiemi vengono poi "trasmessi" dalla foglia al genitore

In generale, ogni nodo riceve da ogni figlio un insieme di variabili (che servono per l'inconsistenza del figlio) e ne trasmette uno a sua volta

In ogni nodo:


Uso

In ogni nodo, so quali variabili servono per tutte le inconsistenze nel suo sottoalbero

Posso tornare indietro alla variabile necessaria più in basso


Eliminazione della variabile scelta nodo

Dopo aver unito gli insiemi dei figli, elimino la variabile del nodo

Perchè?


Eliminazione della variabile scelta nel nodo

In ogni nodo, mi interessano solo le variabili necessarie al di sopra di esso

Quelle al di sotto no, perchè non le devo saltare

Equivale ad eliminare tutte le variabili scelte nel nodo o sotto

Infatti, ogni nodo elimina la sua, il suo genitore elimina la sua, ecc.


Algoritmo

Riassumendo, l'algoritmo è come il backtracking, ma:

Il terzo punto è dovuto al fatto che le variabili in mezzo non servono per le inconsistenze del sottoalbero che ha il nodo come radice


Doppio salto

Cosa succede se durante la visita del sottoalbero ho già fatto un salto?

Esempio: ho finito con il nodo c, e ho il suo insieme di variabili

Faccio questo salto e mi trovo nel nodo a

Ora voglio sapere dove saltare da a

Uso l'algoritmo di prima

Dato che ad a si arriva direttamente da c, ricevo l'insieme inviato da c

Non quello inviato da b

È un problema?


I nodi saltati non esistono

Il backjumping consiste nel saltare nodi che si sarebbe potuto non analizzare del tutto

I nodi della parte ombreggiata si possono ignorare

È come se c fosse il figlio di a

Quindi, se c manda l'insieme dei suoi nodi ad a, va tutto bene


Scelta degli insiemi delle foglie

Sono in una foglia

Dalla valutazione parziale posso eliminare x oppure z

In entrambi i casi l'inconsistenza rimane

Quale insieme mando al genitore? Quello senza x o quello senza z?

Sono entrambe scelte corrette, perchè basta che venga inviato un insieme che permette di mantenere l'inconsistenza


Insiemi inconsistenti minimi

Inconsistenza=esiste un vincolo violato

Lo scope di un vincolo violato in una foglia è un insieme che garantisce l'inconsistenza nella foglia

(Non è detto che sia minimo: un altro vincolo violato potrebbe avere un sottoinsieme come scope)

Scelta: in ogni foglia, si sceglie lo scope di un vincolo violato


Scelta del vincolo

Fra i vari vincoli violati, quale scelgo?

Voglio i salti più alti possibile


Un sistema differente

Risulta meno buono

È per far vedere che ci sono diverse strategie di backjumping

È basato sul grafo primale


Backjumping basato sul grafo primale

Rivediamo i requisiti:

Rimpiazzando P con J, le inconsistenze in fondo a Q, R, ecc. non cambiano

Se le variabili valutate in Q, R, ecc. non stanno in nessun vincolo con le variabili di P, allora P si può saltare


Algoritmo

In ogni nodo, foglia o nodo interno, seleziono tutte le variabili sopra al nodo e che stanno in un vincolo con la variabile valutata nel nodo

Ogni nodo invia questo insieme al genitore

Il genitore unisce questi insiemi e li invia al suo genitore

Le variabili al di sotto del nodo si possono eliminare

In pratica, basta eliminare la variabile valutata nel nodo