Ricerca RBFS
La ricerca RBFS è un algoritmo di ricerca informata a memoria limitata basato sulla memorizzazione del migliore cammino alternativo. La sigla RBFS significa Recursive Best First Search. Si tratta di una ricerca Best First ricorsiva su uno spazio lineare. In altri termini, l'algoritmo utilizza soltanto un piccolo spazio di memoria per registrare il migliore cammino alternativo ( valore di backup ). Quando il nodo corrente supera il valore di backup l'algoritmo RBFS torna indietro per espandere il cammino alternativo. Nel grafo seguente abbiamo rappresentato un esempio elementare di ricerca RBFS. Nei nodi del grafo sono i valori euristici che indicano la distanza stimata tra il nodo e l'obiettivo. Il valore di backup è, invece, indicato nel quadrato vino al nodo selezionato.
L'algoritmo RBFS sceglie sempre il percorso migliore, come un algoritmo Best First, mantenendo in memoria il valore del cammino alternativo. Ciò consente all'algoritmo di tornare indietro sui suoi passi quando la via intrapresa diventa troppo onerosa. Ad esempio, una volta giunto al nodo F l'algoritmo si accorge che il passaggio al nodo D implica un costo superiore al valore di backup del cammino alternativo, quindi torna indietro ( ricorsione ) per espandere quest'ultimo. Lo stesso esempio può essere rappresentato su un albero di ricerca. L'algoritmo RBFS viene ideato da Korf nel 1993 anche se non mancano altri esperimenti precedenti di algoritmi ricorsivi.
Complessità spaziale. Il principale vantaggio della ricerca RBFS è l'utilizzo minimo della memoria. L'algoritmo vanta un livello di complessità spaziale molto basso poiché utilizza uno spazio lineare. Una caratteristica particolarmente utile in passato quando la memoria hardware dei computer era particolarmente limitata.
Complessità temporale. La scarsa memoria su cui si basa l'algoritmo non elimina il rischio di analizzare più volte sempre gli stessi percorsi o di incappare in cammini ridondanti. Ciò equivale a dire che la complessità temporale dell'algoritmo può diventare anche molto elevata.
