È una variante del backtracking
Permette di ridurre la ricerca da fare
L'algoritmo di backtracking, concettualmente:
In pratica, viene mantenuta una assegnazione parziale dei valori delle variabili
Si inizia con nessuna variabile assegnata
È 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
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 corrisponde a punti dove l'assegnamento parziale viola qualche vincolo
In questi casi, si ritorna indietro
Violare un vincolo significa:
Assegnamento x=1, y=0
Vincoli: x<y, x>y, x<z
Quali di questi vincoli sono soddisfatti o violati dall'assegnamento?
Assegnamento x=1, y=0
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'è
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
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?
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
⇒ |
In questo esempio y=b lo scelgo comunque
Però poi "salto" la scelta di w
Passo direttamente a scegliere valori per zRequisito: i sottoalberi T1 e T2 restano uguali anche se manca w=d nell'assegnamento parziale
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
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
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
Concettualmente:
Il primo punto dove non c'è più inconsistenza è dove si deve saltare
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
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
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
Nei nodi foglia, dove c'è inconsistenza:
Per risalire:
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í
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
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
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
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
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
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:
In ogni nodo, so quali variabili servono per tutte le inconsistenze nel suo sottoalbero
Posso tornare indietro alla variabile necessaria più in basso
Dopo aver unito gli insiemi dei figli, elimino la variabile del nodo
Perchè?
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.
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
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?
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
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
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
Fra i vari vincoli violati, quale scelgo?
Voglio i salti più alti possibile
Risulta meno buono
È per far vedere che ci sono diverse strategie di 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
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