Ricerca best-first ricorsiva

Ricerca best-first ricorsiva
ClasseAlgoritmo di ricerca
Struttura datiGrafo
Caso peggiore spazialmente O ( b d ) {\displaystyle O(bd)} [1]
Ottimalesì
Completosì
Manuale

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]

Descrizione

Sezione vuotaQuesta sezione sull'argomento informatica è ancora vuota. Aiutaci a scriverla!

Proprietà

Come per A*, RBFS garantisce una soluzione ottimale per il problema del cammino minimo quando la funzione euristica h {\displaystyle h} è ammissibile,[6] ovvero tale che

h ( n ) ≤ c ( n ) {\displaystyle h(n)\leq c(n)}

per tutti i nodi n {\displaystyle n} del grafo, dove c ( n ) {\displaystyle c(n)} è il costo effettivo per raggiungere la soluzione a partire dal nodo n {\displaystyle n} .

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

  1. ^ Dove b {\displaystyle b} è il fattore di diramazione (branching factor) e d {\displaystyle d} è la profondità della soluzione.
  2. ^ a b Nilsson, 2002, p. 172.
  3. ^ Russell & Norvig, 2005, p. 134.
  4. ^ a b Korf, 1992.
  5. ^ Russell & Norvig, 2009, p. 99.
  6. ^ a b c Russell & Norvig, 2009, p. 101.

Bibliografia

  • (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.

Voci correlate

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica