Euristica variabile vincolante
L'euristica della variabile vincolante è una tecnica euristica di ottimizzazione del processo di ricerca CSP. Secondo questa euristica, in un problema di assegnamento è consigliabile ordinare le variabili in base al numero di vincoli che hanno nei confronti delle altre variabili. Le variabili con più vincoli ( variabili più vincolanti ) sono le prime ad essere elaborate e assegnate ai valori. L'euristica è conosciuta anche come degree heuristic, euristica di grado o grado euristico. Ad esempio, il seguente grafo rappresenta un sistema con tre variabili e due vincoli.
Nell'esempio precedente la variabile B ha due vincoli ( B≠A e B≠C ) mentre le variabili A e C hanno un solo vincolo, rispettivamente A≠B e C≠A. La variabile B è, quindi, la variabile più vincolante del problema. Le altre due variabili hanno, invece, un grado di vincolo inferiore. Secondo l'euristica di grado l'ordine di assegnamento delle variabili B⇒A⇒C Avendo le variabili A e C lo stesso grado di vincolo, pari a uno, è possibile scegliere anche un ordine di assegnamento B⇒C⇒A. Iniziando la procedura di assegnamento dei valori a partire dalla variabile B, quella coinvolta in un maggior numero di vincoli con le altre variabili, l'algoritmo dovrebbe ridurre la ramificazione dell'albero di ricerca ( potatura logica ). L'euristica della variabile vincolante si basa sul presupposto logico-razionale che la variabile con più vincoli è in grado, più delle altre variabili, di decretare il successo o l'insuccesso di una ricerca. È quindi legittimo elaborarla prima delle altre, al fine di ottenere una potatura logica dell'albero di ricerca.
L'euristica della variabile vincolante è meno potente rispetto ad altre euristiche e non garantisce sempre un miglioramento dell'efficienza dell'algoritmo di ricerca. Si ricorre all'euristica della variabile vincolante soprattutto in abbinamento ad altre tecniche euristiche e/o nei casi in cui non sia possibile elaborare euristiche di ricerca più potenti ( es. euristica MRV ).
