Ricerca Informata Flashcards
Cos’è un algoritmo di ricerca informata
Un algoritmo di ricerca informata sfrutta la conoscenza specifica del dominio applicativo per fornire suggerimenti su dove si potrebbe trovare l’obiettivo
I suggerimenti hanno la forma di una funzione euristica denotata con h(n)
Ricerca Greedy
la ricerca greedy è una forma di ricerca best-first che espande prima il nodo con il valore più basso di h(n) (quindi in questo caso f(n)=h(n))
Non è un algoritmo ottimo ed è completo sono negli spazi degli stati finiti
Ricerca A*
La ricerca A* è una ricerca best-first che utilizza la funzione di valutazione f(n)=g(n)+h(n) dove g(n) è il costo del cammino iniziale al nodo n e h(n) è il costo stimato del cammino più breve da n a uno stato obiettivo
Caratteristiche della ricerca A*
Completezza
Ammissibilità = un’euristica è ammissibile se non sovrastima mai il costo per raggiungere un obiettivo
Ottimalità
Consistenza = un’euristica è consistente se per ogni nodo n e ogni nodo successivo n’ generato da un azione a, abbiamo che
h(n)<=c(n,a,n’)+h(n’)
(l’euristica di n è minore o uguale al costo del cammino da n a n’ più l’euristica di n’)
Consistenza implica ammissibilità e quindi ottimalità ma non è vero viceversa
La principale problematica della ricerca A* è legata all’impiego della memoria, suddivisa tra la frontiera e gli stati raggiunti.
Ricerca Beam
La ricerca beam limita la dimensione della frontiera, mantenendo soltanto i k nodi con i migliori costi f e scartando ogni altro nodo espanso
Iterative-Deepening A*
La ricerca A* ad approfondimento iterativo (IDA, da Iterative-Deepening A) fornisce i vantaggi della ricerca A* senza la necessità di mantenere in memoria tutti gli stati raggiunti, al costo di visitare alcuni stati più volte
Ogni iterazione esegue una ricerca esaustiva di un confine f, trova un nodo appena al di là di tale confine e utilizza il costo f di tale nodo come confine successivo.
Recursive Best-First Search
La ricerca best-first ricorsiva tenta di imitare il funzionamento di una ricerca best-first standard usando solamente uno spazio lineare. L’algoritmo assomiglia a una ricerca in profondità ricorsiva, ma invece di continuare a seguire indefinitamente il cammino corrente, utilizza la variabile f_limite per tenere traccia il valore f del miglior cammino alternativo che parte da uno qualsiasi degli antenati del nodo corrente.
Se il nodo corrente supera questo limite, la ricorsione torna indietro al cammino alternativo
Simplified memory-bounded A* (da rivedere)
SMA(simplified memory-bounded A) procede proprio come A, espandendo la foglia migliore finché la memoria è piena. A questo punto non può aggiungere un nuovo nodo all’albero di ricerca senza cancellarne uno vecchio.
SMA scarta sempre il nodo foglia peggiore, quello con costo f più alto
