Apprendimento vincoli

È una variante del backtracking

Principio: prima riesco a dimostrare inconsistenza, più sottoalberi evito di visitare

Durante la visita, creo nuovi vincoli

Un esempio

Mi trovo in questa situazione
(parti dell'albero sono state omesse)

Mi accorgo che le due inconsistenze richedono soltanto i valori x1=1 e x4=2

Creo un nuovo vincolo:

• scope: variabili x1 e x4
• relazione: tutte le coppie di valori sono ammesse tranne x1=1 e x4=2

A cosa serve?

Durante il resto della ricerca, si potrebbe incontrare un nodo cosí:

In questo caso, il nuovo vincolo permette di tagliare subito la ricerca

Otterei lo stesso risultato se...

Se dopo aver scelto x4=2 scegliessi x5 come variabile da assegnare, otterrei lo stesso risultato

Però:

• non è detto che la variabile scelta sia x5
• nel caso l'inconsistenza fosse causata da x1 e x3 (invece che x4) si dovrebbe scegliere x5 quando prima si è scelto x4

Esigenze contrastanti

Ci sono due fattori contrastanti da tenere in considerazione:

• più vincoli si creano, più è facile che si trovi rapidamente una inconsistenza in seguito
• più vincoli ci sono, più tempo ci vuole per verificare la loro consistenza/inconsistenza ad ogni passo

Quindi, vanno creati vincoli solo se si ritiene che la loro utilità superi il costo di doverli verificare tutte le volte

Utilità/costo di un vincolo

I vincoli che vengono creati sono del tipo: una singola tupla di valori non è ammessa

Se un vincolo è più corto, allora:

1. è più probabile che venga violato
2. ci vuole di meno per verificarlo

La cosa importante è la 1. La 2 è del tutto secondaria

Bounded learning

Si creano solo i vincoli con un massimo numero di variabili

Esempio: se si sceglie 3, si ha il 3-bounded learning

Si memorizzano solo vincoli che hanno al più tre variabili

Relevance-bounded learning

Si scartano vincoli appresi che non sembrano più utili

In particolare, se un vincolo vieta un assegnamento che è molto diverso dall'assegnamento parziale, allora è difficile che possa servire ancora

relevance bounded learning di ordine i=si scartano i vincoli appresi il cui assegnamento vietato differisce dall'assegnamento parziale per al massimo i valutazioni

Distanza=valori assegnati ma diversi

Scelta dei vincoli da aggiungere

I sistemi di backjumping visti producono insiemi di variabili i cui valori attuali bastano a garantire l'inconsistenza

Si possono usare i vincoli associati a questi assegnamenti

Primo sistema visto: in ogni nodo ho un insieme di variabili al di sopra del nodo che bastano a garantire l'inconsistenza di tutte le foglie al di sotto

I valori attuali di queste variabili sono quindi inconsistenti con i vincoli

Si può aggiungere il vincolo che corrisponde a questo assegnamento parziale