Il look-ahead

Aiuta le scelte del backtracking:


Esigenze contrastanti

Per quello che riguarda la scelta della variabile e dei valori

variabile
scegliere quella con cui inconsistenza si dimostra più velocemente
valore
scegliere quello che più probabilmente porta ad una soluzione

Scelta della variabile

Scegliere differenti variabili porta ad alberi di ricerca di differenti dimensioni

Caso estremo: esiste una variabile che dimostra la inconsistenza, ma ne scelgo un'altra

Esempio: esiste un vincolo y<x con Dy={1,2,3}

viene scelta la variabile y viene scelta un'altra variabile z
e poi altre prima di y

Se si provano subito i valori di y ci si accorge subito dell'inconsistenza

Se si scelgono altre variabili, si potrebbe visitare un albero molto grande prima di accorgersi dell'inconsistenza


Scelta della variabile

Si cerca la variabile che genera il sottoalbero più piccolo

Si usa sempre l'assunzione che non ci siano soluzioni nel sottoalbero

Anche se la soluzione c'è, il tempo dominante è la ricerca nei sottoalberi inconsistenti

Poco tempo per raggiungere la soluzione, molto per i sottoalberi inconsistenti

Se si potesse seguire la freccia, basterebbero pochi passi per trovare la soluzione

Di solito non è possibile: vengono visitati sottoalberi inconsistenti (T1, T2 e T3 nell'esempio) prima di trovare la soluzione

Il percorso con la freccia è breve (al più il numero delle variabili)
I sottoalberi possono avere grandezza esponenziale nel numero delle variabili


Numero dei valori

Il numero dei valori possibili dà una indicazione di quanto sarà grande l'albero generato da una variabile

pochi valori ammessi molti valori ammessi

Se ci sono pochi valori possibili, si hanno meno sottoalberi

Non è detto che i sottoalberi siano della stessa grandezza nel primo e nel secondo caso

Però si può presumere in assenza di altre informazioni

Meglio usare y, dato che ci sono meno sottoalberi


Analisi dei sottoalberi

Farebbe comodo poter sapere quanto saranno grandi i sottoalberi

In generale, questo richiede fare effettivamente la visita

Non ha senso (una volta visitati, il tempo è stato perso)

Caso facile: sottoalbero vuoto

pochi sottoalberi, nessuno vuoto tanti sottoalberi, ma molti vuoti

Il primo albero sembra meglio (pochi sottoalberi)

È meglio il secondo, perchè molti suoi sottoalberi sono in effetti vuoti (l'inconsistenza si rileva subito)


Scelta variabile

Si sceglie la variabile che ha il minimo numero di valori che non sono inconsistenti


Scelta variabile: principio

Si contano i sottoalberi non vuoti per ogni variabile x

Si sceglie la variabile che produce il minimo numero di sottoalberi non vuoti


Look ahead

Idea: si simulano gli effetti di aggiungere x=a alla valutazione attuale

Se si capisce in anticipo che produce una inconsistenza, è meglio

Permette di scegliere la variabile per la quale ci sono meno valori possibili


Differenza look-ahead/backtracking

Domanda: la valutazione x=a non viene fatta comunque?

Backtracking lo fa solo per la variabile scelta

Look-ahead lo fa per tutte le variabili, e lo fa per scegliere la variabile

È una simulazione di cosa farebbe backtracking se la prossima variabile assegnata fosse x, oppure y, oppure z, etc.

Serve per valutare quale di queste variabili sembra portare ad alberi di visita più piccoli


Look ahead

Per ogni variabile e ogni valore, si stimano gli effetti di scegliere il valore e la variabile

Si fa per tutte le variabili, con ogni valore possibile per ogni variabile

Nell'algoritmo precedente, si verificava solo la consistenza


Forward checking

È un meccanismo che permette di capire che x=a non fa parte di nessuna soluzione anche se nessun vincolo è violato

Per la variabile x e il valore a ∈ Dx:

Si "simula" una semplificazione che si può fare se si sceglie x=a


Scelta variabile

Per scegliere la prossima variabile:

Tutto questo va fatto tenendo anche conto delle variabili che sono già state valutate


Look-ahead: generalizzazione

Al posto di:

Si mette:

Al posto del forward checking, si può per esempio usare arc-consistency


Forward checking e arc consistency

Sono metodi che eliminano elementi dai domini

In entrambi i casi, se un dominio resta vuoto allora non ci sono soluzioni

Non sono uguali


Differenza fra forward checking e arc consistency

Caso di vincoli binari

Quando si guarda x=a

forward checking
viene fatta la verifica di arc consistency di variabili non assegnate con x
arc consistency
si guarda la arc consistency fra tutte le possibili coppie di variabili

In entrambi i casi, si usa D'x={a} al posto di Dx


Differenza, graficamente

Sia x=a la variabile che viene valutata

Forward checking:

Arc consistency:

I vincoli fra variabili già assegnate e fra variabili già assegnate e x si suppone siano stati già verificati


Full e partial look ahead

Sono meccanismi meno costosti della verifica di arc consistency ma che danno inconsistenza più spesso di forward checking


Full look ahead

Si forza la directional arc concistency una volta sola

Algoritmo: per ogni vincolo, si controlla e forza la arc consistency

Non si ripete questo passo finchè non ci sono modifiche, come fa invece arc consistency


Partial look ahead

Si verifica la consistenza di una variabile con quelle che lo seguono in un certo ordine


Scelta di valori

Una volta scelta una variabile, si devono provare tutti i valori

Si sceglie per primo il valore che ha più probabilità di portare ad una soluzione

Ci sono vari metodi

La scelta dei valori si basa sugli effetti del look ahead che si è scelto (forward checking, arc consistency, ecc.)


Min-conflicts

Si sceglie il valore per il quale il look ahead elimina meno valori complessivamente dai domini delle varaibili

In altre parole:


Max-domain-size

Dopo aver fatto look ahead, si vede quale è la dimensione del dominio più piccolo rimasto per le altre variabili

Si sceglie il valore per cui questa dimensione è maggiore possibile


Stima del numero delle soluzioni

Dopo aver fatto look ahead (che ridice i domini), si fa questo calcolo:

Si moltiplicano fra loro le dimensioni dei domini delle variabili non assegnate

Questa si può considerare una stima del numero delle soluzioni

Sarebbe uguale al numero delle soluzioni se non ci fossero altri vincoli fra le variabili


Randomizzazione

Se due variabili o valori hanno la stessa preferenza (o simile) si può scegliere a caso