Propagazione dei vincoli
La propagazione dei vincoli è una tecnica di ottimizzazione del processo di ricerca CSP ( Constraint Satisfaction Problem ) che consente di ridurre l'esplorazione dell'albero di ricerca ai soli nodi consistenti ( consistenza dei nodi ). Un algoritmo CSP analizza un problema prendendo in considerazione le variabili e i relativi domini. Ogni variabile può assumere soltanto i valori compresi nel proprio range di variazione ( dominio ). Questi valori sono detti valori legali. La combinazione dei valori legali delle variabili costituisce l'insieme di ricerca dell'algoritmo CSP. Può, tuttavia, capitare che alcune combinazioni siano impossibili da raggiunger, pur rispettando ogni variabile il proprio dominio. In un problema CSP il dominio effettivo di una variabile dipende anche dal valore assunto dalle altre variabili. Ad esempio, date tre variabili X1, X2 e X3 e i relativi domini, il seguente algoritmo CSP ricerca le combinazioni che consentano di produrre una somma pari a tre.
L'algoritmo può analizzare tutte le 33 (27) combinazioni possibili e selezionare quelle che producono una somma X1+X2+X3 pari a 3. Ciò implica 27 cicli di elaborazione durante l'esecuzione dell'algoritmo L'algoritmo analizza anche le combinazioni incosistenti, ossia quelle che comunque non consentono di raggiungere l'obiettivo. Ad esempio, se alla variabile X1 viene assegnato il valore 2 è inutile analizzare la combinazione di X1 con la variabile X2 poiché quest'ultima ha un range di variazione da 2 a 4. Qualsiasi somma avrebbe un valore superiore a tre. La propagazione dei vincoli analizza la consistenza locale dei singoli nodi legali e li elimina dal grafo dei vincoli quando sono inconsistenti. Analizziamo le possibili assegnazioni di valore { 0, 1, 2 } della variabile X1 in relazione all'obiettivo finale dell'algoritmo.
- Assegnazione X1 al valore 0. Quando la variabile X1 è assegnata al valore 0, il dominio della variabile X2 si riduce a { 2, 3 } e quello della variabile X3 è immutato { 1, 2, 3 }.
- Assegnazione X1 al valore 1. Quando la variabile X1 è assegnata al valore 1, il dominio della variabile X2 si riduce a { 2 } e quello della variabile X3 a { 2 }.
- Assegnazione X1 al valore 2. Quando la variabile X1 è assegnata al valore 2, il dominio della variabile X2 è un insieme vuoto { } e quello della variabile X3 è pari a { 1 }.
La propagazione dei vincoli consente di ridurre notevolmente lo spazio di ricerca. Dopo l'analisi di propagazione dei vincoli le combinazioni di valore ( problema di assegnazione ) è ridotto a sole 9 combinazioni possibili rispetto alle 27 combinazioni iniziali.
L'analisi della propagazione dei vincoli può essere.
- Propagazione dei vincoli dinamica. La propagazione dei vincoli dinamica viene effettuata durante l'esecuzione dell'algoritmo di ricerca. Durante l'esplorazione dell'albero di ricerca l'algoritmo interrompe la ricerca quando si trova dinnanzi a un nodo inconsistente, evitando così di analizzare anche le sue sotto-ramificazioni ( taglio di ricerca ).
- Propagazione dei vincoli preliminare. La propagazione dei vincoli preliminare viene effettuata prima dell'esecuzione dell'algoritmo di ricerca, al fine di ridurre l'albero di ricerca ai soli nodi consistenti. Questa operazione preliminare consente di restringere il numero dei nodi su cui effettuare il processo ricerca in seconda istanza. Spesso, l'operazione preliminare della propagazioni dei vincoli è talmente restrittiva da giungere direttamente all'obiettivo cercato, rendendo così del tutto inutile l'esecuzione del processo di ricerca vero e proprio.
