Ricerca a memoria limitata
Una ricerca a memoria limitata è un algoritmo di ricerca sviluppato per utilizzare una quantità di memoria più ridotta rispetto agli algoritmi di ricerca tradizionali. Ogni algoritmo di ricerca deve utilizzare una determinata quantità di memoria per registrare le code dei dati analizzati e quelli da analizzare, nonché le migliori soluzioni possibili. La quantità di memoria dell'algoritmo può crescere anche in modo esponenziale nei problemi complessi, raggiungendo il limite massimo della memoria hardware del computer. Per eliminare o ridurre questo problema gli sviluppatori hanno ideato algoritmi specifici in grado di svolgere un lavoro di ricerca uguale o simile utilizzando una minore quantità di energia. Qui di seguito elenchiamo due algoritmi di ricerca a memoria limitata.
- Ricerca RBFS. La ricerca RBFS (Recursive Best First Search) è un algoritmo Best First in grado di funzionare con una minima quantità di memoria (spazio lineare).
- Ricerca MA*. La ricerca MA* (Memory-bounded A*) è un algoritmo A* (A-star) in grado di funzionare con una quantità di memoria limitata. Una volta esaurita la memoria disponibile l'algoritmo elimina le peggiori ipotesi in memoria per fare spazio alle migliori.
Gli algoritmi di ricerca a memoria limitata hanno il vantaggio di ridurre la complessità spaziale degli algoritmi di ricerca, ossia la quantità di memoria necessaria per effettuare una ricerca in un grafo o in un albero di ricerca. Tuttavia, la minore complessità spaziale degli algoritmi di ricerca a memoria limitata è spesso compensata dalla crescita del tempo di esecuzione dell'algoritmo ( complessità temporale ), dalla rinuncia alla completezza e/o dell'ottimalità della ricerca.
