SMA*

SMA*
Classe	Algoritmo di ricerca
Struttura dati	Grafo
Caso peggiore temporalmente	$O(|E|)=O(b^{d})$
Caso peggiore spazialmente	$O(n)$
Ottimale	sì
Completo	sì

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.

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*