Problemi di Soddisfacimento Vincoli Flashcards
Problema con soddisfacimento di vincoli e assegnazioni
UN problema di soddisfacimento di vincoli è costituito da 3 elementi:
- X: insieme di variabili
- D: insieme di domini
- C: insieme di vincoli
Un assegnamento che non viola alcun vincolo è chiamato consistente o legale.
Un assegnamento è completo se a tutte le variabili è assegnato un valore.
Un assegnamento è parziale se alcune delle variabili rimangono non assegnate.
Varianti di CSP (Constrait Satisfaction Problem)
CSP:
* Domini Discreti/continuo
* Domini Finiti/infinito
Vincoli:
* Unari
* Binari: relazione tra due variabili
* Globale: interessa un numero arbitrario di variabili (non necessariamente tutte)
Propagazione dei vincoli
Invece di procedere direttamente con un algoritmo di ricerca, vengono effettuati dei passaggi preliminari, detti di propagazione dei vincoli, ovvero utilizziamo dei vincoli per ridurre il dominio delle variabili
Consistenza di nodo e di arco
Una singola variabile (corrispondente a un nodo nel grafo CSP) è nodo-consistente se tutti i valori del suo dominio soddisfano i suoi vincoli unari.
Diciamo che un grafo è nodo-consistente se ogni variabile del grafo è nodo-consistente.
Una variabile in un CSP si dice arco-consistente se ogni valore del suo dominio soddisfa i suoi vincoli binari
In termini più formali, Xi è arco-consistente rispetto a un’altra variabile Xj se per ogni valore nel dominio corrente Di c’è un valore nel dominio Dj che soddisfa il vincolo binario sull’arco (Xi, Xj).
Algoritmo AC-3
Consistenza di Cammino e K-consistenza
La consistenza di cammino restringe i vincoli binari utilizzando vincoli impliciti che sono inferiti considerando triplette di variabili. Un insieme di due variabili {Xi, Xj} è cammino-consistente rispetto a una terza variabile Xm se, per ogni assegnamento {Xi = a, Xj= b} consistente con i vincoli (se esistono) su {Xi, Xj}, esiste un assegnamento di Xm che soddisfa i vincoli su {Xi, Xm} e {Xm, Xj}.
Un CSP è k-consistente se, per ogni insieme di k–1 variabili e ogni loro assegnamento consistente, è sempre possibile assegnare un valore consistente a ogni k-esima variabile.
Ricerca con backtracking per CSP
Se dopo il processo di propagazione dei vincoli, ci sono ancora variabili con valori possibili, allora viene effettuata una ricerca in profondità con backtracking. L’algoritmo sceglie ripetutamente una variabile non assegnata e poi prova uno a uno tutti i valori del suo dominio, cercando di estendere ogni assegnamento a una soluzione attraverso una chiamata ricorsiva. Se la chiamata ha successo, viene restituita la soluzione, mentre se fallisce, l’assegnamento è riportato allo stato precedente e si prova il valore successivo
Come scegliere ordinamento di variabili e valori
In generale, possiamo avere diverse strategie:
* Seguire un ordine preciso
* Scegliere le variabili a caso
Nessuna delle due è efficiente.
Per questo motivo, si preferisce applicare l’euristica MRV (minimum remaining values): scegliere la variabile con il minor numero di valori possibili (euristica fail first)
Nel caso tutte le variabili hanno lo stesso numero di valor, scegliamo quella coinvolta nel maggior numero di vincoli
Il valore viene scelto quello meno vincolante.
Alternanza di ricerca e inferenza
Ogni volta che scegliamo un valore per una variabile, abbiamo una opportunità del tutto nuova di inferire nuove riduzioni dei domini delle variabili adiacenti
Verifica in avanti:
Ogni volta che una variabile X è assegnata, il processo di verifica in avanti stabilisce la consistenza d’arco per essa: per ogni variabile non assegnata Y collegata a X da un vincolo, cancella dal dominio di Y ogni valore non consistente con quello scelto per X.
