SMA*

SMA*
Classe	Algoritmo di ricerca
Struttura dati	Grafo
Caso peggiore temporalmente	${\displaystyle O(|E|)=O(b^{d})}$[1]
Caso peggiore spazialmente	${\displaystyle O(n)}$[2]
Ottimale	sì[3]
Completo	sì[4]
Manuale

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.^[5]

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.^[6] Come si evince anche dal nome, questo tipo di ricerca fa parte della famiglia memory-bounded A* (o MA*).^[5]

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,^[7] 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.^[7] A questo punto, l'algoritmo adotterà una strategia RBFS,^[7] 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à.^[8]

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 

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.

• (EN) Stuart Russell, Peter Norvig, 3.5 Informed (heuristic) search strategies, in Artificial Intelligence: A Modern Approach, 3ª ed., Pearson, 1º dicembre 2009, pp. 101-102, ISBN 978-0-13-604259-4.

• Algoritmo A*
• MA*
• RBFS
• IDA*

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica