Consistenza locale

La consistenza locale è la condizione che si verifica quando ogni variabile di un sistema o nodo di una rete soddisfa sia i propri vincoli unari e/o i vincoli n-ari ( es. vincolo binario ) rispetto alle altre variabili/nodi. La consistenza locale consente di ridurre lo spazio di ricerca di un algoritmo CSP ( Constraint Satisfaction Problem ), eliminando dal grafo dei vincoli i nodi non consistenti e/o dal dominio delle variabili quei valori che non rispettano i vincoli CSP. In un modello CSP la consistenza locale può essere definita in rapporto alla consistenza di nodo, di arco o di cammino.

• Consistenza di nodo. La consistenza di nodo ( node consistency ) consiste nella verifica dei valori del dominio di una variabile ( nodo ) rispetto ai vincoli del nodo stesso. Ad esempio, se il dominio del nodo-variabile x₁ è pari a { 1, 2, 3 } e il vincolo unario del nodo-variabile x₁ è x₁>1, la consistenza di nodo consente di ridurre il dominio di x₁ a { 2, 3 } riducendo il processo di ricerca dell'algoritmo.
• Consistenza di arco. La consistenza di arco ( arc consistency ) consiste nella verifica dei valori di un dominio di una variabile ( nodo ) rispetto ai vincoli binari con un altro nodo. Ad esempio, date due nodi-variabili x₁ e x₂ con rispettivi domini { 1, 2, 3 } e { 1, 4, 5, 9 }, il vincolo x₂=x₁² consente di ridurre il dominio del nodo x₂ a { 1, 4, 9 } poiché non sussiste alcun nesso tra il valore 5 dell'insieme dominio di x₂ e qualsiasi altro elemento dell'insieme dominio di x₁.
• Consistenza di cammino. La consistenza di cammino ( path consistency ) consiste nella verifica dei valori di una variabile rispetto ai vincoli n-ari con altri n nodi. La consistenza di cammino è un'estensione della consistenza di arco ed è detta anche k-consistenza. Si distingue dalla consistenza di arco che, invece, è dedicata ai vincoli binari (k=2) tra due nodi.

Propagazione dei vincoli. La propagazione dei vincoli è una tecnica di ottimizzazione della ricerca CSP. Una volta trovati dei valori inconsistenti di nodo, di arco o di cammino, l'algoritmo riduce il dominio di una variabile ( nodo ). La propagazione dei vincoli consente di analizzare gli effetti della riduzione del dominio della variabile x₁ su tutte le altre variabili del sistema, al fine di propagare le riduzioni anche sui domini delle altre n variabili del sistema ( x₂, ... , x_n ) che hanno una relazione diretta o indiretta con x₁.