# Intelligenza artificiale/Problema di soddisfacimento di vincoli

Intelligenza artificiale
Copertina Tutti i moduli · Sviluppo
* DefinizioneIntelligenza artificiale/Definizione
* StoriaIntelligenza artificiale/Storia
* FilosofiaIntelligenza artificiale/Filosofia
** Test di TuringIntelligenza artificiale/Test di Turing
** Stanza cineseIntelligenza artificiale/Stanza cinese
* Rappresentazione della conoscenzaIntelligenza artificiale/Rappresentazione della conoscenza
** Linguaggi formaliIntelligenza artificiale/Linguaggi formali
** Alberi di decisioneIntelligenza artificiale/Alberi di decisione
* Apprendimento automaticoIntelligenza artificiale/Apprendimento automatico
** Apprendimento non supervisionatoIntelligenza artificiale/Apprendimento non supervisionato
*** ClusteringIntelligenza artificiale/Clustering
*** Regole di associazioneIntelligenza artificiale/Regole di associazione
** Apprendimento supervisionatoIntelligenza artificiale/Apprendimento supervisionato
*** Regole di decisioneIntelligenza artificiale/Regole di decisione
*** Sistemi espertiIntelligenza artificiale/Sistemi esperti
** Apprendimento con rinforzoIntelligenza artificiale/Apprendimento con rinforzo
*** AgenteIntelligenza artificiale/Agente
*** Reti neuraliIntelligenza artificiale/Reti neurali
*** Algoritmi geneticiIntelligenza artificiale/Algoritmi genetici
*** ClassificatoriIntelligenza artificiale/Classificatori
* Logica FuzzyIntelligenza artificiale/Fuzzy
* Problema di soddisfacimento di vincoliIntelligenza artificiale/Problema di soddisfacimento di vincoli
* ApplicazioniIntelligenza artificiale/Applicazioni
Modifica il sommario
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:
$\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.

## Algoritmi

Per risolvere problemi di soddisfacimento di vincoli, vengono usati diversi algoritmi, fra cui algoritmi che valutano i vincoli a posteriori:
* Backtracking
* Backjumping
* Backmarking
Algoritmi che valutano i vincoli a priori
* Forward Checking
* Partial Look-Ahead
* Full Look-Ahead
Algoritmi per semplificare il problema
* Arc-Consistenza
* Path-Consistenza