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	${\displaystyle O(bd)}$[1]
Ottimale	sì
Completo	sì

Descrizione

Proprietà

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

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

per tutti i nodi ${\displaystyle n}$ del grafo, dove ${\displaystyle c(n)}$ è il costo effettivo per raggiungere la soluzione a partire dal nodo ${\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]