Grafo di vincoli
Il grafo di vincoli è una rappresentazione grafica di un problema di soddisfacimento di vincoli ( CSP ). Il grafo di vincoli consente di analizzare più facilmente i vincoli tra le variabili di un problema, in quanto il grafo si presenta come una rappresentazione più naturale, più facile da leggere e da comprendere da parte dell'uomo. I nodi rappresentano le variabili e gli archi i vincoli tra le variabili. Un esempio di grafo di vincoli è il seguente.
Nell'esempio sono rappresentati graficamente i vincoli tra le variabili X0, X1 e X2. Le variabili sono indicate dai nodi di forma circolare. Gli archi che congiungono i nodi-variabili indicano, invece, la relazione tra queste ultime. Ad esempio, l'arco che congiunge il nodo X0 con il nodo X2 rappresenta un vincolo di uguaglianza tra le rispettive variabili ( X0 = X2 ). L'arco che congiunge il nodo X0 con il nodo X1 rappresenta un vincolo di maggioranza tra le rispettive variabili ( X0 > X1 ). Infine, l'arco che congiunge il nodo X1 con il nodo X2 rappresenta un vincolo di disuguaglianza tra le rispettive variabili ( X2 ≠ X1 ). Quando tutti vincoli sono soddisfatti, l'algoritmo CSP è giunto a una soluzione del problema.
Vincoli CSP. Nel grafo di vincoli precedente sono mostrati soltanto dei vincoli binari ossia dei vincoli in grado di unire due variabili in una relazione. Esistono diversi tipi di vincoli oltre quello binario. Ad esempio, il vincolo unario che fissa un vincolo soltanto su una variabile ( nodo ), il vincolo temporale che fissa un vincolo di precedenza o meno in una sequenza di azioni/operazioni, ecc.
