| SMA* | |
|---|---|
| Classe | Algoritmo di ricerca |
| Struttura dati | Grafo |
| Caso peggiore temporalmente | [1] |
| Caso peggiore spazialmente | [2] |
| Ottimale | sì[3] |
| Completo | sì[4] |
| Manuale | |
SMA*, acronimo diSimplified Memory-Bounded A*, è unalgoritmo euristico per la ricerca delcammino minimo basato sull'algoritmo A*, proposto dall'informatico anglo-statunitenseStuart 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 famigliamemory-bounded A* (o MA*).[5]
L'idea di algoritmi a "memoria limitata" (bounded-memory) nasce dal fatto che altri algoritmi euristici, comeRBFS oIDA*, 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 costof verranno scartati (o "potati") dalla coda.[7] A questo punto, l'algoritmo adotterà una strategia RBFS,[7] ricordando il costof 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 inpseudocodice:
functionSMA_star(problema):camminocoda:insiemedinodi,ordinatiperillorocostof;begincoda.insert(problema.nodo-radice);whileTruedobeginifcoda.vuoto()thenreturnfallimento;//nessuna soluzione entra in memorianodo:=coda.begin();// nodo con il più basso costo fifproblema.soluzione(nodo)thenreturnsuccess;s:=successore(nodo)if!problema.soluzione(s)&&profondità(s)==massima_profonditàthenf(s):=inf;// non c'è più spazio disponibile in memoriaelsef(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 successoreendififnessunnuovosuccessorethenaggiornacostofdinodoe,senecessario,deisuoigenitori(ricorsivamente)ifnode.successori⊆codathencoda.rimuovi(nodo);// tutti i figli sono già stati aggiunti alla coda tramite un cammino più breveifmemoriaèpienathenbeginnodoPeggiore:=nodopiùsuperficialeconilpiùaltocostof;forgenitoreinnodoPeggiore.genitoridobegingenitore.successori.rimuovi(nodoPeggiore);ifneededthencoda.inserisci(genitore);endforendifcoda.inserisci(s);endwhileend
SMA* è caratterizzato delle seguenti proprietà:
Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica