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]

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]

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,[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]

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

1. Dove ${\displaystyle b}$ è il fattore di diramazione (branching factor) e ${\displaystyle d}$ è la profondità della soluzione.
2. Dove ${\displaystyle n}$ è il numero di nodi che entrano in memoria.
3. Se la soluzione più superficiale entra in memoria, altrimenti restituisce la soluzione migliore che è riuscito a trovare.
4. Se la soluzione più superficiale entra in memoria.
5. Rong Zhou e Eric A. Hansen, Memory-Bounded A* Graph Search (PDF), Proceedings of the Fifteenth International Florida Artificial Intelligence Research Society Conference, Pensacola Beach, Florida, 2002, pp. 203-209. URL consultato il 29 marzo 2020 (archiviato dall'url originale l'8 settembre 2017).
6. (EN) Max Welling, Informed search algorithms (PDF), su ics.uci.edu, Università della California, Irvine, pp. 31-33. URL consultato il 27 marzo 2020 (archiviato il 3 ottobre 2015).
7. Russell & Norvig, 2009, p. 101.
8. S. Russell, Efficient memory-bounded search methods, a cura di Neumann B., Proceedings of the 10th European Conference on Artificial intelligence, Vienna, Austria, John Wiley & Sons, New York, NY, 1992, pp. 1–5.

Bibliografia

• (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.

Voci correlate

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