Definizione
Caratteristiche
- Variabili
- Dominio per ogni variabile
- Costraints per ogni variabile
Queste tre sono elementi che definiscono un problema di soddisfazione delle restrizioni, una soluzione è un assegnamento di variabili che soddisfi ogni restrizioone e sia all’interno del dominio
Consistenza
Vogliamo andare a limitare il dominio valutando le consistenze possibili
Consistenza del punto
Si può dire che un punto sia consistente se le sue variabili possibili non viola nessuna restrizione unaria: eg. se ho N e ho la restrizione n ≥ 0, allora avere tutto N è inconsistente nel punto.
Consistenza ad arco
Questo tratta delle restrizioni binarie: una coppia di punti si dice che è arco consistente se per ogni variabile nel primo dominio esiste sempre una variabile nel secondo dominio che mi soddisfa la restrizione.
k-consistenze
Si può estendere il concetto della consistenza per avere un numero arbitrario di nodi, questo dovrebbe causa però un costo del calcolo molto maggiore.
AC-3 algorithm
Questo è un algoritmo per forzare la consistenza ad arco, praticamente va di forza bruta a imporre la consistenza su un arco, se i domini vengono aggiornati gli archi vicini vengono rimessi in coda, in modo da essere sicuri che restino ancora consistenti (infatti eliminando certe variabili potrebbero aver perso di consistenza)
La ricerca di una soluzione
Backtracking
Euristiche della scelta dei valori
Minimum remaining Values
vorremmo che la ricerca della variabile non assegnata fallisca il prima possibile, quindi scegliamo la variabile con più vincoli, o meno valori assegnabili.
Least constraining value
Se vogliamo una unica soluzione che soddisfa vogliamo scegliere variabili che hanno meno probabilità di fallire.
Forward check
Abbastanza simile ad AC-3, toglie dei valori che non possono esserci??? boh cose simili.