Ricerca MA* ( Memory bounded A* )

La ricerca MA* è un algoritmo di ricerca informata del tipo A* (A-star o A-stella) in grado di utilizzare tutta la memoria disponibile dell'elaboratore. La sigla MA* significa Memory-bounded A*. La ricerca MA* riesce a completare un determinato problema computazionale attraverso una via intermedia alla ricerca A* e alla ricerca RBFS. Come abbiamo visto la ricerca A* è una ricerca euristica completa ma risente della complessità spaziale del grande utilizzo della memoria dell'elaboratore. La ricerca a memoria limitata RBFS è, invece, una ricerca informata in grado di ridurre l'impiego della memoria a uno spazio lineare ma che risente della complessità temporale di esecuzione a causa delle continue ricorsioni. La ricerca MA* procede come la ricerca A* entro una determinata quantità di memoria prefissata. Una volta impiegata tutta la quantità di memoria del computer l'algoritmo MA* cancella dalla memoria il nodo con il valore peggiore di costo per fare spazio al nuovo nodo e memorizza nel nodo-padre il valore del nodo dimenticato. In questo modo l'algoritmo ottiene i seguenti vantaggi.

• Minore ricorsioni. Agendo su una quantità di memoria superiore rispetto allo spazio di memoria lineare può elaborare i migliori cammini precedenti senza doverli ogni volta ricalcolare. A differenza dell'algoritmo RBFS può vantare uno spazio di memoria notevolmente superiore anche se non infinito. Ciò consente di ridurre la complessità temporale dell'algoritmo rispetto a un algoritmo di ricerca RBFS.
• Spazio di memoria limitato. Lo spazio di memoria è limitato a una determinata quantità. In tal modo l'algoritmo evita di mandare in overflow l'elaboratore quando il problema computazionale richiede un impiego di memoria superiore a quello della macchina. Fino all'esaurimento della memoria l'algoritmo lavora esattamente come l'algoritmo A*. Ciò consente di ridurre la complessità spaziale dell'algoritmo di ricerca rispetto a un algoritmo A*.
• Completezza. L'algoritmo di ricerca MA* è un algoritmo di ricerca completo. Se esiste una soluzione migliore entro una determinata profondità, compatibile con la quantità di memoria disponibile, l'algoritmo è in grado di trovarla al pari di un algoritmo A*. Quando la memoria è piena l'algoritmo deve cancellare i nodi peggiori dalla memoria (nodi dimenticati) per espandere i nuovi nodi. Tuttavia, l'algoritmo non elimina completamente i nodi dimenticati. Inserendo l'informazione dei nodi dimenticati nel nodo-padre, come un algoritmo RBFS, può tornare a riprendere in considerazione i nodi dimenticati nel caso in cui tutti gli altri cammini in memoria abbiano valori peggiori. In ogni caso, una volta esaurita la memoria a disposizione l'algoritmo non soddisfa più la proprietà della completezza della ricerca.

Esistono diverse versioni dell'algoritmo MA*. Tra queste merita d'essere citata la versione SMA* che consiste in una versione semplicata dell'algoritmo MA*. La sigla SMA* significa Semplified MA* ( MA* semplificato ).

Non ottimalità. Non è detto che l'algoritmo RBFS porti alla soluzione ottimale. Una volta esaurita la memoria disponibile è possibile che l'algoritmo erediti gli stessi problemi della ricerca RBFS e che non porti a risultati ottimali ma soltanto ai migliori risultati tra quelli raggiungibili. La ricerca MA* è ottima soltanto nel caso in cui la memoria disponibile sia sufficientemente elevata da raggiungere la profondità della soluzione ottimale.

Complessità temporale. La complessità temporale è direttamente correlata alla quantità di memoria disponibile. Quanto è maggiore la memoria a disposizione dell'algoritmo tanto minore è la possibilità di dover ricalcolare i cammini dimenticati e la generazione ripetuta degli stessi nodi.