Problema di soddisfacimento di vincoli
Un problema di soddisfacimento di vincoli è un problema composto da un insieme di variabili { x1, ... , xn }, da un insieme di domini { d1, ... , dn } e da un insieme di vincoli/condizioni C che delimitano le combinazioni di valori ammesse per la soluzione del problema. I problemi di soddisfacimenti di vincoli possono essere espressi mediante la rappresentazione fattoriale di un sistema di equazioni e disequazioni, e risolti mediante l'ausilio della programmazione lineare. Un esempio di problema di soddisfacimento di vincoli è il seguente:
Il dominio è l'insieme dei valori che una variabile può assumere. Ad esempio, il dominio di è composto dai valori ammessi { v1, ... , vm } della variabile xi. L'insieme dei vincoli C è composto dalle condizioni, ogni condizione è una tuple di variabili che definisce in astratto una relazione nei confronti di un vincolo da soddisfare. Per comprendere meglio un problema di soddisfacimento di vincoli è opportuno evidenziare i concetti di stato e di assegnamento.
- Stato. Ogni combinazione di valori assunti dalle variabili { x1, ... xn } definisce uno stato del problema. L'insieme degli stati ( combinazioni ) definisce lo spazio degli stati del problema.
- Assegnamento. La soluzione del problema è un problema di assegnamento dei valori a tutte le variabili ( assegnamento completo ) in modo tale da soddisfare tutti i vincoli del problema ( assegnamento consistente ).
La soluzione di un problema di soddisfacimento di vincoli è un problema di assegnamento completo e consistente. Il problema di soddisfacimento di vincoli consente di delimitare lo spazio degli stati alle tuple di valori che soddisfano tutti i vincoli di esistenza e di sistema mediante un algoritmo CSP. Mentre una ricerca sequenziale semplice effettua l'esplorazione sull'intero albero di ricerca, un algoritmo CSP si concentra soltanto nel sottoinsieme di valori che rispetta i vincoli di soddisfacimento del problema.
