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 di complessità combinatorica, di allocazione di risorse, pianificazione e ragionamento temporale. Questi problemi possono essere risolti efficientemente attraverso tecniche ben note di risoluzione di CSP.

Definizione formale[modifica | modifica wikitesto]

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 (constraints) $(C_{1},C_{2},\dots ,C_{n})$ . 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. Si definisce grado della variabile il numero di vincoli a cui è sottoposta.

Un problema di soddisfacimento di vincoli presuppone un assegnamento iniziale, ovvero un insieme di variabili già vincolate. L'assegnamento iniziale può anche essere vuoto. La risoluzione del problema prosegue estendendo l'assegnamento iniziale, ovvero assegnando via via valori alle variabili ancora libere. La soluzione di un CSP è un assegnamento completo e coerente di valori alle variabili (ovvero un assegnamento che soddisfi tutti i vincoli e non lasci variabili libere), ottenuto estendendo l'assegnamento iniziale.^[1]

Esempi[modifica | modifica wikitesto]

Problema delle otto regine[modifica | modifica wikitesto]

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 $X=\{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:

$\forall i,j.R_{i}\neq R_{j}$

ad indicare che due regine non possono trovarsi sulla stessa colonna e:

$\forall i,j$ , se $R_{i}=a$ e $R_{j}=b$ , allora $i-j\neq a-b$ e $i-j\neq b-a$

per imporre che due regine non possono trovarsi sulla stessa diagonale.

Sudoku[modifica | modifica wikitesto]

Altro esempio classico è la risoluzione di un sudoku. In questo caso le variabili sono le 81 caselle della griglia, il dominio di ogni variabile sono i numeri da 1 a 9 e i vincoli sono la non ripetizione delle cifre in righe, colonne, sottogriglie. In questo caso è dato anche un assegnamento iniziale (i numeri già presenti nella griglia) che rende unica la soluzione allo schema.^[1]

Ricerca della soluzione[modifica | modifica wikitesto]

I CSP possono essere risolti con tutti i meccanismi dei problemi di ricerca della soluzione ottima. Gli algoritmi di ricerca su alberi sono favoriti dai problemi CSP, poiché infatti questi problemi danno una precisa indicazione sulla profondità massima della soluzione nell'albero di ricerca: avere $N$ variabili libere significa dover effettuare esattamente $N$ assegnamenti. In particolare, l'approccio solitamente utilizzato nella risoluzione dei CSP prevede l'impiego della ricerca in profondità^[1]: tale algoritmo infatti è ottimo e completo, poiché tutte le soluzioni si trovano alla stessa profondità (e solitamente hanno lo stesso costo) e non si corre il rischio di incorrere in cammini infiniti, la ricerca termina sempre al più al livello della soluzione. Inoltre la ricerca in profondità offre buoni compromessi sulla complessità spaziale e temporale. Grande svantaggio dei problemi CSP è il considerevole fattore di diramazione: a ogni livello dell'albero, tale fattore è infatti pari al numero di variabili non ancora assegnate moltiplicato per il numero di valori che ogni variabile può assumere. Questo problema viene risolto con il meccanismo del backtracking e considerando a ogni livello un'unica variabile e tutti i suoi possibili assegnamenti. Per stabilire quale variabile considerare, si usano determinate euristiche:

Variabile con il grado massimo, ovvero si predilige l'esame delle variabili impiegate nel numero maggiore di vincoli.
Numero minore di valori del dominio, impiegata tra le variabili selezionate dall'euristica precedente, prevede di scegliere la variabile con il dominio più ristretto.

Una volta selezionata la variabile, sono disponibili euristiche anche per la selezione del valore:

Valore meno vincolante, ovvero la selezione del valore che scarta il minor numero di valori dal dominio delle variabili correlate a quella in esame.

Inferenza[modifica | modifica wikitesto]

Ciò che maggiormente differenzia i CSP dai normali problemi di ricerca è la possibilità di fare inferenza sfruttando la propagazione dei vincoli: nel caso del sudoku, ad esempio, se a una casella è assegnato un certo numero è possibile scartare quel numero da tutte le caselle nella stessa riga, colonna e sottogriglia. Questo porta in alcuni casi a poter risolvere interi problemi senza dover ricorrere ad algoritmi di ricerca, come appunto nel caso del sudoku. Nel caso delle otto regine, invece, si predilige una strategia che intervalli ricerca a inferenza: ogni volta che ad una variabile è assegnato un valore, si scartano dai domini delle variabili ad essa correlate tutti i valori non più disponibili, in modo da preservare la coerenza ogni volta che una scelta viene effettuata.

Algoritmi di risoluzione[modifica | modifica wikitesto]

Per risolvere problemi di soddisfacimento di vincoli, sono disponibili diversi algoritmi che tengono in considerazione proprio questa peculiarità di questo tipo di problemi, divisi tra:

Algoritmi che valutano i vincoli a posteriori:
- Backtracking
- Backjumping
- Backmarking
- DLX (Dancing Links)
Algoritmi che valutano i vincoli a priori
- Forward Checking
- Partial Look-Ahead
- Full Look-Ahead
Algoritmi di inferenza
- Controllo della coerenza tra due variabili (arc-consistency);
- Controllo della coerenza, date due variabili, su una terza (path-Consistency), o più in generale:
- Controllo della coerenza, date $k-1$ variabili, su una $k-esima$ variabile (k-Consistency).

Note[modifica | modifica wikitesto]

^ ^a ^b ^c Stuart Russell and Peter Norvig, Artificial Intelligence A Modern Approach 2nd Edition, Upper Saddle River, New Jersey, Pearson Education, 2003, ISBN 0-13-080302-2.