Algoritmi CSP

Gli algoritmi CSP sono algoritmi di ricerca che utilizzano la struttura degli stati per trovare la soluzione a un problema. Negli algoritmi CSP il problema viene trasformato in un sistema di equazioni/disequazioni composto da variabili e vincoli di sistema. Ogni variabile è, a sua volta, delimitata da vincoli di esistenza. Lo spazio di ricerca dell'algoritmo CSP si riduce a un sottoinsieme dello spazio degli stati. Il sottoinsieme di ricerca comprende tutti gli stati in cui le variabili ( fattori ) soddisfano i relativi vincoli di esistenza e di sistema.

Ad esempio, poniamo di voler analizzare le vendite a Roma nel mese di marzo. In questo caso è inutile analizzare anche quelle del resto dell'anno o in altre città. L'algoritmo CSP associa alla variabile tempo il vincolo di esistenza "marzo" e alla variabile luogo il vincolo di esistenza "Roma". Gli algoritmi CSP prendono il nome dalla tecnica Constraint Satisfaction Problem ( CSP ) e sono utilizzati nell'ambito delle tecniche di risoluzione dei problemi di soddisfacimenti di vincoli. I principali campi di applicazione degli algoritmi CSP sono la ricerca operativa, l'economia politica e l'intelligenza artificiale.

Rappresentazione fattorizzata. Per la rappresentazione di un problema con soddisfacimento di vincoli ( CSP ) si ricorre alla rappresentazione fattorizzata. Un problema CSP non può, infatti, essere rappresentato mediante il tradizionale strumento dell'albero di ricerca poiché l'esplorazione di ricerca non è completa, bensì è limitata soltanto alle ramificazioni che soddisfano i vincoli di esistenza e i vincoli di sistema.