Lezione 7 Constraint satisfaction problems Flashcards
Qual’è il concetto della local search?
Nella local search noi non cerchiamo un path ad uno stato finale, la soluzione è composta solamente dallo stato finale. Per questo cercheremo di cominciare la nostra ricerca da stati che sappiamo essere promettenti a priori e, navigando attraverso lo state space attorno ad essi, cercheremo di trovare la soluzione, con il principio che essa dovrebbe essere vicina.
In cosa consiste l’hill climb search?
L’hill climb search è un algoritmo di ricerca locale, e consiste nello scegliere ad ogni iterazione uno stato adiacente a quello di partenza che sia migliore secondo la sua euristica. Si ferma solo quando ogni stato adiacente è peggiore. Questo algoritmo presenta il limite di potersi impantanare il massimi locali o altopiani ma è possibile trovare soluzioni a questi problemi.
Come si definisce un problema di constraint satisfaction?
Un problema di constraint satisfacion è definito da una serie di variabili a cui dobbiamo assegnare un valore, ognuna di esse con il suo dominio, ovvero la lista di valori assegnabili. Abbiamo inoltre una lista di costrizioni che dobbiamo rispettare quando andiamo ad assegnare i valori. La soluzione in questo tipo di problemi è la combinazione delle variabili con dei valori in modo che ogni costrizione venga rispettata.
Cos’è il diagramma delle costrizioni nel contesto della risoluzione di constraint satisfaction problems?
E’ la rappresentazione grafica delle relazioni di costrizione tra le variabili del problema. I nodi sono le variabili e gli archi le costrizioni. Per questo corso useremo unicamente costrizioni binarie.
Come funziona il forward checking nella risoluzione di constraint satisfaction problems?
Il forward checking consiste nel controllare, ogni volta che si assegna un valore ad una variabile, i constraint associati ad essa ed eventualmente togliere dal dominio delle variabili vicine ad essa i valori che li infrangerebbero. (per fare questo è utile il grafo)
Qual’è il concetto di arc consistency nel contesto della risoluzione di constraint satisfaction problems?
Una variabile si dice arc consistent se ogni valore nel suo dominio è assegnabile senza infrangere alcun constraint.
Come funziona l’algoritmo di AC-3?
L’arc consistency 3 consiste nell’effettuare controlli di forward checking ad ogni passagio della nostra assegnazione di variabili, in modo da garantire l’arc consistency ad ogni variabile. Inoltre, nel caso in cui alcune scelte dovessero essere obbligate, cancella in anticipo i valori che interferirebbero con esse in passaggi futuri.
Qual’è il concetto di constraint propagation nel contesto della risoluzione di constraint satisfacion problems?
Il concetto è che durante la nostra assegnazione di valori alle variabili possiamo effettuare dell’inferenza per accorgerci in anticipo di combinazioni che infrangerebbero i nostri constraint.
Quando può essere utile usare la ricerca nel contesto della risoluzione di constraint satisfaction problems?
Anche con i nostri algoritmi di constraint propagation ci possiamo trovare nella situazione di avere più scelte di valori assegnabili, e possiamo trattare il nostro problema di constraint satisfaction come un problema di ricerca, cercando la soluzione provando ad assegnare valori alle variabili con vari metodi.
Come funziona l’algoritmo di backtracking search nel contesto della risoluzione di constraint satisfaction problems?
Iniziamo effettuando una singola assegnazione di valore, effettuiamo constraint propagation e poi proviamo ad assegnare un valore alla volta in maniera simile al depth first search, quindi seguendo un’assegnazione fino alla fine. Ad ogni passaggio effettuiamo constraint propagation e continuiamo fino a quando non possiamo più assegnare valori, e continuiamo la ricerca tronando indietro sempre come depth first.
Quali accorgimenti si possono adottare per migliorare il backtracking search?
Si può scegliere ad ogni passaggio di provare ad assegnare il valore prima alle variabili con meno valori rimasti nel dominio (minimum-remaining-values), oppure a parità di questo dare sempre precedenza alle variaibli legate da più constraint (degree heuristic), oppure di nuovo possiamo, una volta selezionata la variabile, provare prima i valori che sappiamo andranno ad impattare meno constraint (least-constraining-value). Inoltre possiamo applicare metodi di constraint propagation più efficaci tipo AC 3.
In che modo può essere utile applicare la ricerca locale durante la risoluzione di problemi di constraint propagation?
Possiamo trasformare un problema di constraint satisfaction in uno di ricerca locale prendendo come variabile da ottimizzare il numero di constraint infranti, partendo da un’assegnazione casuale di tutte le variabili e cercando di cambiarne una alla volta in modo da diminuire il numero di constraint infranti. (min-conflicts). Inoltre possiamo dare un peso diverso ai vari constraint per cercare di risolvere prima quelli più problematici.
