Aiuta le scelte del backtracking:
Per quello che riguarda la scelta della variabile e dei valori
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
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
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
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)
Si sceglie la variabile che ha il minimo numero di valori che non sono inconsistenti
Si contano i sottoalberi non vuoti per ogni variabile x
Si sceglie la variabile che produce il minimo numero di sottoalberi non vuoti
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
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
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
È 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
Per scegliere la prossima variabile:
Tutto questo va fatto tenendo anche conto delle variabili che sono già state valutate
Al posto di:
Si mette:
Al posto del forward checking, si può per esempio usare 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
Caso di vincoli binari
Quando si guarda x=a
In entrambi i casi, si usa D'x={a} al posto di Dx
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
Sono meccanismi meno costosti della verifica di arc consistency ma che danno inconsistenza più spesso di forward checking
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
Si verifica la consistenza di una variabile con quelle che lo seguono in un certo ordine
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.)
Si sceglie il valore per il quale il look ahead elimina meno valori complessivamente dai domini delle varaibili
In altre parole:
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
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
Se due variabili o valori hanno la stessa preferenza (o simile) si può scegliere a caso