Eliminazione vincoli unari

L'eliminazione dei vincoli unari è una tecnica di ottimizzazione delle variabili e dei vincoli di un sistema CSP. Consiste nell'applicazione dei vincoli unari di una variabile ( nodo ) sul dominio della variabile. Ad esempio, una variabile X è definita in un dominio di numeri da zero a cinque { 0, ... , 5 }. L'algoritmo CSP deve eseguire 6 cicli di assegnazione, uno per ciascun valore possibile della variabile X. Supponiamo che il sistema abbia anche il seguente vincolo unario sulla variabile: X<3. Il sistema matematico può essere scritto nel seguente modo:

x = { 0, 1 , 2, 3, 5 }

x < 3

All'inizio di ogni ciclo l'algoritmo CSP verifica se il valore assegnato alla variabile è minore di 3 ed eventualmente prosegue. In tali circostanze è possibile migliorare l'efficienza dell'algoritmo integrando il vincolo unario nel dominio della variabile ( X ) in questione. A parità di efficacia ( risultato ), possiamo riscrivere il sistema matematico nel seguente modo:

x = { 0, 1, 2 }

L'integrazione del vincolo unario sul dominio della variabile ( nodo ) consente di ridurre il campo di variazione della variabile da 6 elementi a 3 elementi detti nodi consistenti. Una volta rimossi i valori non consistenti dal dominio della variabile X, è inutile riscrivere il vincolo unario su X in quanto tutti i valori della variabile ( dominio ) soddisfano le condizioni del vincolo unario. L'algoritmo CSP può elaborare 3 cicli di assegnazione anziché 6, ottenendo una migliore efficienza di esecuzione.

Efficienza dell'algoritmo. L'integrazione del vincolo unario sul dominio della variabile consente di ridurre il numero dei cicli di elaborazione dell'algoritmo La riduzione dello spazio di ricerca migliora la complessità temporale e spaziale dell'algoritmo Nell'esempio precedente l'algoritmo riduce i cicli di assegnazione da 6 a 3.

Ottimizzazione del sistema. L'integrazione del vincolo unario sul dominio della variabile consente anche di eliminare il vincolo unario stesso dalle condizioni del sistema matematico. A parità di efficacia, l'eliminazione del vincolo unario permette di ottenere la semplificazione e l'ottimizzzione del sistema matematico. Nell'esempio precedente il numero dei vincoli del sistema matematico viene dimezzato da due a uno.