SMA*, acronimo di Simplified Memory-Bounded A*, è un algoritmo euristico per la ricerca del cammino minimo basato sull'algoritmo A*, proposto dall'informatico anglo-statunitense Stuart Russell nel 1992.
Il vantaggio principale di SMA* è l'uso limitato della memoria, al contrario di A* che ha bisogno, nel caso peggiore, di uno spazio esponenziale. Tutte le altre caratteristiche di SMA* derivano direttamente da A*, incluse le prestazioni in termini di tempo, che nel caso peggiore rimangono esponenziali. Come si evince anche dal nome, questo tipo di ricerca fa parte della famiglia memory-bounded A* (o MA*).
Descrizione L'idea di algoritmi a "memoria limitata" (bounded-memory) nasce dal fatto che altri algoritmi euristici, come RBFS o IDA*, usano fin troppa poca memoria, a danno delle prestazioni di velocità. SMA* usa dunque un algoritmo sostanzialmente identico a A* fino a quando la memoria assegnatagli sarà sufficiente, dopodiché gli stati con il maggior costo f verranno scartati (o "potati") dalla coda. A questo punto, l'algoritmo adotterà una strategia RBFS,. ricordando il costo f migliore relativo ad ogni ramo potato (al posto del costo del nodo da cui il ramo parte). Quando tutti i rami esplorati sembreranno peggiori di quello dimenticato, quest'ultimo verrà ri-esplorato più in profondità.
Implementazione Segue una possibile implementazione in pseudocodice: function SMA_star(problema): cammino coda: insieme di nodi, ordinati per il loro costo f; begin coda.insert(problema.nodo-radice);
while True do begin if coda.vuoto() then return fallimento; //nessuna soluzione entra in memoria nodo := coda.begin(); // nodo con il più basso costo f if problema.soluzione(nodo) then return success;
s := successore(nodo) if !problema.soluzione(s) && profondità(s) == massima_profondità then f(s) := inf; // non c'è più spazio disponibile in memoria else f(s) := max(f(node), g(s) + h(s)); // il costo f del successore è il valore massimo fra // il costo f del genitore // il costo per raggiungere il successore + il costo predetto (euristico) del successore endif if nessun nuovo successore then aggiorna costo f di nodo e, se necessario, dei suoi genitori (ricorsivamente)
if node.successori ⊆ coda then coda.rimuovi(nodo); // tutti i figli sono già stati aggiunti alla coda tramite un cammino più breve if memoria è piena then begin nodoPeggiore := nodo più superficiale con il più alto costo f; for genitore in nodoPeggiore.genitori do begin genitore.successori.rimuovi(nodoPeggiore); if needed then coda.inserisci(genitore); endfor endif
coda.inserisci(s); endwhile end
Proprietà SMA* è caratterizzato delle seguenti proprietà: Lavora con un euristica, esattamente come A*. È completo se la soluzione più superficiale entra in memoria. È ottimale se la soluzione più superficiale entra in memoria, altrimenti restituisce la soluzione migliore che è riuscito a trovare. Evita di esplorare più volte lo stesso stato finché la memoria premette di farlo. Usa tutta la memoria a disposizione. L'uso della memoria è proporzionale alla velocità di esecuzione dell'algoritmo. Avendo abbastanza memoria da ospitare l'intero albero di esecuzione, la velocità di esecuzione sarà ottimale.
Note
Bibliografia
Voci correlate Algoritmo A* MA* RBFS IDA*
Categoria:Algoritmi sui grafi Categoria:Algoritmi di ricerca