Ricerca Non Informata Flashcards
Cos’è un algoritmo di ricerca
Un algoritmo di ricerca riceve in input un problema di ricerca e restituisce una soluzione o un’indicazione di fallimento
Questi algoritmi sovrappongono un albero di ricerca al grafo dello spazio degli stati:
-un nodo corrisponde ad uno stato
-i rami corrispondono alle azioni
-la radice è lo stato iniziale
Lo spazio degli stati descrive l’insieme degli stati del mondo e le azioni. L’albero descrive i cammini tra questi stati.
Gli algoritmi di ricerca aiutano nella scelta di QUALI nodi figli bisogna considerare
Algoritmo di ricerca best-first
Ad ogni nodo del nostro albero attribuiamo una funzione di valutazione f(n), che corrisponderà a 0 nel nostro stato iniziale.
L’algoritmo espanderà il nodo che avrà la funzione di valutazione minore e restituirà il valore se è uno stato obiettivo, altrimenti continuerà l’espansione scegliendo sempre f(n) minore
Caratteristiche di un nodo
Un nodo è rappresentato da:
-n.stato: stato del nodo
-n.padre: nodo che lo ha generato
-n.azione: l’azione applicata allo stato del padre per generare il nodo corrente
-n.COSTO-CAMMINO: costo totale del cammino che va dallo stato iniziale al nodo corrente
Cos’è la frontiera e come viene gestita
Nodi di frontiera: Nodi raggiunti ma non espansi
La struttura dati per la frontiera è una coda che può avere più tipi di gestione:
-A priorità (Ricerca best first)
-FIFO (Ricerca in Ampiezza)
-LIFO (Ricerca in Profondità)
Quali sono gli indici di prestazione di un algoritmo di ricerca
Completezza: deve essere in grado di esplorare ogni stato che sia raggiungibile a partire dallo stato iniziale e quindi trovare sempre una soluzione (se esiste)
Ottimalità rispetto al costo: soluzione a costo minimo
Complessità temporale: tempo impegato per la soluzione
Complessotà Spaziale: memoria necessaria per operare
Cos’è un algoritmo di ricerca non informata
Un algoritmo di ricerca non informata non riceve alcuna informazione su quanto uno stato sia vicino all’obiettivo
Opera in ambienti episodici, a singolo agente, completamente osservabili, deterministici, statici, discreti e noti
Ricerca in Ampiezza
Si espande prima il nodo radice, poi tutti i suoi successori, poi i successori di questi ultimi, e così via. Si tratta di una ricerca sistematica, quindi completa anche su spazi degli stati infiniti
La ricerca in ampiezza trova sempre una soluzione con un numero minimo di azioni, ciò significa che è ottimale e completa in ogni caso
Ricerca a costo uniforme
La ricerca a costo uniforme è completa e ottima rispetto al costo, perché la prima soluzione che trova avrà un costo basso almeno quanto quello di ogni altro nodo sulla frontiera.
Questa ricerca esamina sistematicamente tutti i cammini in ordine di costo crescente, quindi non entra mai in un cammino infinito
Ricerca in Profondità
La ricerca in profondità espande sempre per primo il nodo a profondità maggiore nella frontiera
La ricerca in profondità non è ottima rispetto al costo, infatti restituisce sempre la prima soluzione che trova
Per spazi degli stati finiti che sono alberi, la ricerca in profondità è efficiente e completa, mentre in spazi di stati ciclici può trovarsi bloccato all’interno di un ciclo
Variante: Ricerca a profondità limitata
Per evitare che la ricerca in profondità si perda in un cammino infinito possiamo usare la ricerca a profondità limitata, in cui forniamo un limite di profondità, l, e consideriamo tutti i nodi a profondità l come se non avessero successori
Ricerca ad approfondimento iterativo
La ricerca ad approfondimento iterativo risolve il problema di trovare un buon valore di l provando tutti i valori: prima 0, poi 1, poi 2, e così via fino a quando si trova una soluzione
La ricerca ad approfondimento iterativo è ottima per problemi in cui tutte le azioni hanno lo stesso costo, ed è completa su spazi degli stati aciclici finiti
Ricerca bidirezionale
Gli algoritmi che abbiamo trattato finora partono da uno stato iniziale e possono raggiungere ognuno dei possibili stati obiettivo. Un approccio alternativo è quello della ricerca bidirezionale, che ricerca procedendo simultaneamente in avanti a partire dallo stato iniziale e all’indietro a partire dallo stato obiettivo
