k-consistenza

La k-consistenza è una tecnica di consistenza locale per ottimizzare un problema tramite la propagazione dei vincoli lungo un cammino di nodi. Dati k nodi, l'analisi di k-consistenza verifica se l'assegnamento dei valori alle variabili ( nodi ) soddisfa i vincoli del cammino. L'analisi di k-consistenza consente di eliminare dal problema tutti quei nodi e quei cammini che non risultano k-consistenti. È un'analisi preliminare rispetto all'esecuzione vera e propria dell'algoritmo In base al parametro k è possibile individuare le seguenti tipologie di k-consistenza.

• Consistenza di nodo ( 1-consistenza ). La k-consistenza con k=1 è l'analisi di consistenza di nodo. Sono verificati i vincoli unari relativi a ogni singolo nodo ( variabile ).
• Consistenza di arco ( 2-consistenza ). La k-consistenza con con k=2 è l'analisi di consistenza di arco. Sono verificati i vincoli binari tra un nodo ( variabile ). e gli altri nodi collegati ( variabili ).
• Consistenza di cammino ( k-consistenza ). La k-consistenza con con k>2 è l'analisi di consistenza di cammino. Sono verificati i vincoli lungo un cammino da un nodo di partenza ( variabile ) a un nodo destinazione.

Spazio e tempo di ricerca dell'algoritmo. Dopo un'analisi di k-consistenza, l'algoritmo CSP elabora soltanto gli assegnamenti k-consistenti, riducendo sia lo spazio di ricerca che il tempo di esecuzione della ricerca.

Assenza cammini k-consistenti. In assenza di cammini k-consistenti, è inutile eseguire l'algoritmo CSP poiché il problema non ha soluzioni. L'operazione preliminare di k-consistenza ha già appurato che l'insieme delle combinazioni k-consistenti è un insieme vuoto.

Complessità. L'analisi di k-consistenza implica un incremento della complessità temporale e spaziale. In particolar modo, quando l'analisi del cammino è su più di tre nodi ( k>3 ), l'aumento esponenziale della complessità spaziale potrebbe rendere impraticabile questa tecnica di ottimizzazione. Per ridurre la complessità della k-consistenza si può utilizzare la ricerca con inferenza in avanti. In una ricerca con inferenza in avanti i vincoli del problema sono verificati durante la ricerca stessa, soltanto sulle singole sotto-ramificazioni del nodo corrente.