Nodo consistente
Un nodo consistente è un nodo di una rete caratterizzato da consistenza locale ( consistenza di nodo ). Un nodo è consistente quando tutti i valori nel suo dominio soddisfano i vincoli unari del nodo stesso. Ad esempio, un nodo A con dominio pari a { 0, 1, 2, 3 } e un vincolo unario A<2 non può dirsi consistente poiché i valori 2 e 3 nel suo dominio non soddisfano il vincolo unario del nodo. Il nodo A è consistente soltanto quando il suo dominio è pari a { 0, 1 }. La consistenza di nodo è un aspetto molto importante per l'ottimizzazione degli algoritmi nei modelli CSP ( Constraint Satisfaction Problem ). Ad esempio, un nodo "ore" (H) con dominio pari a { 0, ..., 24 } è inconsistente quando la variabile H è sottoposta a un vincolo unario 7<H<19 come nel seguente grafo dei vincoli.
L'algoritmo CSP deve effettuare 24 processi di assegnazione della variabile H ossia 24 cicli di assegnazione. Tuttavia, soltanto 11 assegnazioni sono consistenti mentre le rimanenti 13 sono non consistenti ( inutili ). L'elaborazione dei nodi non consistenti è un evidente spreco di risorse. La verifica della consistenza di nodo consente di migliorare l'efficienza dell'algoritmo, di ridurre la complessità spaziale ( spazio di ricerca ) e la complessità temporale ( tempo di elaborazione ) dell'algoritmo La riduzione del dominio della variabile equivale a lavorare soltanto su un sottoinsieme di valori rispetto a quello iniziale.
Eliminazione dei vincoli unari. L'applicazione del vincolo unario al dominio del nodo ( variabile ) consente di eliminare il vincolo unario e semplificare il modello matematico. Una volta rimpossi i valori non consistenti dal dominio della variabile, è inutile elaborare nuovamente il vincolo unario durante l'esecuzione dell'algoritmo In altri termini, il controllo di consistenza di nodo permette di eliminare il vincolo unario dal modello.
Propagazione dei vincoli. In un modello matematico le variabili sono dipendenti dal valore di altre variabili. La riduzione del range di variazione di una variabile ( nodo ) potrebbe ridurre indirettamente anche il range di variazione dei nodi ove si presenta come variabile indipendente.
