Ricerca CSP

La ricerca CSP è un algoritmo di ricerca applicato a un problema di soddisfacimento dei vincoli. Un algoritmo CSP ( Constraint Satisfaction Problem ) può essere suddiviso in due fasi. In una prima fase ( inferenza ) l'algoritmo verifica la consistenza delle variabili e delle equazioni/disequazioni del problema, riducendo notevolmente il dominio delle variabili ( ottimizzazione dei vincoli ). In una seconda fase ( ricerca ) l'algoritmo CSP avvia una fase di assegnamento dei valori logico-consistenti alle variabili, al fine di ricercare la soluzione o le soluzioni del problema. Questa seconda fase è detta "ricerca CSP". La ricerca CSP è, pertanto, un semplice problema di assegnamento dei valori alle variabili e può essere effettuata in vari modalità e tecniche ( ricerca in profondità, ricerca backtracking, ecc. ). Ad esempio, nel seguente problema a tre variabili ( A, B, C ) abbiamo reso consistenti le variabili rispetto ai vincoli del problema nella fase di inferenza. Possiamo quindi procedere alla ricerca della soluzione tramite un algoritmo di ricerca CSP.

Supponiamo di voler trovare la combinazione di valori delle variabili ( A, B, C ) in grado di restituire una somma pari a 5 ( obiettivo ). Possiamo procedere all'assegnamento dei valori delle variabili, assegnando prima il valore alla variabile A, poi alla variabile B e, infine, alla variabile C. L'albero di ricerca dell'algoritmo è il seguente:

Per trovare la prima soluzione valida l'algoritmo di ricerca CSP impiega otto passi di assegnamento. È opportuno sottolineare come, nel nostro esempio, l'operazione di assegnamento si interrompe nel momento in cui una somma parziale oltrepassa l'obiettivo. Ad esempio, dopo aver assegnato il valore 2 alla variabile A e il valore 4 alla variabile 4, è del tutto inutile procedere in profondità con l'assegnamento della variabile C poiché il risultato A+B è superiore all'obiettivo. È quindi preferibile fare un passo indietro ( backtracking ) e procedere con la successiva combinazione di assegnamento delle variabili.

Backtracking. Al termine di ogni cominazione di assegnamento, l'algoritmo di ricerca CSP si limita a modificare l'ultimo valore assegnato, lasciando immutati gli altri, fino al termine del dominio della variabile. Ad esempio, dopo aver assegnato A=2, B=1 e C=1 ( primo ramo ) l'algoritmo non ripete l'operazione di assegnamento A=2 e B=1, si limita a modificare l'assegnamento della variabile C ( C=3 ). In tal modo l'operazione di ricerca CSP ( assegnamento ) impegna soltanto 4 passi anziché 6, riducendo il tempo di esecuzione dell'algoritmo di ricerca.

Ordine di assegnamento delle variabili. L'ordinamento delle variabili nella procedura di assegnamento è uno dei fattori che può incidere sull'efficienza della ricerca. In particolar modo negli algoritmi in cui è necessario trovare rapidamente una soluzione, la prima disponibile nel minore tempo possibile e non la migliore in assoluto. Ad esempio, nell'esempio precedente avremmo potuto trovare la soluzione in soli quattro passi se l'ordine di assegnamento fosse stato B⇒C⇒A anziché A⇒B⇒C.

Ordine di assegnamento dei valori. L'ordinamento dei valori nel dominio delle variabili è un altro fattore determinante della complessità e dell'efficienza della procedura di assegnamento. La disposizione dei valori nel dominio delle variabili influisce sul tempo di esecuzione dell'operazione di ricerca. Ad esempio, se la variabile A avesse un dominio { 3, 2 } anziché { 2, 3 }, seguendo l'ordine di assegnamento delle variabili A⇒B⇒C avremmo potuto trovare la soluzione in soli tre passi di assegnamento.

Funzione euristica. Non è sempre possibile conoscere a priori l'ordine di assegnamento migliore da seguire sia per quanto riguarda l'ordine delle variabili che per quanto riguarda l'ordine dei valori di una variabile. La distribuzione dei valori tra le variabili e nel dominio delle variabili influisce nell'efficienza della ricerca. È consigliabile verificare sempre l'eventuale esistenza di inferenze, logiche ed euristiche in grado di migliorare razionalmente l'efficienza del processo di assegnamento e di ricerca ( es. euristica MRV, fail-first, fail-last ).

Apprendimento dei vincoli ( algoritmo nogood ). Nel corso dell'elaborazione di un problema complesso è possibile che si verifichino nuove situazioni conflittuali, inizialmente non previste, nell'assegnazione dei valori a un sottoinsieme di variabili. Queste sotto-ramificazioni conflittuali ( no good ) dell'albero di ricerca potrebbero ripetersi più volte durante la ricerca CSP. La tecnica di apprendimento dei vincoli consente all'algoritmo di riconoscere la combinazione di valori "no good" ed evitare di elaborarla nuovamente, migliorando l'efficienza dell'algoritmo ricerca e riducendone i tempi di esecuzione.