Constraint Satisfaction Problem

La Constraint Satisfaction Problem è un problema ( problem ) che può essere risolto tramite la simultanea soddisfazione ( satisfaction ) di due o più vincoli ( constraint ). Le tecniche Constraint Satisfaction Problem sono conosciute anche come tecniche di risoluzione CSP o modelli CSP. In italiano sono definiti come problemi a soddisfacimento di vincoli. Dal punto di vista matematico un problema CSP è composto da un insieme di variabili X ( X1, X2, ... Xn ) e da un insieme di vincoli C sotto forma di equazioni, disequazioni, matrici. Ogni vincolo può ridurre il valore di ogni singola variabile entro un determinato range di variazione. Il risultato finale di un modello CSP non consiste, pertanto, in una soluzione ottimale bensì in un sottoinsieme cartesiano dei valori che le variabili X possono assumere contemporaneamente.

MODELLO CSP - CONSTRAINT SATISFACTIN PROBLEM

La logica delle tecniche Constraint Satisfaction Problem individua N combinazioni di valori ( vettori ) delle variabili X. Ciò consente di ridurre la scelta finale ( decisione ) ad un sottoinsieme di scelte più piccolo rispetto a quello di partenza. La scelta della decisione finale dell'agente razionale viene comunque effettuata mediante criteri diversi dalla tecnica Constraint Satisfaction Problem che si limita soltanto a selezionare le scelte possibili. Il procedimento di risoluzione di un problema CSP è suddiviso in due fasi:

  • Ottimizzazione dei vincoli. Nella fase di ottimizzazione l'algoritmo verifica la consistenza dei vincoli del problema, analizzando la consistenza locale, la consistenza degli archi e del cammino, al fine di ridurre il dominio delle variabili entro i valori consistenti, eliminando tutti gli altri. Ciò consente di ridurre notevolmente lo spazio di ricerca della soluzione del problema.
  • Ricerca CSP. Nella fase di ricerca CSP l'algoritmo effettua le operazioni di assegnamento dei valori alle variabili del problema, al fine di individuare le combinazioni in grado di fornire una soluzione al problema. La fase di ricerca CSP è un semplice problema di assegnamento.

Un modello CSP si trasforma anche in un modello decisionale soltanto nel caso in cui il sottoinsieme individuato contiene un solo vettore ( N = 1 ) ossia una sola combinazione di valori delle variabili X. La tecnica Constraint Satisfaction Problem è alla base dei sistemi esperti, del problem solving e dell'intelligenza artificiale.

Ricerca con inferenza in avanti. La fase di ottimizzazione dei vincoli ( inferenza ) può anche essere integrata direttamente nella fase di ricerca CSP, evitando così di elaborarla come fase preliminare prima delle ricerca csp. In tali casi, l'algoritmo elabora l'ottimizzazione dei vincoli del problema soltanto sui valori correnti ( nodi ) delle variabili, durante l'operazione di assegnamento dei valori alle variabili, al fine di eliminare i valori non consistenti dal dominio dei nodi-figli. Ciò consente di ridurre la potenza di calcolo al singolo caso contingente ( nodo corrente ), evitando di dover elaborare l'elaborazione preliminare su tutti i vincoli del problema nell'albero di ricerca, ottenendo comunque la potatura logica delle sotto-ramificazioni non consistenti. La ricerca con inferenza in avanti è particolarmente utile per elaborare la consistenza di cammino ( k-consistenza ) in profondità, laddove l'algoritmo debba ricercare la prima soluzione utile a un problema ( non tutte le soluzioni ) nel minore tempo possibile.

https://www.okpedia.it/constraint_satisfaction_problem


Segnala un errore o invia un suggerimento per migliorare la pagina


Constraint Satisfaction Problem


FacebookTwitterLinkedinLinkedin