Consistenza di cammino
La consistenza di cammino ( path consistency ) è una tecnica di consistenza locale per ottimizzare una rete, analizzando il cammino tra due nodi con un nodo intermedio. Ad esempio, dati tre nodi A, B e C, si analizza la consistenza di cammino tra i nodi A e C, considerando i relativi vincoli con il nodo intermedio B. Il dominio della variabile A è { 0, 1 ), quello della variabile B è { 1 } e, infine, quello della variabile C è { 0, 1, 2 }. Non esiste alcun vincolo diretto tra A e C. Tuttavia, esistono due vincoli binari ( archi ) di non uguaglianza tra i nodi A e B e tra i nodi B e C.
Per analizzare la consistenza di cammino A-C è necessario analizzare le combinazioni possibili di assegnamento tra il nodo A e il nodo C, tenendo conto dei vincoli binari dei due nodi con il nodo B.
Come si può notare, alcune combinazioni non sono cammino-consistenti ( combinazioni in rosso ). Ad esempio, quando uno dei due nodi è uguale a 1, non è possibile soddisfare il vincolo binario di non uguaglianza con B. È quindi possibile eliminare i valori non consistenti di cammino dal dominio delle variabili A e C, al fine di concentrare l'elaborazione successiva soltanto sulle combinazioni cammino-consistenti.
Al termine dell'analisi preliminare di consistenza di cammino il dominio della variabile ( nodo ) A si riduce da { 0, 1 } a { 0 } e quello della variabile ( nodo ) C da { 0, 1, 2 } a { 0, 2 }. In conclusione, la consistenza di cammino consente di ottimizzare un problema CSP tramite la propagazione dei vincoli, riducendo il dominio delle variabili ( nodi ) lungo un cammino, prima ancora di avviare l'elaborazione dell'algoritmo CSP.
Assenza cammino-consistenza. Quando un problema non è cammino-consistente, ciò equivale a dire che non è esiste nessun assegnamento cammino-consistente delle variabili ( insieme vuoto ) e il problema CSP non ha soluzione. In tale caso è inutile avviare l'elaborazione dell'algoritmo CSP, l'analisi preliminare di consistenza di cammino ha già appurato che il problema non ha soluzione.
K-consistenza. Nell'esempio precedente si è considerato un cammino composto da tre nodi. In questo caso, la consistenza locale è detta k-consistente con k=3. È possibile ampliare l'analisi di consistenza del cammino su più di tre nodi ( k>3 ). Quanto maggiore è il parametro di k-consistenza, tanto migliore è l'ottimizzazione del problema CSP. 
Va comunque considerato che l'incremento della k-consistenza implica anche un incremento della complessità spaziale e temporale dell'analisi di consistenza. In alcuni casi la complessità potrebbe essere talmente alta ( esponenziale ) da rendere impossibile o sconsigliabile l'analisi di consistenza del cammino. 
Per ridurre la complessità della consistenza di cammino si può ricorrere alla tecnica della ricerca con inferenza in avanti, in cui i vincoli del problema sono verificati, durante la ricerca stessa, soltanto sulle singole ramificazioni del nodo corrente.
