Intelligenza artificiale/Problema di soddisfacimento di vincoli

Molti problemi nell’ambito dell'intelligenza artificiale sono classificabili come problemi di soddisfacimento di vincoli (Constraint Satisfaction Problem o CSP); fra questi citiamo problemi combinatori, di allocazione di risorse, pianificazione e ragionamento temporale. Questi problemi possono essere risolti efficientemente attraverso tecniche ben note di risoluzione di CSP.

Formalmente, un CSP può essere definito su un insieme finito di variabili $(X_{1},X_{2},\dots ,X_{n})$ i cui valori appartengono a domini finiti di definizione $(D_{1},D_{2},\dots ,D_{n})$ e su un insieme di vincoli. Un vincolo su un insieme di variabili è una restrizione dei valori che le variabili possono assumere simultaneamente. Concettualmente, un vincolo può essere visto come un insieme che contiene tutti i valori che le variabili possono assumere contemporaneamente: un vincolo tra k variabili $c(X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}})$ è un sottoinsieme del prodotto cartesiano dei domini delle variabili coinvolte $D_{i_{1}},D_{i_{2}},\dots ,D_{i_{k}}$ che specifica quali valori delle variabili sono compatibili con le altre. Questo insieme può essere rappresentato in molti modi, per esempio per mezzo di matrici, equazioni, disuguaglianze o relazioni. Una soluzione ad un CSP è un assegnamento di valori alle variabili che soddisfi tutti i vincoli.

Un classico esempio di problema che può essere visto come CSP è il rompicapo delle otto regine. Il problema consiste nel disporre su una scacchiera otto regine che non si attacchino a vicenda; naturalmente, non è possibile disporne più di otto, perché questo implicherebbe posizionarne due su una stessa riga. Per formalizzare il problema come CSP dobbiamo identificare un insieme di variabili, un insieme di domini ed un insieme di vincoli. Poiché su ogni riga e su ogni colonna della scacchiera dovrà essere posta esattamente una regina, una possibile formalizzazione del problema è quella di considerare come variabili ciascuna delle otto righe della scacchiera; l’insieme delle variabili sarà quindi $V=\{R_{1},R_{2},\dots ,R_{8}\}$ . Ciascuna di queste variabili può assumere un valore che rappresenta la colonna su cui si trova la regina corrispondente, per cui i domini delle variabili sono le otto possibili colonne: $D_{1}=D_{2}=\dots =D_{8}=\{1,2,3,4,5,6,7,8\}$ . Abbiamo quindi già inserito in questa formalizzazione il concetto che due regine non possono trovarsi sulla stessa riga; resta da imporre che due regine non possono trovarsi né sulla stessa colonna, né sulla stessa diagonale. L’insieme dei vincoli sarà dunque: