Ricerca best-first ricorsiva
La ricerca best-first ricorsiva[2][3] (in inglese recursive best-first search, nota anche con l'acronimo RBFS) è un algoritmo di ricerca euristico proposto da Richard Korf nel 1992. Si tratta di un'estensione dell'algoritmo best-first search che sfrutta uno spazio lineare anziché esponenziale.[4][5]
| Ricerca best-first ricorsiva | |
|---|---|
| Classe | Algoritmo di ricerca |
| Struttura dati | Grafo |
| Caso peggiore spazialmente | [1] |
| Ottimale | sì |
| Completo | sì |
Descrizione modifica
Proprietà modifica
Come per A*, RBFS garantisce una soluzione ottimale per il problema del cammino minimo quando la funzione euristica è ammissibile,[6] ovvero tale che
per tutti i nodi del grafo, dove è il costo effettivo per raggiungere la soluzione a partire dal nodo .
La sua complessità, in termini di spazio è lineare rispetto alla soluzione più profonda, mentre in termini di tempo è più difficile da qualificare.[6] Sperimentalmente, rispetto al best-first search quest'ultima sembra peggiorare di un fattore costante.[4]
RBFS è particolarmente utile quando si opera in un sistema con memoria limitata. D'altro canto, in generale, rispetto ad altri algoritmi RBFS usa fin troppa poca memoria, che potrebbe essere invece sfruttata per migliorarne la velocità (cfr. memoizzazione).[6] È comunque leggermente più veloce di IDA*, rispetto al quale occupa poca memoria in più.[2]
Note modifica
- ^ Dove è il fattore di diramazione (branching factor) e è la profondità della soluzione.
- ^ a b Nilsson, 2002, p. 172.
- ^ Russell & Norvig, 2005, p. 134.
- ^ a b Korf, 1992.
- ^ Russell & Norvig, 2009, p. 99.
- ^ a b c Russell & Norvig, 2009, p. 101.
Bibliografia modifica
- (EN) Richard E. Korf, Linear-Space Best-First Search: Summary of Results (PDF), Proceedings of the 10th National Conference on Artificial Intelligence, San Jose, California, 1992.
- (EN) Richard E. Korf, Linear-space best-first search, in Artificial Intelligence, vol. 62, n. 1, luglio 1993, pp. 41-78, DOI:10.1016/0004-3702(93)90045-D.
- Nils J. Nilsson, Ricerca best-first ricorsiva, in Salvatore Gaglio (a cura di), Intelligenza artificiale, traduzione di Ivana La Rosa, Apogeo Editore, 2002, pp. 172-173, ISBN 88-7303-746-1.
- Stuart Russell, Peter Norvig, Ricerca euristica con memoria limitata, in Intelligenza artificiale. Un approccio moderno, traduzione di Stefano Gaburri, vol. 1, 2ª ed., Pearson Italia, aprile 2005, pp. 134-137, ISBN 88-7192-228-X.
- (EN) Stuart Russell, Peter Norvig, Informed (heuristic) search strategies, in Artificial Intelligence: A Modern Approach, 3ª ed., Pearson, 1º dicembre 2009, pp. 99-101, ISBN 9780136042594.
