Lezione 4 Risoluzione tramite ricerca Flashcards
Quali sono i passaggi che compie un agente per affrontare un problema di ricerca?
Goal formulation: Identificare la condizione di risoluzione del problema,
Problem formulation: formalizzare il problema individuando tutti gli stati possibili e tutte le azioni,
Search: la fase in cui l’agente esplora possibili soluzioni e alla fine della quale trova una soluzione oppure capisce che il problema è irrisolvibile,
Execution: esegue la soluzione e risolve il problema.
Nel contesto della modellizzazione di un problema di ricerca, cos’è lo state space?
Il set di tutti i possibili stati in cui si può trovare il nostro problema.
Nel contesto della modellizzazione di un problema di ricerca, cos’è l’initial state?
Lo stato in cui ci troviamo ad inizio esecuzione.
Nel contesto della modellizzazione di un problema di ricerca, cosa sono i Goal states? Quale funzione è correlata con questi?
Si dicono goal states tutti gli stati che rispettano le condizioni che deve possedere lo stato che stiamo cercando. Correlato a questo set di stati esiste la funzione Is-Goal(s) che ci permette di capire se uno stato è finale.
Nel contesto della modellizzazione di un problema di ricerca, cosa sono le actions? Quale funzione è correlata con queste?
Actions sono le azioni che l’agente può compiere durante la ricerca per modificare lo stato. Usiamo la funzione Actions(s) per ottenere il set di azioni che possono essere svolte a partire dallo stato s.
Nel contesto della modellizzazione di un problema di ricerca, cos’è il transition model? Quale funzione è correlata con questo?
E’ il modello che rappresenta cosa succede agli stati quando viene compiuta su di essi un’azione. Per sfruttarlo usiamo la funzione Result(s,a) che ci restituisce lo stato s’ risultato dell’azione a compiuta a partire da s.
Nel contesto della modellizzazione di un problema di ricerca, cos’è l’Action Cost Function?
E’ la funzione che calcola il costo associato a compiere un’azione a partire da uno stato per raggiungerne un’altro Action-Cost(s,a,s’).
Qual’è la definizione di ‘solution’ nel contesto dei problemi di ricerca?
Possiamo dire di aver trovato la soluzione ad un problema di ricerca quando abbiamo trovato una sequenza di azioni che ci porta dallo stato iniziale ad uno finale. Per un problema possono esistere più soluzioni e tramite le funzioni di costo si può individuare quella ottimale.
Cos’è il search tree? In cosa si differenzia dal grafo dello state space?
Il search tree è un albero che solitamente viene generato durante l’esecuzione di un algoritmo di ricerca, e che serve ad esso per tenere traccia degli stati visitati e delle azioni compiute. E’ un sottoalbero del grafo dello state space e si differenzia soprattutto perchè, quando è possibile trovare una soluzione, è finito.
In generale, in che modo si crea un albero di ricerca?
L’albero di ricerca a inizio esecuzione è formato solo dalla radice, lo stato iniziale, ad ogni iterazione l’agente usa la funzione Actions per ottenere le azioni disponibili, e tramite Results scopre quali sono i prossimi stati che può raggiungere. Ne sceglie uno, espande l’albero e ricomincia il ciclo.
Quali sono le caratteristiche del Best-First search? Quali sono le politiche di Evaluation che applica?
Il best first search consiste, ad ogni iterazione di ricerca, nello scegliere sempre l’azione con costo minore.
Quali tipi di liste possiamo utilizzare per rappresentare la frontiera?
Possiamo usare una priority queue, ovvero una lista che viene ordinata secondo una evaluation function in modo da restituire sempre lo stato desiderato, oppure una FIFO o LIFO.
Che tipi di approccio possiamo prendere nei confronti della ridondanza degli stati durante la ricerca?
Esiste il graph-search, in cui cerchiamo di tenere conto degli stati ridondanti attraverso varie politiche, aumentando quindi il costo computazionale. Esiste anche il tree-like search, in cui non ci preoccupiamo della ridondanza e quindi rischiamo di cadere in dei loop.
Quali sono i criteri che dobbiamo tenere in considerazione quando scegliamo un algoritmo di ricerca?
Completezza: ovvero se l’algoritmo ci garantisce una soluzione se questa esiste. Ottimizzazione del costo: ovvero se l’algoritmo ci offre la soluzione ottimale dal punto di vista del costo. Complessità spaziale e temporale: le risorse fisiche necessarie all’esecuzione e il tempo che questa richiede.
