Visualizza wikitesto di SMA*

{{Algoritmo
|classe = [[Algoritmo di ricerca]]
|struttura dati = [[Grafo]]
|immagine = 
|didascalia = 
|tempo = <math>O(|E|) = O(b^d)</math><ref>Dove <math>b</math> è il [[fattore di diramazione]] (''branching factor'') e <math>d</math> è la profondità della soluzione.</ref>
|spazio = <math>O(n)</math><ref>Dove <math>n</math> è il numero di nodi che entrano in memoria.</ref>
|ottimale = sì<ref>Se la soluzione più superficiale entra in memoria, altrimenti restituisce la soluzione migliore che è riuscito a trovare.</ref>
|completo = sì<ref>Se la soluzione più superficiale entra in memoria.</ref>
}}
'''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.<ref name="Zhou-Hansen-2002">{{cita pubblicazione|url=https://www.aaai.org/Papers/FLAIRS/2002/FLAIRS02-041.pdf|titolo=Memory-Bounded A* Graph Search|autore=Rong Zhou|autore2=Eric A. Hansen|conferenza=Proceedings of the Fifteenth International Florida Artificial Intelligence Research Society Conference|città=Pensacola Beach, Florida|pp=203-209|data=2002|accesso=29 marzo 2020|dataarchivio=8 settembre 2017|urlarchivio=https://web.archive.org/web/20170908193318/http://www.aaai.org/Papers/FLAIRS/2002/FLAIRS02-041.pdf|urlmorto=sì}}</ref>

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.<ref>{{cita web|url=https://www.ics.uci.edu/~welling/teaching/271fall09/InfSearch271f09.pdf|lingua=en|titolo=Informed search algorithms|autore=Max Welling|editore=[[Università della California, Irvine]]|pp=31-33|accesso=27 marzo 2020|urlmorto=no|urlarchivio=https://web.archive.org/web/20151003214356/http://www.ics.uci.edu/%7ewelling/teaching/271fall09/InfSearch271f09.pdf|dataarchivio=3 ottobre 2015}}</ref> Come si evince anche dal nome, questo tipo di ricerca fa parte della famiglia [[memory-bounded A*]] (o MA*).<ref name="Zhou-Hansen-2002"/>

== 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,<ref name="russel-norvig-2009"/> 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.<ref name="russel-norvig-2009"/> A questo punto, l'algoritmo adotterà una strategia RBFS,<ref name="russel-norvig-2009">{{cita|Russell & Norvig, 2009|p. 101}}.</ref> 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à.<ref>{{Cita conferenza|cognome= Russell |nome=S. |anno= 1992 |titolo=Efficient memory-bounded search methods |conferenza= Proceedings of the 10th European Conference on Artificial intelligence |città= Vienna, Austria |curatore= Neumann B. |editore= John Wiley & Sons, New York, NY |pp= 1-5 }}</ref>

== Implementazione ==
Segue una possibile implementazione in [[pseudocodice]]:
<syntaxhighlight lang="pascal">
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
</syntaxhighlight>

== Proprietà ==
SMA* è caratterizzato delle seguenti proprietà:
* Lavora con un [[Euristica (informatica)|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 ==
<references/>

== Bibliografia ==
* {{cita libro|lingua=en|titolo=Artificial Intelligence: A Modern Approach|anno=2010|url=https://archive.org/details/nlsiu.340.11.rus.27359|autore=[[Stuart Russell]], [[Peter Norvig]]|data=1º dicembre 2009|edizione=3|pp=[https://archive.org/details/nlsiu.340.11.rus.27359/page/101 101]-102|capitolo=3.5 Informed (heuristic) search strategies|editore=Pearson|isbn=978-0-13-604259-4|cid=Russell & Norvig, 2009}}

== Voci correlate ==
* [[Algoritmo A*]]
* [[MA*]]
* [[RBFS]]
* [[IDA*]]

{{Algoritmi ricerca grafi}}
{{portale|informatica}}

[[Categoria:Algoritmi sui grafi]]
[[Categoria:Algoritmi di ricerca]]