Semplificazione dei vincoli
La semplificazione dei vincoli è una tecnica di ottimizzazione dei problemi CSP che consente di ridurre un problema complesso in un problema più semplice da analizzare e da risolvere. Esistono diverse tecniche di semplificazione dei vincoli, le principali sono le seguenti:
- Insieme di taglio condizionato. Un sottoinsieme di variabili del problema viene tagliato ( isolato ) dalle altre variabili. L'algoritmo elabora i vincoli dell'insieme di taglio ( sottoproblema ) e, successivamente, sulla base delle soluzioni effettua una propagazione dei vincoli sulle variabili restanti.
- Soddisfacimento dei vincoli distribuiti. Le variabili del problema sono raggruppate in sottoinsiemi di variabili e vincoli ( sottoproblemi ), i quali continuano ad essere legati tra loro da vincoli ( sottoproblemi vincolati ). L'algoritmo risolve ogni singolo sottoproblema e, successivamente, verifica il soddisfacimento dei vincoli tra i sottoproblemi.
Nel primo caso ( insieme di taglio condizionato ) le variabili sono separate dalle altre. L'algoritmo risolve un solo sottoproblema e verifica la consistenza delle soluzioni con le altre variabili. Nel secondo ( soddisfacimento dei vincoli distribuiti ) le variabili sono raggruppate tra loro per formare dei sottoproblemi ossia dei sottoinsiemi di variabili. L'algoritmo risolve ogni singolo sottoproblema e verifica la consistenza delle soluzioni con i vincoli tra i sottoproblemi.
