Arco orientato di consistenza

L'arco orientato di consistenza è una tecnica di analisi della consistenza delle variabili in un problema CSP. Un problema CSP si dice arco orientato consistente con un ordinamento di variabili ( x₁, x₂, x₃, ...x_n ) se e solo se ogni x_i è arco-consistente con ogni x_j per j>i. L'arco di consistenza orientata ( Direct Arc Consistency o DAC ) permette di semplificare l'analisi di un problema trasformando i vincoli ( archi ) in archi orientati di consistenza e fissando un ordinamento di variabili. Ad esempio, per risolvere il seguente problema possiamo analizzare tutte le combinazioni possibili di valori delle variabili.

In realtà, sarebbe consigliabile modificare l'ordine di assegnazione delle variabili da (b->d->e) a (e->d->b). Sapendo che la variabile (b) è isolata ( svincolata ) dalle altre può essere analizzata per ultima. I suoi valori non influiscono sulla soluzione del problema. Il vincolo di disuguaglianza tra le variabili (d) ed (e) può essere modificato in un arco orientato ( vincolo orientato ) ponendo la variabile (e) prima della variabile (d). Essendo la variabile (e) composta da un solo valore {2}, con una sola operazione è possibile ridurre ll dominio della variabile (d) da {1,2,3 } a { 1,3 }. Ciò consente di ridurre il numero di assegnazioni da analizzare.