Ricerca best-first ricorsiva

Da Teknopedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Ricerca best-first ricorsiva
ClasseAlgoritmo di ricerca
Struttura datiGrafo
Caso peggiore spazialmente[1]
Ottimale
Completo

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]

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]

  1. ^ Dove è il fattore di diramazione (branching factor) e è 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.

Voci correlate

[modifica | modifica wikitesto]
  Portale Informatica: accedi alle voci di Teknopedia che trattano di informatica